0
$\begingroup$

Let $n$ and $k$ be a positive integers satisfying $n\geq k$, then

$$c(n,k)=(n-1)c(n-1,k)+c(n-1,k-1)$$

where $c(n,k)$ denotes the number of $n$-permutations with $k$ cycles.

The proof of this theorem goes like this: we take the entry $n$ and ask if that entry form a cycle by itself or not, if it does, then we get the number $c(n-1,k-1)$. OK, elsewhere, $n$ does not form a cycle by itself, then we have the remaining $n-1$ entries that must form $k$ cycles. The $k$ cycles can be formed in $c(n-1,k)$ ways and in every such permutation we insert entry $n$ after each element. This multiplies the number of possibilities by $n-1$, and we get $(n-1)c(n-1,k)$ such permutations.

My question is, because we need insert the entry $n$ to all $c(n-1,k)$ permutations, and in every such permutation we have $n-1$ ways of doing that, what insures that, with inserting $n$ after each element(instead inserting it before each element) we won't miss any permutation?

Edit:

image

The paragraph before he finishes his proof.

$\endgroup$
  • $\begingroup$ Putting $n$ in front of everything in a cycle gives the same cycle as putting it after everything in the cycle, right? $\endgroup$ – Gerry Myerson Apr 10 '15 at 9:39
  • $\begingroup$ @GerryMyerson: Please see the edit. $\endgroup$ – Salech Rubenstein Apr 10 '15 at 10:18
  • $\begingroup$ I see it, and I ask the same question that I asked before I saw it. But I'll be specific. Suppose you want to stick $4$ into $(1\ 2\ 3)$. You might worry that you have to stick it in $4$ different places: $(4\ 1\ 2\ 3),(1\ 4\ 2\ 3),(1\ 2\ 4\ 3),(1\ 2\ 3\ 4)$. But isn't $(4\ 1\ 2\ 3)$ equal to $(1\ 2\ 3\ 4)$? $\endgroup$ – Gerry Myerson Apr 10 '15 at 12:24
  • $\begingroup$ I see it now. Thanks! $\endgroup$ – Salech Rubenstein Apr 10 '15 at 13:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.