Interpretation of the unsigned Stirling number of the first kind.

Question

Let $C_{2}, C_{3},\dots, C_{n}$ be the directed star graphs: the vertex set of $C_{j}$ is $\{1, 2, \dots, j\}$ and its edge set is $\{(j, i): 1\leq i <j\}$ . Let $c'(n,i)$ be the number of sets $X$ of $n-i$ edges from the stars $C_{2}, C_{3},\dots, C_{n}$ with no two edges in $X$ being in the same star. Show that $c'(n,i)$ is the unsigned Stirling number $c(n,i)$ of the first kind.

The unsigned Stirling number of the first kind corresponds to the number of permutations in the symmetric group $S_{n}$ with $k$-cycle.

Answer 1

Here’s a solution based on the recurrence for the unsigned Stirling numbers of the first kind instead of on generating functions.

I write ${n\brack k}$ for the unsigned Stirling number of the first kind that you denote by $c(n,k)$. The Stirling numbers of the first kind satisfy the recurrence

$${{n+1}\brack k}=n{n\brack k}+{n\brack{k-1}}$$

for $k>0$, with initial conditions ${0\brack 0}=1$ and ${n\brack 0}={0\brack n}=0$ for $n>0$. I claim that $c'(n,k)$ satisfies the same recurrence:

$$c'(n+1,k)=nc'(n,k)+c'(n,k-1)$$

for $k>0$. To see this, let $G_n$ be the disjoint union of the star graphs $C_2,\ldots,C_n$.

Note that what you defined are not the star graphs; the star graph $C_k$ has only the $k-1$ edges $\langle j,k\rangle$ for $1\le j<k$. I’m assuming that you’re supposed to have the star graphs, not the graphs that you described.

Let $\mathscr{E}(n,k)$ be the family of all sets $X$ of $n-k$ edges of $G_n$ such that $X$ contains at most one edge from each $C_i$, $i=2,\ldots,n$. Let

$$\mathscr{E}_0(n+1,k)=\{X\in\mathscr{E}(n+1,k):X\text{ contains an edge from }C_{n+1}\}\;,$$

and let $\mathscr{E}_1(n+1,k)=\mathscr{E}(n+1,k)\setminus\mathscr{E}_0(n+1,k)$; clearly

$$c'(n+1,k)=|\mathscr{E}(n+1,k)|=|\mathscr{E}_0(n+1,k)|+|\mathscr{E}_1(n+1,k)|\;.$$

It’s not hard to see that $\mathscr{E}_1(n+1,k)=\mathscr{E}(n,k-1)$: both contain precisely the sets $X$ of $(n+1)-k=n-(k-1)$ edges of $G_n$ with at most one edge from any $C_i$. Thus, $\mathscr{E}_1(n+1,k)=c'(n,k-1)$, and

$$c'(n+1,k)=|\mathscr{E}_0(n+1,k)|+c'(n,k-1)\;.$$

Finally, each $X\in\mathscr{E}(n,k)$ can be extended to $n$ different members of $\mathscr{E}_0(n+1,k)$ by adding one of the $n$ edges of $C_{n+1}$, and every member of $\mathscr{E}_0(n+1,k)$ arises uniquely in this way, so

$$|\mathscr{E}_0(n+1,k)|=n|\mathscr{E}(n,k)|=nc'(n,k)\;,$$

and hence

$$c'(n+1,k)=nc'(n,k)+c'(n,k-1)\;,$$

as desired.

The numbers $c'(n,k)$ are actually defined only for $n\ge 2$. Clearly

$$\begin{align*} &c'(2,0)=0={2\brack 0},c'(2,1)=1={2\brack 1}\;,\\ &c'(2,2)=1={2\brack 2},\text{ and }c'(2,k)=0={2\brack k}\text{ for }k\ge 3\;, \end{align*}$$

and it follows that $c'(n,k)={n\brack k}$ whenever $n\ge 2$.

In fact we could extend the function $c'(n,k)$ to allow $n=1$ and $n=0$. The graphs $G_0$ and $G_1$ are both empty, so $\mathscr{E}(0,0)=\{\varnothing\}$, $\mathscr{E}(1,1)=\{\varnothing\}$, $\mathscr{E}(1,0)=\varnothing$, and we have $c'(0,0)=c'(1,1)=1$ and $c'(1,0)=0$, agreeing with ${0\brack 0},{1\brack 1}$, and ${1\brack 0}$, respectively.

Answer 2

Supposing that we are really working with star graphs and not complete graphs this is indeed true and it follows by inspection from the OGF of the unsigned Stirling numbers of the first kind.

Assume that we want to select $n-q$ edges from the $n-1$ stars and that star one with label $C_2$ contains one edge, star two with label $C_3$ two edges and so on up to star $n$ with label $C_n$ and $n-1$ edges the answer is given by

$$[z^{n-q}] \prod_{p=1}^{n-1} (1+pz) = [z^{n-q}] z^{n-1} \prod_{p=1}^{n-1} (1/z+p) = [z^{n-1+1-q}] z^{n-1} \prod_{p=1}^{n-1} (1/z+p) \\ = [z^{-(q-1)}] \prod_{p=1}^{n-1} (1/z+p) \\ = [w^{q-1}] \prod_{p=1}^{n-1} (w+p) = [w^{q}] \prod_{p=0}^{n-1} (w+p) .$$

This is the OGF as announced and we may conclude with

$$\left[ n\atop q\right].$$