1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – marcelgoh Aug 2 '19 at 7:02
  • $\begingroup$ 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)$. $\endgroup$ – Yip Jung Hon Aug 2 '19 at 7:05
  • $\begingroup$ Ahh okay. I believe this is $p_k(n)$, the number of partitions of $n$ into exactly $k$ parts. I'll edit my answer. $\endgroup$ – marcelgoh Aug 2 '19 at 7:11
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks, I'll look that up. Also, I've added an edit with a follow up question regarding notation. If you have time, please check it out. Thanks! $\endgroup$ – Yip Jung Hon Aug 2 '19 at 6:49
  • $\begingroup$ I tried to address your follow-up question. The recurrence relation suggests a recursive algorithm to enumerate all such partitions, but I can't think of it on the spot. I hope this helps. $\endgroup$ – marcelgoh Aug 2 '19 at 7:18
  • $\begingroup$ Alright thank you! I'll check that out! $\endgroup$ – Yip Jung Hon Aug 2 '19 at 7:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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