A Note on the Generating Function for the Stirling Numbers of the First Kind

Ricky X. F. Chen Department of Mathematics and Computer Science University of Southern Denmark Campusvej 55 DK-5230, Odense M Denmark

                   chen.ricky1982@gmail.com

Abstract

In this short note, we present a simple constructive proof for the generating function for the unsigned Stirling numbers of the first kind using the equidistribution of pilots and cycles of permutations.

1 Introduction

There are many studies on different statistics of permutations in the literature, e.g., inversion number, excedance and descent [4]. In this note, we study another simple statistic of permutations which we call pilots (while they could be called right-to-left minima as well). For a permutation π = π_{1}π_{2} ⋯ π_{n} on [n] = {1, 2, … n}, π_{i} is called a pilot of π if π_{i} < π_{j} for all j > i. Note that π_{n} is always a pilot of π. We relate pilots to a representation of a permutation as a product of its disjoint cycles, that allows us to give a simple constructive proof for the generating function for the unsigned Stirling numbers of the first kind.

The unsigned Stirling number of the first kind c(n, k) (see \underline{A132393} [3]) is the number of permutations on [n] consisting of k disjoint cycles [2, 4]. Our main result is to prove the following theorem:

Theorem 1. For 1 ≤ k ≤ n, we have

∑_{k=1}^{n} c(n, k)x^{k} = x(x + 1)(x + 2) ⋯ (x + n − 1).  (1)

2 Proof of Theorem 1

There are four proofs of Eq. (1) in Stanley [4] and one in Callan [1]. In Stanley [4], when a permutation π is written as product of its disjoint cycles, a standard representation is defined as follows: each cycle is written with its largest element first, and all the cycles are written in increasing order of their largest element. By this standard representation, we can obtain a bijection between permutations with k cycles and permutations with k left-to-right maxima. However, to make use of pilots, we define a different representation as follows: we write π = C_{1}C_{2} ⋯ C_{k} so that min{C_{i}} < min{C_{j}} for all j > i and each cycle C_{i} ends with min{C_{i}} for all i. We call this new representation as the standard representation of type P. For example, π = 76154832 has three cycles: (173), (268) and (45). Then, in the standard representation of type P, we write π = (731)(682)(54).

For a permutation π with k cycles written in the standard representation of type P, if we erase the parentheses of the cycles, we obtain a permutation as a word π′. For example, from π = (731)(682)(54) we obtain π′ = 73168254. Reversely, each pilot of π′ induces a cycle of π, e.g., 1 → (731), 2 → (682), 4 → (54). It is easy to observe that such a correspondence between permutations with k cycles and permutations with k pilots is a bijection, that is, we have

Lemma 2. The number of permutations with k pilots equals to the number of permutations with k cycles.

Let pil(π) denote the number of pilots of π. Our idea to prove Eq. (1) is to show that

∑_{π} x^{pil(π)} = x(x + 1)(x + 2) ⋯ (x + n − 1),

where the sum is over all permutations π on [n].

Proof of Theorem 1. Note that π_{1} is a pilot of π = π_{1}π_{2} ⋯ π_{n} if and only if π_{1} = 1; the other n − 1 cases will not make π_{1} a pilot. The element π_{2} is a pilot of π if and only if π_{2} = min{[n] \ {π_{1}}}; the remaining n − 2 cases, i.e., π_{2} ∈ [n] \ {π_{1}, min{[n] \ {π_{1}}}}, will not make π_{2} a pilot; and so on and so forth. In summary, to construct a permutation π starting from an empty word, suppose π_{j} has been determined for 1 ≤ j ≤ i − 1, then π_{i} has only one chance to be a pilot of π, i.e., π_{i} = min{[n] \ {π_{1}, π_{2}, … π_{i−1}}}, and the other n − i cases not. Hence,

∑_{π} x^{pil(π)} = (x + n − 1)  by π_{1}
× (x + n − 2) by π_{2}
⋮
× (x + 1) by π_{n−1}
× x by π_{n}.

Therefore, Eq. (1) holds from Lemma 2.

3 Acknowledgments

The author would like to thank the referee for his/her useful comments which helped to improve the presentation of this note.

References

[1] D. Callan, Notes on Stirling cycle numbers, preprint,

   http://www.stat.wisc.edu/~callan/papersother/.

[2] J. H. van Lint and R. M. Wilson, A Course in Combinatorics, 2nd edition, Cambridge University Press, 2001.

[3] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, http://oeis.org.

[4] R. P. Stanley, Enumerative Combinatorics, Vol. 1, 2nd edition, Cambridge University Press, 1997.

2010 Mathematics Subject Classification: Primary 05A05. Keywords: permutation, pilot, Stirling number of the first kind.

(Concerned with sequence \underline{A132393}.)

Received January 25 2015; revised version received February 16 2015. Published in Journal of Integer Sequences, March 25 2015.

Return to Journal of Integer Sequences home page.