# How solutions of distinct non-negative solutions are there to $k_1+\cdots+k_n=k$?

How many distinct $n$-tuples with distinct non-negative integer elements are there that add to $k$.

For example there are $6$ triples that add to $4$. Namely $(0, 1, 3)$ and its $6$ permutations. Is there a formula for this amount? I have tried very hard to do it but with no luck.

This question can also be rephrased as:

How many sets of non-negative solutions are there to $k_1+\cdots+k_n=k$ where $k_i\ne k_j$.

It is obvious that the smallest $k$ would be $\frac{n(n-1)}{2}$.

Another example would be

How many pairs of distinct non-negative integers are there that add to $6$? Clearly this is the number of compositions of length $2$ with distinct terms and $2!$ times the number of compositions of length $1$ with distinct terms (how to count the zeros). We get

$0+6$, $1+5$, $2+3$, $3+2$, $5+1$, $6+0$

So there are $6$ such pairs.

I should note that the answer may be given in terms of the partition function. Which gives how many ways can an integer be written as a sum of positive .integers.

By way of enrichment I would like to point out that using the Polya Enumeration Theorem the closed form is also given by

$$n! [z^k] Z(P_n)\left(\frac{1}{1-z}\right)$$

where $Z(P_n) = Z(A_n)-Z(S_n)$ is the difference between the cycle index of the alternating group and the cycle index of the symmetric group. This cycle index is known in species theory as the set operator $\mathfrak{P}_{=n}$ and the species equation here is

$$\mathfrak{P}_{=n}\left(\mathcal{E} + \mathcal{Z} + \mathcal{Z}^2 + \mathcal{Z^3} + \cdots\right).$$

Recall the recurrence by Lovasz for the cycle index $Z(P_n)$ of the set operator $\mathfrak{P}_{=n}$ on $n$ slots, which is $$Z(P_n) = \frac{1}{n} \sum_{l=1}^n (-1)^{l-1} a_l Z(P_{n-l}) \quad\text{where}\quad Z(P_0) = 1.$$ This recurrence lets us calculate the cycle index $Z(P_n)$ very easily.

For example when $n=3$ as in the introduction to the problem the cycle index is $$Z(P_3) = 1/6\,{a_{{1}}}^{3}-1/2\,a_{{2}}a_{{1}}+1/3\,a_{{3}}$$ and the generating function becomes $$1/6\, \left( 1-z \right) ^{-3}-1/2\,{\frac {1}{ \left( -{z}^{2}+1 \right) \left( 1-z \right) }}+1/3\, \left( -{z}^{3}+1 \right) ^ {-1}$$ which gives the sequence $$0, 0, 6, 6, 12, 18, 24, 30, 42, 48, 60, 72, 84, 96,\ldots$$ which is six times OEIS A069905.

Similarly when $n=5$ we get the cycle index $$Z(P_5) = {\frac {{a_{{1}}}^{5}}{120}}-1/12\,a_{{2}}{a_{{1}}}^{3}+1/6\,a_{{ 3}}{a_{{1}}}^{2}+1/8\,a_{{1}}{a_{{2}}}^{2}\\-1/4\,a_{{4}}a_{{1}}-1/ 6\,a_{{2}}a_{{3}}+1/5\,a_{{5}}$$ and the generating function becomes $${\frac {1}{120\, \left( 1-z \right) ^{5}}}-1/12\,{\frac {1}{ \left( -{z}^{2}+1 \right) \left( 1-z \right) ^{3}}}\\+1/6\,{ \frac {1}{ \left( -{z}^{3}+1 \right) \left( 1-z \right) ^{2}}}+1 /8\,{\frac {1}{ \left( -{z}^{2}+1 \right) ^{2} \left( 1-z \right) }}-1/4\,{\frac {1}{ \left( -{z}^{4}+1 \right) \left( 1- z \right) }}\\-1/6\,{\frac {1}{ \left( -{z}^{2}+1 \right) \left( - {z}^{3}+1 \right) }}+1/5\, \left( -{z}^{5}+1 \right) ^{-1}$$ which gives the sequence $$0, 0, 0, 0, 0, 0, 0, 0, 0, 120, 120, 240, 360, 600, \ldots$$ which is $120$ times OEIS A001401.

