I'm having some trouble with the following question:
How many permutations of $\{1,…,n\}$ are there such that, the cycle containing $1$ has length $k\leq n$?
Let $[n]$ for $n \in \mathbb N$ denote the set $\{1,…, n\}$
I did the following:
there are $\binom nk$ ways of choosing witch elements of $[n]$ will be on the k-cycle containing $1$.
Then, there are $(k-1)!$ ways of writing the k-cycle
Now, there are $(n-k)!$ permutations of the other elements that are not in the k-cycle, thus the total number of permutations should be:
$$\binom nk (k-1)!(n-k)! = \frac{n!}{k}$$
I'm asking this because, in the next question, my teacher says that if we sum all these numbers from $k = 1$ to $k = n$ we should get $n!$, but I'm getting: $$n! \sum_{k = 1}^n \frac{1}{k}$$
What did I do wrong?
Best Answer
The problem is that you selected $k$ elements, but if $1$ is in the cycle, then you just need $k-1$ elements out of the $n-1$ elements that are not $1$.