I am stuck with a combinatoric problem... Well, I have to solve
$T_{n,k} =\sum_{i=0}^{n-k}{{n-k}\choose{i}}T_{n-1,k-1+i}$ where $T_{0,0}=1$, $T_{n,0}=0$ for $n>0$
Can anyone help?
 A: Suppose we have the recurrence
$$T_{n,k} = \sum_{q=0}^{n-k} {n-k\choose q} T_{n-1, k-1+q}$$
where $T_{0,0} = 1$ and $T_{n,0} = 0$ for $n\gt 0.$
Put $S_{n, k} = T_{n, n-k}$ to obtain
$$S_{n,k} = \sum_{q=0}^{k} {k\choose q} S_{n-1, k-q}
= \sum_{q=0}^{k} {k\choose q} S_{n-1, q}.$$
where we now have $S_{n,n} = 0$ unless $n=0$ when we get the value $1.$
Following  the conjecture  $$S_{n, k}  = (n-k)  n^{k-1}$$ by  Marc Van
Leeuwen we prove  this by induction on $n$ with  base case $n=1.$ Note
that when $k=0$ the recurrence  unrolls to $S_{n,0}= S_{n-1,0} =\cdots
= S_{0,0} =1$  as pointed out in the comments.   This is indeed $(n-0)
n^{-1} = 1$ so we may assume that $k\ge 1$ in the induction.
We have for $n=1$ as the base  case that $S_{1,0} = 1$ which agrees as
just observed and $S_{1,1} = 0$ by definition which agrees as well.
For the induction step we need to evaluate
$$\sum_{q=0}^{k} {k\choose q} S_{n-1, q}
= \sum_{q=0}^{k} {k\choose q} (n-1-q) (n-1)^{q-1}
\\ = \sum_{q=0}^{k} {k\choose q}  (n-1)^{q}
- \sum_{q=0}^{k} {k\choose q} q (n-1)^{q-1}
\\ = \sum_{q=0}^{k} {k\choose q}  (n-1)^{q}
- k \sum_{q=1}^{k} {k-1\choose q-1} (n-1)^{q-1}
\\ = n^k - k \sum_{q=0}^{k-1} {k-1\choose q} (n-1)^{q}
= n^k - k n^{k-1} = (n-k) n^{k-1}.$$
This is the claim.
A: Partial answer: experimental evidence suggests $T_{n,k}=kn^{n-k-1}$ (note that for $k=n$ this is $n/n=1$).
The next challenge is to understand where those powers of $n$ come from in the recurrence. This has the distinct smell of trees and forests.
So here is a combinatorial interpretation of $T_{n,k}$: it is the number of planted forests (disjoint union of trees, with a specified root node for each tree) on a labelled set of $n$ vertices, with a specified $k$-subset to be the set of roots. This interpretation is inspired by proposition 5.3.2 of R. P. Stanley's Enumerative Combinatorics (vol 2), which says that this number equals $kn^{n-k-1}$.
Here is why those combinatorial numbers satisfy the given recurrence. For $n=0$ one can of course only have the empty forest (with $k=0$), matching $T_{0,k}=\delta_{0,k}$. For $n>1$ we need at least one tree (so one root) whence $T_{n,0}=0$. Now assume the vertices are labelled by the set $[n]$ of the first $n$ natural numbers, and that the last $k>1$ of them are to be the roots (it clearly does not matter which $k$ labels are singled out to be the roots). For the final node, a root, choose a subset of the non-root nodes, which will be the set of its descendants. This subset has $i$ nodes with $0\leq i\leq n-k$. Now recursively choose a planted forest on the set $[n-1]$, with as root the remaining $k-1$ original root nodes together with the $i$ chosen (future) descendants. The number of possibilities is $\sum_{i=0}^{n-k}\binom{n-k}iT_{n-1,k-1+i}$, our given recurrence.
For a proof of the fact that now $T_{n,k}=kn^{n-k-1}$, I refer to the mentioned proposition; Stanley gives two proofs, one using Prüfer codes for planted forests and another using a bijection based on two views of permutations. Maybe I'll come back later to paraphrase either or both proofs.
