Number of ways to distribute $n$ items into bins, in decreasing order

103 Views Asked by At

I want to put $n$ items into arbitrarily many bins (equivalently, $n$ bins) such that each bin, has at most, as many items as the previous bin. The items are identical, so we only distinguish distributions by how many items each bin gets.

Another framing is to count how many non-decreasing functions $f : [1,n] \rightarrow [0,n]$ there are such that $\sum_{i=1}^{n} f(i)=n$.

I wrote a small computer program to calculate it and found the first few terms, but I struggle to come up with an exact formula. All I have is this -- very much not tight -- upper bound ${2n-1}\choose{n}$.

The first few terms: $2, 4, 7, 12, 19, 30, 45, 67, 97, 139, 195, 272, 373$

1

There are 1 best solutions below

0
On

From OEIS, (https://oeis.org/A000070), this is equivalent to asking the sum of the number of partitions of the numbers from 1 to n, along with other things if you want to take a look.