Sign up ×

Let $c(n,k)$ be the number of permutations of $[n]$ with $k$ cycles. I am looking for a proof of the following.

  1. $c(n,k)=(n-1)c(n-1,k)+c(n-1,k-1)$ for $n,k \geq 1$ and $c(0,0)=1$
  2. The number of permutations $\pi \in S_n$ with cycle type $(c_1,\dots,c_n)$ is $\frac{n!}{1^{c_1}c_1!2^{c_2}c_2!\dots n^{c_n}c_n!}$ where $c_i=c_i(\pi)$ is the number of cycles of $\pi$ of length $i$.
  3. $\sum\limits_{k=0}^{n} c(n,k)t^k=t(t+1)(t+2)\dots(t+n-1)$.
  4. $\sum\limits_{k=0}^{n} c(n,k) \frac{x^n}{n!}=\frac{1}{k!}\left(\log(\frac{1}{1-x}) \right) ^k$
  5. I looking for a bijection between the set of permutations with $k$ cycles and the set of permutations with $k$ left-right minima.

Thanks for your help!

share|cite|improve this question

1 Answer 1

up vote 1 down vote accepted
  1. This is Lemma 1.3.6 of Richard P. Stanley, Enumerative Combinatorics, Volume 1, freely available here in PDF format. It’s worth noting that these numbers $c(n,k)$ are the unsigned Stirling numbers of the first kind, also written $n\brack k$; the Wikipedia article also has a proof of this recurrence.

  2. This is Proposition 1.3.2 in Stanley.

  3. This is Proposition 1.3.7 in Stanley.

  4. This is misstated, since the index of summation appears on the righthand side. There is an identity $$\sum_{n\ge 0}c(n,k)\frac{x^n}{n!}=\frac1{k!}\left(\ln\frac1{1-x}\right)^k\;,$$ formula (7.50) in Graham, Knuth, and Patashnik, Concrete Mathematics; is this what you meant? There’s a sketch of a proof in the Wikipedia article to which I linked above.

  5. This is Proposition 1.3.1 in Stanley.

share|cite|improve this answer
Thank you very much for your answer. Unfortunately I cannot find the sketch of the proof you were talking about. – bronko Dec 13 '12 at 13:04
@bronko: It’s at Combinatorial proof. – Brian M. Scott Dec 13 '12 at 13:36
Thank you very much! – bronko Dec 13 '12 at 13:40
@bronko: You’re welcome! – Brian M. Scott Dec 13 '12 at 13:46

Your Answer


