Combinatorics – Combinatorial Proof for Stirling Number of the First Kind

combinatorial-proofscombinatoricspermutation-cyclespermutationsstirling-numbers

This question is duplicate. But I have some questions about the already posted answers. And temporarily I don't have enough reputation to comment, so I post one new question. Sorry for that.

This one may need some knowledge with group which I currently haven't learnt.

  1. For $n(n+1)…(n+k-1)=\sum_{j=0}^k \begin{bmatrix}k \\j \end{bmatrix}n^j$, I followed answer_1.

    Both sides are counted by the number of ways to place $k$ distinct flags on $n$ distinct flagpoles, where the order in which several flags are stacked matters.

    Left Hand Side

    The first flag can be placed on any of $n$ poles. The second can be placed on the bottom of any pole, or on top of the first, for $n+1$ options. Continuing, the $i^{th}$ flag can be placed in any of $n+i-1$ places, either on the bottom of any pole, or just above any of the $i-1$ previously placed flags. Therefore, the number of possibilities is $\prod_{i=1}^n(n+i-1)$.

    Right Hand Side

    …

    For example, say $n=9$ and $k=3$. We choose $j=4$, and choose the permutation
    $$\pi=(5\,9)(3\, 4)(2)(1\, 8\, 6\, 7).$$
    We then choose to put the (5 9) on the left pole, (3 4) on the right pole, (2) on the right pole, and (1 8 6 7) on the right pole, resulting in

       |   |   7
   |   |   6
   |   |   8
   |   |   1
   |   |   2
   9   |   4
   5   |   3

    For the above offered example, I thought it first choose $4$ cycles (although the above may be mistaken to let $k=3<j$), so $\begin{bmatrix}k \\4 \end{bmatrix}$. Then it assigns one of $n$ poles to each cycle, so $n^j$. Then based on the product rule, we have the factor $\begin{bmatrix}k \\4 \end{bmatrix} n^j$.

    But the cycle order implies $(1\, 8\, 6\, 7)$ is same as $(8\, 6\, 7\, 1)$ while it is not this case in the Left Hand Side. Then how does the two sides become same?

  2. For generalized version for real number $x$, $(x)_n \equiv x(x-1)\cdots (x-(n-1)) = \sum_{k=0}^n s(n,k) x^k$.

    This one unluckily lost its link.

    • Then I tried this answer_2.

      Imagine the process of expanding this product from the left. We record which summand (from the left) we choose on the $k$th term $\left(x+\underset{n-k\text{ times}}{\underbrace{1+\dots+1}}\right)$. Say that you chose the $i_k$th summand from the $k$th term. We define a sequence $j_1,\dots,j_n$ by
      $$j_{k+1}=i_{k+1}\text{th smallest element in }\{1,\dots,n\}\setminus\{j_1,\dots,j_{k}\}.$$
      The sequence $j_1\dots j_{n}$ is a reordering of $1,\dots ,n$. Now for each $k$ such that $i_k=1,$ put a slash "/" between $j_{k}$ and $j_{k+1}.$ This means that if you chose $i$ $x$'s, then you have $i$ slashes. The resulting sequence looks like
      $$j_1\dots j_{k_{1}}/j_{k_1+1}\dots j_{k_2}/\dots/j_{k_{i}+1}\dots j_{n},$$
      and we can regard this sequence as a permutation which is the product of $i$ cycles.

      The above construction of $j_i$ is a bit complex. I was still stuck with the cycle order. Why can $j_1\dots j_{k_{1}}$ be thought same as $j_{k_{1}} j_1 j_2 \dots j_{k_{1}-1}$. Since this cyclic reorder is dependent on $i_k$ and each $j_i$ is dependent on $j_t,t<i$, it seems to be nontrivial to show this cyclic reorder doesn't influence the result.

    • I also tried answer_3 which is similar to answer_1.

      On the other hand, consider the following method of choosing a permutation, $\pi$. You first choose $\pi(1)$, from one of $n$ options. Then, you choose $\pi(\pi(1))$, then $\pi(\pi(\pi(1)))$, and so on until you complete a cycle. Then, you choose $\pi(s)$, where $s$ is the smallest unassigned element, etc. During the $k^{th}$ stage of this process, you have $n-k+1$ options. Exactly one of these leads to the creation of a cycle.
      After some thought, these processes are exactly the same, so that the number of ways to choose a permutation with $k$ cycles is the coefficient of $x^k$ in the expansion of $x^{\overline n}$.

      What does $\pi(1)$ mean? If it means that we choose the $\pi(1)$th item in the 1st factor $x+n-1$, then the cycle $\pi(\pi(\ldots\pi(s))),s\neq 1$ will not choose the 1st item $x$ of each factor in the permutation process. Then how does the above whole process imply "the coefficient of $x^k$"?

Q:

The above shows the somewhat hard tries by me to understand the relation between cycle implied by the Stirling number of 1st kind and the rising factorial. Could someone help with one of the above questions or offer one easier explanation? Thanks beforehand.

Edit:

