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."
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.
[+] [-] javpaw|9 years ago|reply
[+] [-] losteverything|9 years ago|reply
[+] [-] drostie|9 years ago|reply
"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."
[+] [-] gohrt|9 years ago|reply
[+] [-] ThrustVectoring|9 years ago|reply
[+] [-] gohrt|9 years ago|reply
[+] [-] tofupup|9 years ago|reply