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;

        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.

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