The prefix of zeroes (these two examples start at one) compared to the two OEIS entries represents the fact that the minimum value attainable with $n$ distinct summands in $$[z^k] Z(P_n)\left(\frac{1}{1-z}\right)$$ is $0+1+2+\cdots+n-1 = 1/2\times n\times (n-1).$

These sequences match the formula by @bof, which is $$n! p_n\left(k - \frac{1}{2} n (n - 3)\right).$$

There are many more related links at MSE Meta on Burnside/Polya.

The Maple code for these was as follows.

p :=
proc(n, k)
option remember;

if k=1 then return 1 fi;
if n<k then return 0 fi;

p(n-1, k-1)+p(n-k,k)
end;

pet_cycleind_symm :=
proc(n)
local p, s;
option remember;

if n=0 then return 1; fi;

end;

pet_cycleind_set :=
proc(n)
local p, s;
option remember;

if n=0 then return 1; fi;

a[l]*pet_cycleind_set(n-l), l=1..n));
end;

pet_varinto_cind :=
proc(poly, ind)
local subs1, subs2, polyvars, indvars, v, pot, res;

res := ind;

polyvars := indets(poly);
indvars := indets(ind);

for v in indvars do
pot := op(1, v);

subs1 :=
[seq(polyvars[k]=polyvars[k]^pot,
k=1..nops(polyvars))];

subs2 := [v=subs(subs1, poly)];

res := subs(subs2, res);
od;

res;
end;

q1 :=
proc(n, k)
option remember;
local gf;

gf := pet_varinto_cind(1/(1-z), pet_cycleind_set(n));
n!*coeftayl(gf, z=0, k);
end;

q2 :=
proc(n, k)
option remember;
n!*p(k-n*(n-3)/2, n);
end;


Addendum. As per request we now give a mixed (combinatorial, algebraic) proof of the identity $$[z^n] Z(P_k)\left(\frac{1}{1-z}\right) = p_k\left(n - \frac{1}{2} k(k-3)\right).$$

Observe that we have reverted to the standard convention of using $n$ for the sum of the partition and $k$ for the number of parts.

By the same construction as before (PET) we have $$p_k\left(n - \frac{1}{2} k(k-3)\right) = [z^{n- \frac{1}{2} k(k-3)}] Z(S_k)\left(\frac{z}{1-z}\right)$$ with $Z(S_k)$ being the cycle index of the symmetric group (unlabelled multisets with operator $\mathfrak{M}_{=k}$.)

Using basic algebra this becomes $$[z^{n- \frac{1}{2} k(k-3)}] z^k Z(S_k)\left(\frac{1}{1-z}\right) = [z^{n- \frac{1}{2} k(k-3) -\frac{1}{2} 2k}] Z(S_k)\left(\frac{1}{1-z}\right) \\ = [z^{n- \frac{1}{2} k(k-1)}] Z(S_k)\left(\frac{1}{1-z}\right).$$

But this is the species $$\mathfrak{M}_{=k}\left(\mathcal{E} + \mathcal{Z} + \mathcal{Z}^2 + \mathcal{Z^3} + \cdots\right),$$ i.e. partitions with empty constitutents being permitted and constituents not necessarily distinct.

There is however a straighforward bijection between these and partitions with potentially empty but distinct constituents. To go from the former to the latter add $q$ circles on the left of every row in the Ferrers diagram with row indices $q$ starting at zero. Now if we had two adjacent rows with the first above the second with length $b_1$ and $a_1$ where $b_1\ge a_1$ then the resulting pair is $b_1+q$ and $a_1+q-1.$ The difference between these is $b_1-a_1+1\ge 1$ so the new pair is distinct and in non-decreasing order seen from below. To go from the latter to the former remove $q$ circles from every row (index is $q$), turning $b_2$ and $a_2$ where $b_2>a_2$ into $b_2-q$ and $a_2 -(q-1).$ The difference is $b_2-a_2-1\ge 0$ and the pair is non-decreasing order but not necessarily distinct. The number of circles being added/removed is
$$\sum_{q=0}^{k-1} q = \frac{1}{2} k(k-1).$$

