[Math] How many ways to split 20, and how many such ways contain a number greater or equal to 5

combinatoricsprobability

I came across an interesting question:

How many ways you can split 20 into? For example, {20} as a single group is one way, {1,1,…1} as 1s in 20 groups is another way. And many other ways in middle such as {18,1,1}, {4,4,4,4}, et al. In total, how many such ways.

And another question on top of the above, how many such ways contain at least one group with number greater or equal to 5? For example, {17,3} is one such way because 17 >= 5. {6,6,8} is another way because 6 >= 5 and 8 >= 5. {3,3,3,3,3,3,2} isn't such a way because 3 and 2 both < 5.

Best Answer

You want the number of partitions of $20$. This sequence is OEIS A000041; according to the table here there are $627$ partitions of $20$. There is no really nice closed form for the sequence.

To get the answer to your second question, subtract from this the number of partitions of $20$ whose parts are all at most $4$. The latter number is given by the partition function $q$, specifically, $q(20,4)$. This is $T(20,4)$ in OEIS A026820; more conveniently, the sequence of $T(n,4)$ is OEIS A001400, and this table gives the value $T(20,4)=108$. Thus, the answer to your second question is $627-108=519$.

For small values of $n$ and $k$ reference to these tables is probably the easiest way to answer such questions. For larger values you can make use of the recurrence relations satisfied by the various partition functions involved.