I had to come up with a formula that correctly counts the number of distinct partitions of groups of 2 and/or 3 for a class of n students. For example, a class of 5 students a, b, c, d, and e has ten distinct partitions:
- ab/cde
- ac/bde
- ad/bce
- ae/bcd
- bc/ade
- bd/ace
- be/acd
- cd/abe
- ce/abd
- de/abc
With the help of the OEIS website, I came up with the following recursive formula:
f(n) = (n - 1)*f(n - 2) + (n - 1)*(n - 2)*f(n - 3)/2
with these base cases:
f(0) = 1
f(1) = 0
f(2) = 1
f(3) = 1
Now I must prove that this formula works for every n. I can count by hand up to a class of 7 students and compare my answers to the formula to show that the answers match, but anything beyond that becomes too tedious. However, the recursiveness of this formula makes it very complicated for me to successfully prove its correctness mathematically. Any help is appreciated.
The sequence is OEIS A227937
To derive the recurrence relation, condition on whether student $n$ appears in a group of 2 or a group of 3. In the first case, there are $n-1$ choices of students to appear in the group of 2 with $n$ and then $f(n-2)$ partitions of the remaining $n-2$ students into groups of 2 or 3. In the second case, there are $(n-1)(n-2)/2$ choices of pairs of students to appear in the group of 3 with $n$ and then $f(n-3)$ partitions of the remaining $n-3$ students into groups of 2 or 3. Because these two cases are disjoint and cover all possibilities, we have shown that $$f(n) = (n-1) f(n-2) + (n-1)(n-2) f(n-3)/2.$$