We have shown that $$[z^{n- \frac{1}{2} k(k-1)}] Z(S_k)\left(\frac{1}{1-z}\right) = [z^n] Z(P_k)\left(\frac{1}{1-z}\right).$$ Here we have $n\ge \frac{1}{2} k (k-1),$ both sides are zero otherwise. This concludes the argument.

• Hi! Your answer is an enrichment. Thanks for the nice link into MSE Meta. +1 – Markus Scheuer Nov 5 '14 at 9:17
• The sequences match but does there exist a derivation? – Ali Caglayan Nov 6 '14 at 22:14
• @Alizter Please find the requested proof in the addendum above. – Marko Riedel Nov 7 '14 at 2:02
• Marko thank you for your answer. I have left the question unaccepted in order not to discourage any further contribution. Enjoy your bounty. – Ali Caglayan Nov 8 '14 at 20:47
• Another request. Could you add the generating function for the closed form as well? – Ali Caglayan Nov 12 '14 at 20:27

This is really just a commentary on yashg's (now deleted) answer; I just want to provide a bit of context and a reference.

To save repetition: all variables in this post are restricted to integers.

The title of the question is somewhat confusing: the vector $(0,1,3)$ is a solution, not a "set of solutions", of the multivariable equation $k_1+k_2+k_3=4$. You are asking for the number of solutions of the equation $k_1+\cdots+k_n=k$ where $k_1,\dots,k_n$ are distinct nonnegative integers. By the way, I believe it's usual in the literature (at least, in the Wikipedia reference I'm about to give) to interchange the roles of $k$ and $n$ in such problems.

The answer is in terms of the much-studied partition function $p_k(n)$ which is defined as the number of solutions of the equation $x_1+\cdots+x_k=n$ where $x_1\ge x_2\ge\cdots\ge x_k\ge1$; those solutions are called the partitions of $n$ into (exactly) $k$ parts. For fixed $k$, the generating function is $$\sum_{k=0}^\infty p_k(n)x^n=\frac{x^k}{(1-x)(1-x^2)\cdots(1-x^k)}.$$ For $n\ge k\gt1$ we have the recurrence equation $$p_k(n)=p_{k-1}(n-1)+p_k(n-k),$$ since $p_{k-1}(n-1)$ is the number of partitions of $n$ into $k$ parts with smallest part equal to $1$, while $p_k(n-k)$ is the number of partitions of $n$ into $k$ parts $\ge2$. Using the recurrence equation and the obvious boundary conditions $p_k(n)=0$ for $n\lt k$ and $p_1(n)=1$ for $n\gt0$, we can calculate values of $p(n,k)$, and derive closed formulas for fixed $k$, e.g., $p_2(n)=\lfloor\frac n2\rfloor$, $p_3(n)=\lfloor\frac{n^2+3}{12}\rfloor$, etc.

Next, the transformation $y_j=x_j+1-k+j$ shows that the number of solutions of the equation $x_1+\cdots+x_k=n$ with $x_1\gt x_2\gt\cdots\gt x_k\ge0$ is the same as the number of solutions of $y_1+\cdots+y_k=n-\frac{k(k-3)}2$ with $y_1\ge y_2\ge\cdots\ge y_k\ge1$, that is, $p_k(n-\frac{k(k-3)}2)$.

Since your question allows the summands to be arranged in any order, and since they are all distinct, the number of solutions of $x_1+\cdots+x_k=n$ where $x_1,\dots,x_k$ are distinct nonnegative integers is $k!\,p_k(n-\frac{k(k-3)}2)$; or in your notation:

The number of solutions of $k_1+\cdots+k_n=k$ where $k_1,\dots,k_n$ are distinct nonnegative integers is $$n!\,p_n(k-\frac{n(n-3)}2).$$

