How many unique ways can I sum $k$ non-negative numbers to $N$?

851 Views Asked by At

I have a similar question but not exactly the same as this.

I'm trying to determine the number of unique multisets $S\in \mathbb{N}$ that exist when the members are required to sum to a number $N$. I'm using the word unique to mean that no two multisets are permutations of each other (i.e. $\{1,2,3,2\}$ and $\{3,2,2,1\}$ are both equivalent).

For example, when $n_1,n_2,n_3 \in \{0,1,2,3,4\}$ and $n_1 + n_2 + n_3 =6$, or $k=3$ and $N=6$, I need to determine the number of unique set $\{n_1,n_2,n_3\}$ which exist. In this case, I know from manually counting that there are 5 unique multisets: $\{0,2,4\}$, $\{1,1,4\}$, $\{1,2,3\}$, $\{0,3,3\}$ and $\{2,2,2\}$. Furthermore, based on the stars and bars method, I know there are $\binom{N+k-1}{N} = \binom{N+k-1}{k-1} = 28$ multisets in total.

My question is how can to go about calculating the unique multisets for any $k$ and $N$? Can I somehow use the formula for combinations with repetition?

1

There are 1 best solutions below

1
On

Supposing your constituent values are $0,1,2,\ldots,q$ the answer is given by the following Polya Enumeration formula: $$[z^N] Z(S_k)\left(\sum_{m=0}^q z^m\right).$$

In the example we have $k=3$ and $N=6$ so we obtain the generating function $$f(z) = [z^6] Z(S_3)\left(\sum_{m=0}^4 z^m\right).$$

Now $$Z(S_3) = 1/6\,{a_{{1}}}^{3}+1/2\,a_{{2}}a_{{1}}+1/3\,a_{{3}}$$ so the substituted cycleindex is $$1/6\, \left( {z}^{4}+{z}^{3}+{z}^{2}+z+1 \right) ^{3}\\+1/2\, \left( {z}^{8}+{z}^{6}+{z}^{4}+{z}^{2}+1 \right) \left( {z}^{4 }+{z}^{3}+{z}^{2}+z+1 \right)\\ +1/3\,{z}^{12}+1/3\,{z}^{9}+1/3\,{ z}^{6}+1/3\,{z}^{3}+1/3$$ and we see that indeed $$[z^6] f(z) = 5.$$

Remark. The total when any constitutent is admitted as opposed to a maximum value is given by the partition function. We obtain $$[z^N] Z(S_k)\left(\frac{1}{1-z}\right) = [z^{N+k}] Z(S_k)\left(\frac{z}{1-z}\right) .$$

Recall that $$\sum_{k\ge 0} Z(S_k) w^k = \exp\left(\sum_{q\ge 1} a_q \frac{w^q}{q}\right).$$

Hence we seek to compute $$[z^{N+k}] [w^k] \exp\left(\sum_{q\ge 1} \frac{z^q}{1-z^q} \frac{w^q}{q}\right).$$

The inner term is $$\sum_{q\ge 1} \sum_{p\ge 1} z^{pq} \frac{w^q}{q} = \sum_{p\ge 1} \sum_{q\ge 1} z^{pq} \frac{w^q}{q} = \sum_{p\ge 1} \log\frac{1}{1-wz^p}.$$

Therefore we are actually calculating $$[z^{N+k}] [w^k] \exp\sum_{p\ge 1} \log\frac{1}{1-wz^p} = [z^{N+k}] [w^k] \prod_{p\ge 1} \frac{1}{1-wz^p}$$ which is readily seen to be $$p_k(N+k).$$