Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
I think what your describing is integer partitions, en.wikipedia.org/wiki/Partition_(number_theory) –  Ethan Jan 23 '13 at 0:12

2 Answers 2

up vote 0 down vote accepted

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.

share|improve this answer

There are (1) partitions of an integer; and (2) ordered partitions of an integer. The partitions of $4$ are these: \begin{align} & 4 \\ & 3 + 1 \\ & 2 + 2 \\ & 2 + 1 + 1 \\ & 1 + 1 + 1 + 1 \end{align} The ordered partitions of $4$ are these: \begin{align} & 4 \\ & 3 + 1 \\ & 1 + 3 \\ & 2 + 2 \\ & 2 + 1 + 1 \\ & 1 + 2 + 1 \\ & 1 + 1 + 2 \\ & 1 + 1 + 1 + 1 \end{align} Generally it's easier to cound ordered things than unordered things. Google "partition of an integer" and you'll find tons of stuff on this.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.