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.
 A: 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).$$
A: 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.
A: 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.
A: 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.
A: This isn't a closed-form solution, but here is a straightforward recurrence that admits a slow $O(nk^2)$ dynamic programming solution in $O(k^2)$ space. Let $f_n(k,m)$ be the number of sorted solutions to $k_1 + \cdots + k_n = k$ with $k_1 \le \cdots \le k_n \le m$, then
$$f_n(k,m) = \sum_{k' = 0}^{\min(m,k)} f_{n-1}(k-k',k'-1)$$
Base case is $f_1(k,m) = [k \le m]$.
Since each integer is distinct, the number of solutions with any ordering is $n! f_n(k,k)$.
