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