Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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
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


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.