Let $s\left(n,k\right)$ be the Stirling numbers of the first kind. Prove that \begin{align} \left(x\right)_n = \sum_{k=0}^n s\left(n,k\right) x^k , \end{align} where \begin{align} \left(x\right)_n = x\left(x-1\right)\left(x-2\right)\cdots\left(x-n+1\right) . \end{align}
I can prove this identity using induction but i was looking for a combinatorial proof for this identity regarding stirling numbers of first kind. How should i proceed?
On
Although this was asked a while ago, it might be worth recording a proof here as an illustration of a more general principle, namely Burnside's lemma.
As done in Phicar's proof, we will instead prove the equivalent identity for unsigned Stirling number of the first kind $c(n, k)$ and in fact show that, the identity is simply a particular case of Burnside's lemma.
We will prove that $$\binom{x+n-1}{n} = \dfrac{1}{n!}\sum_{k=0}^{n}c(n, k)x^{k}$$
The symmetric group $S_{n}$ acts on the set of functions $X = \{f: [n] \to [x]\}$ by pre-composition with the inverse. That is, $(\sigma, f) \mapsto f\circ\sigma^{-1}$ defines a valid group action, which then allows us to use Burnside's orbit-counting lemma, which we recall below.
Burnside's lemma: Let $G$ be a finite group acting on a set $X$, let $X / G$ denote the set of orbits under this action and let $X^{g} = \{x \in X: g.x = x\}$ denote the set of fixed points of $g.$ Then these objects are related by: $$|X / G| = \dfrac{1}{|G|}\sum_{g \in G}|X^{g}| $$
Returning to our set-up, each orbit of $X$ is of the form $\{f\circ \sigma: \sigma \in S_{n}\}.$ Suppose the range of $f$ is a multiset $S$ of size $n$ chosen from $[x].$ Note that for any $\sigma$, the range of $f \circ \sigma^{-1}$ is also $S.$ Hence each orbit is uniquely characterised by a choice of multiset of size $n$ from $[x]$ of which there are $\binom{x+n-1}{n}$ many, by the usual stars-and-bars argument. Thus the LHS in Burnside's lemma is $\binom{x+n-1}{n}.$
Now, given $\sigma \in S_{n}$, $X^{\sigma} = \{f \in X: f\circ \sigma = f\}.$ Note that $f \circ \sigma = f \iff f$ is constant on each cycle of $\sigma.$ Such functions $f$ are then completely determined only by the $n(\sigma)$ different values it takes, where $n(\sigma)$ is number of cycles of $\sigma$. There are $x^{n(\sigma)}$ functions like this and rewriting the sum on the RHS of Burnside's lemma and noting that there are $c(n, k)$ permutations with $k$ distinct cycles, we are done.
On
Here is a combinatorial proof that does not require any knowledge of groups. Let ${n \brack k}=(-1)^{n-k}s(n,k)$. The Stirling number ${n \brack k}$ may be interpreted as the number of ways to seat $n$ people at $k$ identical round tables where two arrangements are considered the same if each person has the same left neighbor in both arrangements. The coefficient of $x^k$ in the product $x(x+1)\cdots (x+n-1)$ is a sum of products. Each of these products counts the number of seatings of $n$ people at $k$ tables under certain constraints.
An example will serve to illustrate the general case. Suppose $n=8$ and $k=3$. Consider the number of seatings of 8 `people', say $0,1,\ldots,7$, at 3 tables such that the minimum numbers at each of the tables are $0,3$ and $6$ respectively. First seat $0,3,6$ at different tables. Now succesively seat the other numbers $1,2,4,5,7$.
$1$ can only be seated at the table with $0$: 1 way.
$2$ can only be seated at the table with $0$: 2 ways.
$4$ can be seated at the table with $0$ in 3 ways or the table with $3$ in one way: 4 ways.
$5$ can be seated at the table with $0$ or at the table with $3$: 5 ways.
$7$ can be seated at any of the three tables: 7 ways.
Note that, at each stage, the number of ways to seat the number $i$ is exactly $i$ for each $i\in \{1,2,4,5,7\}$. Thus the total number of seatings corresponding to the minimum values $\{0,3,6\}$ is precisely the product of elements in $\{1,2, 4, 5, 7\}$. This idea can be generalized to show that, given $n,k$ and a subset $S\subseteq \{0,1,\ldots,n-1\}$ of size $k$, the number of seatings of $\{0,\ldots,n-1\}$ in which the minimum elements at the tables are given by the subset $S$ is the product of those $n-k$ elements in $\{0,1,\ldots,n-1\}$ that are not in $S$. Summing up all such products as $S$ varies over $k$-element subsets, we find that the Stirling number ${n \brack k}$ is the coefficient of $x^k$ in the product $$x(x+1)\cdots (x+n-1).$$
That is equivalent to prove $x^\overline{n}=x(x+1)\ldots (x+n-1)=\sum |s(n,k)|x^k$, taking x=-y, and remembering $|s(n,k)|=(-1)^{n+k}s(n,k)$.
So, recall $|s(n,k)|=|\{\pi \in S_n:\pi = (a_{1,1}\ldots a_{1,b_1})_1\ldots (a_{k,1}\ldots a_{k,b_k})_k\}|$, the permutations of $S_n$ with exactly $k$ disjoint cycles. Also, recall that $x^k$ is the numbers of different functions from $[k]=\{1,2,\ldots ,k\}$ to $[x]=\{1,2,\ldots ,x\}$, and $x^\overline{n}$ is the numbers of different inyective functions from $[n]$ to $[x+n-1]$. So, you must find a factorization of an inyective function into a surjective function with some cyclic order ($\pi \in s(n,k)$) and a regular function $f\in [x]^{\left [k\right ]}$. So, i suppose that the representative elements of each cycle must go to the elements in $[x]$ and, as at least there is one cycle, the remaining elements (at most $n-1$) must go in some way to the elements $\{x+1,x+2,\ldots , x+n-1\}$.
Hope it helps.