What is wrong with my reasoning on this partitioning question?

Question

I set the following question for my secondary school students, but realised it's harder than I intended.

How many ways can a class of 20 students be divided into three teams of any size?

I realise that this is unclearly phrased, but the intended interpretation was that the teams could be empty, and hence "three teams" should read something like "up to three teams".

My reasoning would be the following, which must be wrong as it does not give an integer. Why is this reasoning wrong?

---

Assign to each student one of the letters A, B or C. There are $3^{20}$ ways to do this. However, if you permute all the A's and B's then the division of students is the same. So we divide by the number of permutations of ABC, which is $3!$. So the answer is $$\frac{3^{20}}{3!}=581\,130\,733.5$$

Answer 1

Your reasoning is very close to correct: you count assignments of $A, B, C$ to your 20 students, but then you've counted every possible split into teams $3!= 6$ times, and you correct by dividing by 6. However, you actually haven't counted every split 6 times: you've only counted the split $AAAAAAAAAAAAAAAAAAAA$ three times! So the correct answer is actually $$ \frac{3^{20} - 3}{3!} + \frac33 = 581130734. $$

Answer 2

Hint: The Stirling number $S(n,k)$ of the second kind counts the number of ways to partition a set of $n$ elements into $k$ nonempty subsets. These numbers can be computed by a recursion, here $S(20,3)$. If empty subsets are allowed, then you have to consider $S(20,1)$ and $S(20,2)$, too.

Answer 3

You assumed every arrangement appears $3!$ times, i.e. all the strings you can get from a given string by permuting $\{A,B,C\}$ are different. This is true as long as there is at most one empty team. However, the (unique) arrangement with two empty teams only appears $3$ times, as the strings $AA...A$, $BB...B$ and $CC...C$. Thus the answer should be $\frac{3^{20}-3}{3!}+1$.