During my spare time, I rethought about the above tried answers based on the following transcribed Brian M. Scott's answer and understood them. Thanks very much.

  1. answer_1 which is based on two counting methods of one same object:

    This one is very similar to the following transcribed Brian M. Scott's answer because they both includes 2 steps where one is for $\begin{bmatrix}k \\j \end{bmatrix}$ and one is for $n^j$.

    After thinking about the canonical cycle representation (uniquely defining the product of cycles) which corresponds to the step 2 of RHS and

    because each one begins with a number that is smaller than all numbers below it

    .Then the above $(8\, 6\, 7\, 1)$ is impossible here (sorry for making such a low-level error in the above). It should be $(8)(6\, 7)(1)$.

  2. answer_2

    • It "contains exactly the same information" as answer_3 which is said by the answer_2's author. Here I explains how they are same which is not understood when I read it without understanding Brian M. Scott's answer.

      Here each cycle $j_{k_i+1}\dots j_{k_{i+1}}$ implies ending with the smallest (similar to canonical cycle representation which starts with the largest) element in $\{1,\dots,n\}\setminus\{j_1,\dots,j_{k_1},\dots,j_{k_2},\dots,j_{k_i}\}$ since $i_{k_{i+1}}=1$. So it is impossible for something like $j_{k_{1}} j_1 j_2 \dots j_{k_{1}-1}$ to occur which implies it can be thought as one cycle.

      Also $j_{k_1}<j_{k_2}<\ldots<j_{k_i},i\ge 2$ which is also similar to canonical cycle representation.

      Then its process is something like:

      1. Rearrange $j_1,\dots,j_{k_1}$ corresponding the original increasing sub-sequence like $1,\ldots,m_{k_1}$ so that $j_{k_1}=1$. This corresponds to $\pi(\pi(\pi(\dots\pi(1))))=1$

      2. Rearrange $j_{k_1+1}\dots j_{k_2}$ corresponding the original increasing sub-sequence like $s,\ldots,m_{k_2}$ so that $j_{k_2}=s$. This corresponds to $\pi(\pi(\pi(\dots\pi(s))))=s$. This is due to the choice of $s$:

        Then, you choose $\pi(s)$, where $s$ is the smallest unassigned element, etc.

        .The rest is similar.

      Then the example offered by answer_2 means that $\pi(1)=3,\pi(\pi(1))=1;\pi(2)=4,\pi(\pi(2))=2$.

    • Based on the canonical cycle representation, it is similar to answer_1.

  3. answer_3 which is based on two counting methods of one same object where the construction of one cycle corresponds to one choice of $x$ among $x+1+\dots+1$:

    Exactly one of these leads to the creation of a cycle.

    It corresponds to that exactly one of $(x+1+\dots+1)$ contributes to $x$ factor in $x^k$.

    So if $s\neq 1$ is the start of one cycle, then $\pi(\pi(\pi(\dots\pi(s))))=s$ (here we use the product/composition operation) means that it chooses one $x$ factor because only $s$ among all available choices at each permutation step can cause the construction of the cycle although $s\neq 1$.

    More specifically, here $\pi(s)$ doesn't choose among $x+1+\dots+1$. It chooses among left unchosen elements among $\{1,2,\dots,n\}$

    The above is mostly same as the original answer_3 author says. But I add some emphasizes related with my questions above.

Best Answer

You mentioned that there was an answer which lost its link. Actually, the question and answer still exist, but only users with a high enough reputation can view them. Since it may be helpful to you, I have transcribed the deleted question and answer below.

Question (user801358)

Using combinatorics to show that $$x^{\overline n}=\sum_{k=0}^{n}{n\brack k}x^k$$

Where $x^{\overline n}$ is defined as $\prod_{i=0}^{n-1}\left(x+i\right)$ and ${ n\brack k}$ denotes Stirling numbers of the first kind.

The left-hand side counts the number of injections from $[n]$ to $[x+n-1]$, however, I don't know what the right-hand side does count and why these two are the same.

I know that $\sum_{k=0}^{n}{ n\brack k}=\left|S_n\right|$,but I don't know if that helps.( $S_n$ is the symmetric group on $[n]$)

Answer (Brian M. Scott)

Because both sides are polynomials in $x$, it suffices to prove the identity for positive integers $x$: the polynomials are of degree $n$, so if they agree at more than $n$ values of $x$, they must be identical. Fix $m\in\Bbb Z^+$.

Suppose that $1\le k\le n$, and let $S_n(k)$ be the set of permutations of $[n]$ with $k$ cycles. For each $\pi=\sigma_1\ldots\sigma_k\in S_n(k)$ and $\langle\ell_1,\ldots,\ell_k\rangle\in[m]^k$, give each element of the cycle $\sigma_i$ the label $\ell_i$ for $i=1,\ldots,k$; this produces

$$\left|S_n(k)\times[m]^k\right|={n\brack k}m^k$$

labelled permutations. Summing over $k$ yields the number of permutations of $[n]$ whose elements are labelled with members of some subset of $[m]$ in such a way that all of the elements in any cycle have the same label.

We can also count those labelled permutations as follows. Let $\tau$ be any sequence of length $n+m-1$ whose elements are the integers in $[n]$ and $m-1$ identical markers; a straightforward stars-and-bars argument shows that there are $n!\binom{n+m-1}n$ such sequences. I claim that there is a bijection between these sequences and the labelled permutations of the previous paragraph. Let $\pi$ be the permutation of $[n]$ obtained by deleting the markers from $\tau$. The markers divide $\pi$ into $m$ segments, any of which can be empty. If $\rho=\langle r_1,\ldots,r_k\rangle$ is a non-empty segments, we can regard it as the canonical cycle representation of a permutation of $\{r_1,\ldots,r_k\}$. Let $\pi'$ be the product of the cycles derived in this way from the non-empty segments. Finally, if $\sigma$ is one of the cycles of $\pi'$, and $\sigma$ was derived from the $i$-th segment, empty or non-empty, of $\tau$, we give every element of $\pi'$ the label $i$. Clearly $\pi'$ is one of the labelled permutations of the previous paragraph, and it’s not hard to see that every one of those labelled permutations can be produced in this way. It follows that

$$m^{\overline{n}}=n!\binom{n+m-1}n=\sum_{k=0}^n{n\brack k}m^k$$

for all $m\in\Bbb Z^+$ and hence that

$$x^{\overline{n}}=\sum_{k=0}^n{n\brack k}x^k.$$

Related Question