14
$\begingroup$

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.

$\endgroup$
11
+100
$\begingroup$

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;

        expand(1/n*add(a[l]*pet_cycleind_symm(n-l), l=1..n));
end;



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

        if n=0 then return 1; fi;

        expand(1/n*add((-1)^(l-1)*
        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.

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

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).$$

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

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

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.