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.
Best Answer
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.