Ive been asked to find how many ways can we split a group of n numbers: {1,2…..n} to 3 groups. Assume that the groups are identical, means for example that the partition of all the numbers to one group is counted only once.
My solution at first was 3^n / 3! but this isn't true.
Best Answer
There are $3^n$ ways to assign each of the numbers to one of the three groups. In three of these cases, all will end up in one single group, which is to be counted as one case. In the remaining cases, we will have three pairwise distinct groups (even though one of them may be empty), hence in order to "un-distinguish" them, we need to divide by $3!$. Thus in total we count $$ 1 +\frac{3^n-3}{6}.$$