Partitions of a number for a fixed number of integers

206 Views Asked by At

Is there a name for the number of ways to write a positive integer $n$ as a sum of $k$ integers, including 0?

For example, the number 4 can be written as the sum of 3 numbers in the following ways:

  • 4+0+0
  • 3+1+0
  • 2+2+0
  • 2+1+1

Note that $1+2+1$ counts as being the same as $2+1+1$. Also, the number 5 can be written as the sum of 3 numbers in the following ways:

  • 5+0+0
  • 4+1+0
  • 3+2+0
  • 3+1+1
  • 2+2+1

Aside: If we wanted to treat $1+2+1$ as being distinct $2+1+1$, then the number of ways would be equivalent to the number of ways of choosing $k$ items from $n$ options (with replacement, and order does not matter): ${n + k -1 \choose k}.$

Is there a closed form expression for this number? If there was, let's call it $n_k.$ It would not follow that the total number of partitions is equal to $\sum_{k=1}^{k=n} n_k,$ because the fact that we allow $0$ means that this would overcount partitions.

1

There are 1 best solutions below

0
On BEST ANSWER

The ways to write a positive integer $n$ as non-ordered sums of $k$ integers are called the partitions of $n$ into $k$ parts, or the strict partitions of $n$ into $k$ parts.

If the part $0$ is allowed, we have the partitions of $n$ with $0$ into $k$ parts, or the weak partitions of $n$ into $k$ parts.

Ordered integer partitions are called integer compositions.

As Henry wrote in his comment, the number you ask is the number of partitions of $n$ into up to $k$ parts (OEIS: A026820).

See e.g. the books of MacMahon, Comtet or Charalambides.