# permutation with cycles

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.

-

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