# Number of ways to split $N$ up into $k$ baskets such that different arrangements of the $k$ baskets are considered equivalent?

I've been considering the problem of integer partitions and while there have been some answers for related questions, I haven't came across a solution for my following problem.

Suppose you have $$N$$ balls and wish to throw it into $$k$$ indistinguishable baskets. Find the number of ways to do this.

Then $$S_1+S_2+...+S_k= N$$ where each $$S_i$$ ca n only take on integer values. So if $$k=3$$ and $$N=5$$, then something like $$(1,1,3)$$ will be equivalent to $$(1,3,1)$$ and $$(3,1,1)$$.

I've thought about generating polynomials, and if I wanted the number of non-distinct ways to do this, I would take the coefficient of $$x^5$$ in the expansion of $$(x^1+x^2+x^3)^3$$, which also can be evaluated by the multinomial coefficient formula to give $$6$$. It makes sense as the only sets of values $$(S_1,S_2,S_3)$$ can take are $$(1,1,3)$$ and $$(1,2,2)$$, both of which can be permuted $$3$$ times.

There was another solution to a related problem, and it involved the number of ways to split $$N$$ up into $$N$$ integers or less such that no two numbers are the same. For our problem, it would be the sum of the number of ways to split $$5$$ into $$1$$ number, split $$5$$ into $$2$$ numbers, split $$5$$ into $$3$$ numbers... such that $$S_i \neq S_j, \forall i \neq j$$. In this case, integer partitions of $$5$$ into $$3$$ number will not be considered, since both $$(1,1,3)$$ and $$(1,2,2)$$ contain repetitions. The $$3$$ ways that this can be done are $$(5,0), (4,1), (3,2)$$.

But obviously this is not what I want as it doesn't count $$(1,1,3)$$ and $$(1,2,2)$$.

Is there a formula to do this? A related question is here, but no explicit algorithm/formula is given.

EDIT: @marcelgoh said that Stirling numbers of the second kind would work. I have a follow-up question:

Is there a way to iterate through permutations of numbers making up $$N$$, but in a 'Stirling' sense?

For instance, if I wanted to express:

$$\frac{20!}{(2*1+1)!(2*1+1)!(2*3+1)!} + \frac{20!}{(2*1+1)!(2*3+1)!(2*1+1)!} + \frac{20!}{(2*3+1)!(2*1+1)!(2*1+1)!} + \frac{20!}{(2*2+1)!(2*2+1)!(2*1+1)!} + \frac{20!}{(2*2+1)!(2*1+1)!(2*2+1)!} + \frac{20!}{(2*1+1)!(2*2+1)!(2*2+1)!}$$

I could use: $$\sum_{i+j+k=5, i,j,k\geq 1}\frac{20!}{(2i+1)!(2j+1)!(2k+1)!}$$

But what if I just wanted:

$$\frac{20!}{(2*1+1)!(2*1+1)!(2*3+1)!} + \frac{20!}{(2*2+1)!(2*2+1)!(2*1+1)!}$$

Could I use something like:

$$\sum_{i+j+k=5, 1\leq i\leq j\leq k}\frac{20!}{(2i+1)!(2j+1)!(2k+1)!}$$

Or is there some less messy notation for the same concept?

• I'm having trouble understanding the follow-up question. My guess is that you're fixing $N = 5$ and you want to iterate through each of the $\big\{ {5\atop k} \big\}$ combinations of summands equalling $5$, for $k = 1,2,3,4$. Is this correct? – marcelgoh Aug 2 '19 at 7:02
• More of I want to iterate through the summands for $n=5, k=3$. Also I checked Stirling numbers of the second kind out and it is useful to $n$ labelled elements, but what if my elements are unlabelled, say identical balls? So if let's say $n=6, k=4$, I would like to iterate through $(1,1,1,3), (1,1,2,2)$. If $n=7, k=3$, then the iteration would be $(1,1,5), (1,2,4), (1,3,3), (2,2,3)$. – Yip Jung Hon Aug 2 '19 at 7:05
• Ahh okay. I believe this is $p_k(n)$, the number of partitions of $n$ into exactly $k$ parts. I'll edit my answer. – marcelgoh Aug 2 '19 at 7:11

I believe that the Stirling numbers of the second kind $$\big\{{n\atop k}\big\}$$ are what you need. This is the number of ways to partition $$n$$ labelled elements into $$k$$ unlabelled non-empty subsets.
EDIT: If we're trying to partition $$n$$ unlabelled elements into $$k$$ subsets, then the function we're actually looking to use is $$p_k(n)$$. According to Wikipedia, this function satisfies the recurrence relation $$p_k(n) = p_k(n-k) + p_{k-1}(n-1),$$ with initial conditions $$p_0(0) = 1$$ and $$p_k(n) = 0$$ if either of $$n$$ or $$k$$ is non-positive.