\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}

\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}


\begin{center}
\vskip 1cm{\LARGE\bf A Note on the Generating Function for the
\\
\vskip .1in
Stirling Numbers of the First Kind }
\vskip 1cm
\large
Ricky X. F. Chen\\
Department of Mathematics and Computer Science\\
University of Southern Denmark \\
Campusvej 55\\
DK-5230, Odense M \\
Denmark\\
\href{mailto:chen.ricky1982@gmail.com}{\tt chen.ricky1982@gmail.com}
\end{center}

\vskip .2 in

\begin{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.
\end{abstract}


\section{Introduction}

There are many studies on different statistics of permutations in the literature, e.g.,
inversion number, excedance and descent~\cite{stanley}.
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 $\pi=\pi_1\pi_2 \cdots \pi_n$ on $[n]=\{1,2,\ldots n\}$,
$\pi_i$ is called a \emph{pilot} of $\pi$ if $\pi_i < \pi_j$ for all $j>i$.
Note that $\pi_n$ is always a pilot of $\pi$.
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 \seqnum{A132393}~\cite{Sloane})
is the number of permutations on $[n]$
consisting of $k$ disjoint cycles~\cite{vanlint,stanley}. Our main result is to
prove the following theorem:


\begin{theorem}\label{thm1} For $1\leq k \leq n$, we have
\begin{align}\label{2eq1}
\sum_{k=1}^n c(n,k)x^k =x(x+1)(x+2)\cdots(x+n-1).
\end{align}
\end{theorem}



\section{Proof of Theorem~\ref{thm1}}



There are four proofs of Eq.~\eqref{2eq1} in Stanley~\cite{stanley} and one in Callan~\cite{callan}.
In Stanley~\cite{stanley}, when a permutation $\pi$ 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 $\pi=C_1C_2\cdots 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, $\pi=76154832$ has three cycles: $(173)$,~$(268)$ and $(45)$.
Then, in the standard representation of type $P$, we write $\pi=(731)(682)(54)$.


For a permutation $\pi$ 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 $\pi'$. For
example, from $\pi=(731)(682)(54)$ we obtain $\pi'=73168254$. Reversely, each pilot of $\pi'$ induces
a cycle of $\pi$, e.g., $1\rightarrow (731)$, $2\rightarrow (682)$, $4\rightarrow (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




\begin{lemma}\label{2lem1}
The number of permutations with $k$ pilots equals to the number
of permutations with $k$ cycles.
\end{lemma}

Let $pil(\pi)$ denote the number of pilots of $\pi$.
Our idea to prove Eq.~\eqref{2eq1} is to show that
\[
\sum_{\pi}x^{pil(\pi)}=x(x+1)(x+2)\cdots(x+n-1),
\]
where the sum is over all permutations $\pi$ on $[n]$.

\begin{proof}[Proof of Theorem~\ref{thm1}]
Note that $\pi_1$ is a pilot of $\pi=\pi_1\pi_2\cdots\pi_n$ if and only if $\pi_1=1$;
the other $n-1$ cases will not make $\pi_1$ a pilot.
The element $\pi_2$ is a pilot of $\pi$ if and only if $\pi_2=\min\{[n]\setminus\{\pi_1\}\}$;
the remaining $n-2$ cases, i.e., $\pi_2\in [n]\setminus \{\pi_1, \min\{[n]\setminus\{\pi_1\}\}\}$, will not
make $\pi_2$ a pilot;
and so on and so forth.
In summary, to construct a permutation $\pi$ starting from an empty word, suppose
$\pi_j$ has been determined for $1\leq j\leq i-1$, then $\pi_i$ has
only one chance to be a pilot of $\pi$, i.e., $\pi_i=\min\{[n]\setminus\{\pi_1,\pi_2,\ldots \pi_{i-1}\}\}$,
and the other $n-i$ cases not. Hence,
\begin{align*}
\sum_{\pi}x^{pil(\pi)}&=(x+n-1)\qquad\qquad\qquad \mbox{ by $\pi_1$}\\
&\times (x+n-2) \qquad\qquad\qquad \mbox{ by $\pi_2$}\\
&\qquad\vdots\\
&\times (x+1)\qquad\qquad\qquad\qquad \mbox{ by $\pi_{n-1}$}\\
&\times x\quad\qquad\qquad\qquad\qquad\qquad\mbox{by $\pi_n$}.
\end{align*}
Therefore, Eq.~\eqref{2eq1} holds from Lemma~\ref{2lem1}.
\end{proof}



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







\begin{thebibliography}{9}
\bibitem{callan} D. Callan, Notes on Stirling cycle numbers, preprint,\\
\url{http://www.stat.wisc.edu/\~callan/papersother/}.

\bibitem{vanlint} J. H. van Lint and R. M. Wilson, {\it A Course in
Combinatorics}, 2nd edition, Cambridge University Press, 2001.

\bibitem{Sloane} N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, \url{http://oeis.org}.

\bibitem{stanley} R. P. Stanley, {\it Enumerative Combinatorics}, Vol.\ 1, 2nd edition, Cambridge
University Press, 1997.
\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}: Primary 05A05.

\noindent \emph{Keywords:} permutation, pilot, Stirling number of the first kind.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequence
\seqnum{A132393}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received January 25 2015;
revised version received February 16 2015. 
Published in {\it Journal of Integer Sequences}, March 25 2015.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}