Tuesday, April 14, 2009

n choose m

If I have 3 kids and I want to form a team of 2 kids, how many different teams could I create? [3]

If I have 4 kids, how many different teams of 2 kids? [6]

If I have 5 kids, how many different 2-kid teams? [10]

If I have 6 kids, how many different 2-kid teams? [15]

[At this point they recognized the sum of the numbers from 1 to n-1, which they know the formula for: n kids can form n(n-1)/2 teams of 2.

What about 2 kids? [1]

What about 6 kids forming teams of 3?

[The kids weren't sure how to enumerate the teams of 3.] What about 3 kids forming a team of 1? [3]

What about 3 kids forming a team of 3? [1]

What about 3 kids forming a team of 2? [3. It's like forming a team of 1 kid who is not on the team.]

What about 3 kids forming a team of 0? [1. The immediate response is 0, but the right answer is 1. There is one team with no one on it.]

If you have n kids forming teams of size m then

  • the first kid could be any of n,
  • the second kid could be any of (n-1),
  • the third kid could be any of (n-2),
  • ...
  • the mth kid could be any of (n-m+1).
This is n!/(n-m)!.

Those all get multiplied together. Now the problem is that the same combination of kids gets counted more than once. How many times does a team of m kids get counted?

  • the first kid could have ended up in any of m positions (being chose first, second, third, etc.),
  • the second kid could have ended up in any of m-1 positions,
  • ...
  • the mth kid can only end up in one position.
So the formula is n!/((n-m)! m!).

No comments:

Post a Comment

About Me

I'm research faculty at MIT, and Chief Architect at Tokutek.