# Partitions into 2 and 3

My new OEIS sequence for the weekend: A227937. It begins \( 1, 0, 1, 3, 10, 25, 105, 385\dots \) and counts the number of partitions of a set of \( n \) items into subsets that must have either two or three elements per subset.

A polynomial recurrence relation is not hard to derive from the fact that the \( n \)th element must either be in a set of two (of which there are \( n-1 \) choices) or a set of three (\( (n-1)(n-2)/2 \) choices). From this recurrence, it follows that once three consecutive values in the sequence have the same divisor, so will all subsequent values. So, it tends to pick up prime factors as it goes, causing later values in the sequence to be highly divisible. For instance,

\[ \begin{align} a_{102} = {}& 5^{12} \cdot 7^8 \cdot 11^5 \cdot 13^4 \cdot 17^3 \cdot 19^3 \cdot 23^3 \cdot 29^2 \cdot {} \\ & 31^2 \cdot 37 \cdot 41 \cdot 43 \cdot 47 \cdot 53 \cdot 59 \cdot 61 \cdot 67 \cdot {} \\ & 71 \cdot 73 \cdot 79 \cdot 83 \cdot 89 \cdot 97 \cdot 101 \cdot 3229 \cdot {} \\ & 134593 \cdot 292152888047 \cdot 72472250580547 \\ \end{align} \]In fact, all prime powers not of the form \( 2^k \) or \( 3^k \) each divide all but finitely many values in the sequence. I don't see how to derive this from the recurrence easily, but here's a direct proof: The number of partitions for \( n \) is equal to the sum, for pairs \( (a,b) \) such that \( 2a+3b=n, \) of partitions of \( n \) into sets of size \( 2a \) and \( 3b, \) multiplied by the numbers of partitions of \( 2a \) into pairs and \( 3b \) into triples. The number of partitions of \( 2a \) into pairs is a double factorial (eventually divisible by all odd numbers) and the number of partitions of \( 3a \) into triples is a multinomial that is eventually divisible by all numbers prime to \( 6. \) So for each term in the sum, at least one of its three factors is divisible by large prime powers, and it follows that the same is true for the whole sum.

I'll leave to others the task of filling in OEIS with the counts of partitions into sets of other restricted sizes, but I think there must be quite a few other interesting sequences in that vein.