How many teams (Solution)
I found this to be a surpisingly tricky counting problem. The key is to figure out how to partition the space such that you don’t overcount.
Here is one way:
Let’s define \(f(N, k)\) as the number of ways to break \(N\) kids into exactly \(k\) teams.
Total number of ways to break N kids into teams is:
\[f(N, 1) + f(N, 2) + f(N, 3) + ... + f(N, N)\]In english, all I’m saying is the total number of ways to break N kids up into teams is the number of ways to break them up into exactly 1 team, plus the number of ways I can break them up into exactly 2 teams, and so on. This seems fairly tri vial but it allows you to separate the space of teams rather nicely.
\(f(N, 1) = 1\), which seems fairly obvious. But what is \(f(N, 2)\)?
Well, let’s first answer an easier question. Call \(g(N, k)\) the number of ways you can break up N kids into k named groups. So, in this problem, putting all kids in group #1 is considered different from putting all the kids in group #2. This question has a pretty answer: since you can have \(k\) choices for each of \(N\) kids, it’s \(g(N, k) = k^N\).
How can we relate \(g(N, 2)\) to \(f(N, 2)\)? \(g(N, 2)\) contains groupings with a total of 2 teams and groupings with a total of 1 team. How many groupings with only 1 team (since those shouldn’t be counted for \(f(N, 2)\))? Well, there’s one option where all \(N\) kids are put into group #1 and there’s one option where all \(N\) kids are put into group #2. More generally, there’s \(f(N, 1)\) ways to put \(N\) kids into exactly one group, but if there are two possible groups, which one group should we put them in - there’s \({N \choose 1}\) choices for that.
\[f(N, 2) = \frac{g(N, 2) - {N \choose 1} f(N, 1)}{2!} \\ f(N, 2) = \frac{2^N - {N \choose 1} f(N, 1)}{2!}\]Why do we need to divide by \(2!\) at the end? Since the teams are named in \(g\), but not in \(f\), we will overcount groups of \(2\) by a factor of \(2!\).
So, let’s try to compute \(f(N, 3)\) manually before generalizing to \(f(N, k)\).
\[f(N, 3) = \frac{3^N - {N \choose 2} f(N, 2) 2! - {N \choose 1} f(N, 1)}{3!}\]More generally:
\[f(N, k) = \frac{k^N - \sum_{i=1}^{k-1}{N \choose i} f(N, i) i!}{k!}\]Finally, the question asked how many ways can you make teams out of N kids, regardless of group size, which is just:
\[\sum_{k=1}^{N} f(N, k)\]To double check that this looks reasonable for small N:
| N | #ways |
|---|---|
| 1 | 1 |
| 2 | 2 |
| 3 | 5 |
| 4 | 15 |
| 5 | 52 |
| 6 | 203 |
| 7 | 877 |
| 8 | 4140 |
| 9 | 21147 |
| 10 | 115975 |