0
$\begingroup$

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!

1 Answers 1

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

  • 0
    @bronko: You’re welcome!2012-12-13