Why $S(n,k)$ is the coefficient of $x^{n-k}$ in $\prod_{t=0}^{k}(1+tx+t^2x^2+\cdots+t^nx^n)$? $S(n,k)$ is the Stirling number of the second kind. I think an algebraic proof has something to do with the generating function.
But I'm more interested in combinatorial proof. Could you please give a combinatorial proof?
Thanks!
 A: First of all, title has a typo: $S(n,k)$ is the coefficient of $x^{n-k}$ in $\prod_{t=0}^{k}(1+tx+t^2x^2+\cdots+t^{n-1}x^{n-1})$, and $t=0$ part contributes nothing to the product.
Note that the coefficient is $\sum 1^{a_1-1}2^{a_2-1}\cdots k^{a_k-1}$ where the sum is over all compositions $a_1+\cdots + a_k=n$. Then you may follow the argument here.
A: $S(n,k)={n\brace k}$ is the number of partitions of the set $\{1,2,\ldots,n\}$ into $k$ non-empty subsets, i.e. $\frac{1}{k!}$ times the number of surjective functions from $\{1,\ldots,n\}$ to $\{1,\ldots,k\}$. We have to show that this number equals
$$ \sum_{a_1+\ldots+a_k=n} 1^{a_1-1}\cdot 2^{a_2-1}\cdot\ldots\cdot k^{a_k-1},$$
or, equivalently, we have to show that:
$$ \sum_{n\geq 0}{n \brace k}x^n = \frac{x^k}{(1-x)(1-2x)\cdot\ldots\cdot(1-kx)}. \tag{1}$$
That can be easily done by induction on $k$. We have:
$$ {n\brace k+1} = {n-1\brace k}+k{n-1\brace k+1} $$
hence, if we define $f_k(x)$ as $\sum_{n\geq 0}{n \brace k}x^n$, we have:
$$ (1-(k+1)x)\cdot f_{k+1}(x) = x\cdot f_k(x) $$
and $(1)$ easily follows.