• (+1) Please find an independent verification of your formula by Polya counting below. – Marko Riedel Nov 4 '14 at 21:47

I believe I've found a solution, but it's up to you all to check its correctness. Here it goes:

We have to find the number of non-negative integral solutions to :$$k_1+k_2+....+k_n=P$$ where $k_i\in \{ 0,1,2,3,.....\}$ , $P\in\{1,2,3,4,....\}$ and $k_i\ne k_j$

Since all the numbers in LHS are distinct, we can assume for simplicity that $k_i<k_{i+1}$

With this assumption, let:$$k_1=k_1+0$$$$k_2=k_1+a_1$$$$.$$$$.$$$$.$$$$k_n=k_{n-1}+a_{n-1}$$ where $a_i\in \{ 1,2,3,.....\}$

Then,$$k_1+k_2+...+k_n=k_1+(k_1+a_1)+(k_1+a_1+a_2)+...+(k_1+a_1+...a_{n-1})$$ $$k_1+k_2+...+k_n=nk_1+(n-1)a_1+(n-2)a_2+...+2a_{n-2}+a_{n-1}$$ So we got to find the solutions to$$nk_1+(n-1)a_1+(n-2)a_2+...+2a_{n-2}+a_{n-1}=P$$ Since I don't know how to deal with natural numbers, I rewrite the equation as$$nk_1+(n-1)b_1+(n-2)b_2+...+2b_{n-2}+b_{n-1}=P-\binom{n}{2}$$ where $b_i\in \{0,1,2,3,.....\}$

Now very easily we can write the multinomial in which we will have the coefficient of $x^{P-\binom{n}{2}}$ as the number of solution sets. Which we can multiply by $n!$ to get the desired number of tuples. I give the final answer as $C$ multiplied by $n!$ , where $C$ is the coefficient of $x^{P-\binom{n}{2}}$ in the expansion of $$(1+x^n+x^{2n}+...+x^{n\lfloor\frac{P-\binom{n}{2}}{n}\rfloor})(1+x^{n-1}+x^{2n-2}+...+x^{(n-1)\lfloor\frac{P-\binom{n}{2}}{n-1}\rfloor}).....(1+x+x^2+....+x^{P-\binom{n}{2}})$$ NOTE: If it's not visible, the power of $x$ in the last terms of the brackets has a floor function. If it's still not clear, it's ${n\lfloor\frac{P-\binom{n}{2}}{n}\rfloor}$ in the first bracket, and then you just keep on decreasing n by 1 in the subsequent brackets.

## CHECKING THE FORMULA

First, let's take your first case where $n=3$ and $P=4$. The expression will be $(x^0)(x^0)(x^0)$ in which the coefficient of $x^0$ is 1. Which we multiply by 3! to get the answer 6.

Now let's take your second case where $n=2$ and $P=6$. The expression will be $(1+x^2+x^4)(1+x+x^2+x^3+x^4+x^5)$ in which the coefficient of $x^5$ is 3. Which we multiply by 2! to get 6.

It is not my area of expertise, but I believe that what you are after are called in the literature compositions of $k$ into $n$ distinct parts.

You can probably find the answer in the following 1995 paper by B.Richmond and A.Knopfmacher "Compositions with distinct parts" (link), to which I unfortunately have no access.

The generating function for the number of composition of $k$ into $n$ distinct parts is also given at the very end of the following preprint and a close formula could possibly be derived from it.

If $k_i$ are not distinct then the total ways are: $$\sum_{i}^nk_i=k,k_i\ge0\longrightarrow \binom{k+n-1}{n-1}$$ Now we need to use inclusion-exclusion to remove cases where any two or more $k_i$'s are equal, note that you need to be more careful while using inclusion-exclusion because when taking for example $k_1$ and $k_2$ equal there may be the case that $k_3=k_4,k_1\ne k_3$, not even that for it may be that at the same time groups of 2,3 and 4 elements are equal and this may require much work which I skip here.