It's worth pointing out that the conventional formula for N choose K has a "story proof" as well, and it helps introductory students who can't necessarily keep straight whether, in these groups, order matters.
"There are N people in a room. Place a line of tape across the room dividing it into two halves; we'll say this tape goes North-South. Now ask K of them (politely, but also uniformly-at-random) to be on the East side of the tape and the N-K remainder are on the West side of the tape. We know from the definition that there are N choose K ways to do this.
"Now we ask the people on the East side to stand along the East wall and the people on the West side to stand along the West wall; along the way we will have to choose among the K! and (N-K)! different orderings for each set. So we have a uniform distribution of these people chosen from K! (N-K)! (N choose K) different possibilities.
"Now kindly ask them to walk in the order they're in to the North wall, but to remain on their side of the tape. You suddenly see that this result must be the same as simply asking the N people to line up uniformly-at-random along the North wall and you then place a piece of tape that divides them into the two groups. Every possibility in the one story comes from exactly one configuration in the other story and vice versa, therefore N! = (N choose K) K! (N - K)! no matter what N or K were."
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.
These are fun. There's another similar technique, which proves that a function f(n) maps positive integers to other positive integers by describing the set that the function counts.
any ideas on the last one? It's totally different structure from all the others -- it doesn't involve combinations at all. It seems totally out of place.
