2 ms·

That explanation leaves me more confused than when I started -- there's too much to try to follow and visualize. Maybe it works in person.

by gohrt 10y ago

drostie 10y ago
Yeah. I think it works when you take three fingers from your left hand and mash them together with all five from your right, representing a set of 8 elements. Now to perform 8-choose-3 and choose a set of 3 out of the 8 elements, you separate your hands and you've "chosen" (albeit in advance by the topology of your hands) a group of 3 out of the 8, but your fingers are still bunched up because these are sets and you haven't ordered everyone yet. Now we ask for both sides to line up, you "order" them by flattening out your hands facing each other palm-to-palm, as if you were holding a box on its sides: the 3 and 5 fingers on either side are now lined up. Now if you've been following the math you have (8 choose 3) * 3! * 5! ways that you could have done those steps. Now you take these 2 hands facing each other and turn them palms-down so that they form one line of 8 fingers, a permutation of the original set-of-8 which happens to have a piece of tape (or other division) separating the first 3 from the last 5. Ignoring this division you have just the permutation of 8. With a little reasoning you get the one-to-one and onto properties of this mapping: if you got to some permutation of the 8 this way, there was only one choice of the 3 out of the 8, and only one ordering of the left, and only one ordering of the right, that generates that permutation of the 8. Furthermore every permutation can be generated by those very steps of choosing the first 3 of the permutation in the 8-choose-3 step and then ordering the two groups appropriately. Since this process is one-to-one and onto, it must be the case that (N choose K) K! (N - K)! = N!, the total number of possibilities for each must be the same. Does that help?

That explanation leaves me more confused than when I started -- there's too much to try to follow and visualize. Maybe it works in person.

by gohrt 10y ago

That explanation leaves me more confused than when I started -- there's too much to try to follow and visualize. Maybe it works in person.

drostie 10y ago

Yeah. I think it works when you take three fingers from your left hand and mash them together with all five from your right, representing a set of 8 elements. Now to perform 8-choose-3 and choose a set of 3 out of the 8 elements, you separate your hands and you've "chosen" (albeit in advance by the topology of your hands) a group of 3 out of the 8, but your fingers are still bunched up because these are sets and you haven't ordered everyone yet. Now we ask for both sides to line up, you "order" them by flattening out your hands facing each other palm-to-palm, as if you were holding a box on its sides: the 3 and 5 fingers on either side are now lined up. Now if you've been following the math you have (8 choose 3) * 3! * 5! ways that you could have done those steps. Now you take these 2 hands facing each other and turn them palms-down so that they form one line of 8 fingers, a permutation of the original set-of-8 which happens to have a piece of tape (or other division) separating the first 3 from the last 5. Ignoring this division you have just the permutation of 8. With a little reasoning you get the one-to-one and onto properties of this mapping: if you got to some permutation of the 8 this way, there was only one choice of the 3 out of the 8, and only one ordering of the left, and only one ordering of the right, that generates that permutation of the 8. Furthermore every permutation can be generated by those very steps of choosing the first 3 of the permutation in the 8-choose-3 step and then ordering the two groups appropriately. Since this process is one-to-one and onto, it must be the case that (N choose K) K! (N - K)! = N!, the total number of possibilities for each must be the same. Does that help?