I am stuck with a combinatoric problem...

Question

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?

Answer 1

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.

Answer 2

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.