Nice proof that expected number of $k$-cycles in a permutation of $n$ is $\frac1k$ whenever $0Taking the combintorialist point of view that a cycle of a permutation$~\sigma$ of a finite set $S$ is an orbit of the action of the subgroup generated by$~\sigma$ in its (natural) action on$~S$, it is known that whenever $S$ admits $k$-cycles at all (so $0<k\leq n$ where $n$ is the size of $S$), the expected number of $k$-cycles of$~\sigma$ where $\sigma$ is chosen uniformly at random among all permutations of$~S$, is precisely$~\frac1k$. Stated differently, the statistic "number of $k$-cycles" takes an average value of$~\frac1k$ when $\sigma$ runs over all permutations of$~S$. I am looking for nice, intuitive, transparent, proofs of this fact, notably where the fraction$~\frac1k$ comes about naturally, preferably as the probability of obtaining a specific value when choosing an element uniformly from a $k$-element set. While I know a few easy computations that prove the result, none I've seen so far have achieved this highest standard, though some arrive at the fraction after some very basic cancellations.
The cases $k=1$ (the expected number of fixed points of a permutation is precisely $1$) and $k=n$ (there are $(n-1)!$ distinct cyclic permutations of $S$, which is $\frac1n$ of all permutations) are very well known and with easy proofs, but I would like a proof that covers all allowed values of $k$ in a uniform manner.
I've seen quite a few questions on this site that come close to this one, but few state the result in isolation and none specifically ask for elegant arguments, so I don't feel this question is truly a duplicate of any of them.

This question was inspired by watching this video (with a rather click-bait title) where the deduction of the case for $k=n$ (from 8:17 on) is followed by the irrefutable argument "this is a general result" (implying it's validity for all $k$) with no mention of expectation (for $k=n$ the only possible numbers of cycles are $0$ and $1$, so the expected value is just a probability) and no explanation whatsoever.
 A: One argument is that looking at a particular single element, the probability that the cycle that element is in is of length $k$ is $\frac1n$. (A seats on a plane argument justifies this.)
So the expected number of elements finding themselves in a cycle of length $k$ is $n\left(\frac1n\right)=1$, by linearity of expectation.
Since cycles of length $k$ have $k$ elements, the expected number of cycles of length $k$ is $\frac1k$.
A: So here is a straightforward approach (which a colleague suggested to me), in which the fraction $\frac1k$ unfortunately only comes out after simplification at the end. The idea is to simply count all distinct pairs of a permutation$~\sigma$ of $S$ and a specific $k$-cycle (a set of size $k$) that occurs as orbit for$~\sigma$; this number should turn out to be $\frac{n!}k$ which then proves that the expected number of $k$-cycles associated to a random$~\sigma$ is$~\frac1k$. Start with enumerating the possible $k$-subsets of$~S$ (candidates for orbits) of which there are obviously $\binom nk$. Then for each such $k$-subset $P$, enumerate the permutations for which $P$ occurs as an orbit: a cyclic permutation of $P$ can be chosen in $(k-1)!$ ways (as per the result mentioned in OP) while for the remaining  $n-k$ elements an unconstrained permutation can be chosen in $(n-k)!$ ways (obviously independently of the choice of $P$). Multiply for the total number of pairs:
$$
  \binom nk\times(k-1)!\times(n-k)!
  = \frac{n!\times(k-1)!\times(n-k)!}{k!\times(n-k)!}
  = \frac{n!}k
$$
as desired. Note that the condition $k\leq n$, which necessarily has to be used somewhere, is implicitly invoked when rewriting $\binom nk=\frac{n!}{k!\times(n-k)!}$; when the condition is not satisfied the left hand side is $0$ while $(n-k)!$ in the right hand side is not defined (of course the argument that there are $(n-k)!$ permutations of the "remaining" elements also goes awry). And to be complete, the presence of $(k-1)!$ makes the argument fail for $k=0$, and indeed the statement that a $k$-set admits $(k-1)!$ cyclic permutations needs the hypothesis $k>0$.
A: Here is a proof that exploits linearity of expectation, which is something that certainly comes to mind. I'll fix some value $s\in S$ and $k\in\{1,\ldots,n\}$, and let $\def\Sym{\operatorname{Sym}}\Sym(S)$ denote the set of permutations of $S$. Let $\chi_{s,k}:M\to\{0,1\}$ be the characteristic function of the condition "the cycle of the permutation containing $s$ has length$~k$". The first step is to show that the expected value of$~\chi_{s,k}$, viewed as a random variable on $\Sym(S)$ with uniform probability, is$~\frac1n$, independently of $s$ and of$~k$.
At this point I need to fix an order on $S$, which will allow met to write permutations of $S$ in two-line form; to avoid horribly complicated notation I will just assume that $S=\{1,\ldots,n\}$ (but still think of $s$ as element of $S$ and of $k$ as a number, a potential cycle length). Now
consider the bijection $f:\Sym(S)\to\Sym(S)$ defined as follows. Given $\sigma=({1\atop\sigma_1}~\cdots~{n\atop\sigma_n})$ in two-line form, locate the position $l=\sigma^{-1}_s$ where $s$ occurs in the second line, and form the product$~\pi$ of the cycle $(s~\sigma_1~\sigma_2~\cdots~\sigma_{l-1})$ (effectively reading the entry $\sigma_l=s$ as a right parenthesis) and the permutation of the remaining entries $\{\sigma_{l+1},\ldots,\sigma_n\}$ with $2$-line form $({e_1\atop\sigma_{l+1}}~\cdots~{e_{n-l}\atop\sigma_n}))$ where $\{e_1,\ldots,e_{n-l}\}=\{\sigma_{l+1},\ldots,\sigma_n\}$ and $e_1<\ldots<e_{n-l}$ (which is a complicated way of saying the permutation of those elements suggested by the sequence $(\sigma_{l+1},\ldots,\sigma_n)$); now $f(\sigma)=\pi$. It is not hard to see that $f$ is invertible and therefore a bijection. Also it is clear that $\chi_{s,k}(f(\sigma))$ is the characteristic function of the event $\sigma^{-1}_s=k$, or $\sigma_k=s$, and since $\sigma_k$ could be any value in $S$ with equal probability, the average (or expected) value of that function is$~\frac1n$.
Now we apply linearity of expectation, forming the sum $\sum_{s\in S}\chi_{s,k}$ of the statistics (or random variables if you prefer) $\chi_{s,k}$ for all $n$ values of $s$; clearly one gets that the expected value of this sum is $n\times\frac1n=1$, independently of $k$. But is is also clear that $\sum_{s\in S}\chi_{s,k}(\sigma)$ is the size of the union of $k$-cycles for$~\sigma$, or $k$ times the number of $k$-cycles for$~\sigma$; the expected value of that number is than $\frac1k$ QED.

This is of course the same answer as that of Henry, but written by someone who refuses to be concise (or as I would prefer to say, who refuses to sacrifice precision to conciseness). It was also strongly inspired by this answer by joriki to a closely related question.
A: Assume $n\ge k$. We will be working in the symmetric group $S_n$ of permutations of $[n]=\{1,2,...,n\}$.
Observation 1: Given a fixed $k$-cycle, it appears in exactly $(n-k)!$ elements of $S_n$. (This comes from all the permutations of the remaining $n-k$ elements of $[n]$.)
Observation 2: There are ${n\choose k}\cdot \frac{k!}{k}$ cycles of length $k$ that can be made with elements of $[n]$. (Choose $k$ elements of $[n]$ to form a $k$-cycle, and then choose a cyclic permutation of these elements.)
So counting over all of $S_n$, there will be a total of $(n-k)!\cdot {n\choose k}\cdot \frac{k!}{k}=\frac{n!}{k}$ cycles of length $k$ appearing in all of $S_n$.
So the expected number of cycles of length $k$ appearing in elements of $S_n$ is given by $\frac{\frac{n!}{k}}{{n!}}=\frac1k$
This value of $\frac1k$ comes about because a cycle of length $k$ can be expressed in $k$ different ways (depending on where you want to 'start' the cycle).
A: This bijective proof avoids the use of expectation, it is purely combinatorial:
We will show a bijection between the set $S$ of permutations and the set $\{1,2,\dots,k\}\times T$, where $T$ is the set of occurrences of $k$-cycles in $S$. Hence the number of occurrences of $k$-cycles divided by the number of permutations is $1/k$ as stated. The bijection is really simple, we just need to be careful with notation to make it clear.
The elements of $T$ are the pairs $(\tau,\sigma)$, meaning that $\tau$ is a $k$-cycle in the permutation $\sigma$. We'll adopt the usual cycle notation $\tau=(i_1\,i_2\, \dots \,i_k)$ but the order notation $\sigma=(\sigma_1,\sigma_2, \dots, \sigma_n)$ instead. That is, if these form $(\tau,\sigma)\in T$ then $\sigma_{i_1}=i_2, \sigma_{i_2}=i_3, \dots, \sigma_{i_k}=i_1$. If, in the expression of $\tau$, $i_1$ is the minimum of its $k$ elements we'll say it is in primal form).
For instance, for $n=6$ we have
$$(\tau,\sigma)\in T \quad {\rm for} \quad \tau=(2\, 4\, 6\, 3) \ {\rm and\ } \sigma=(5,4,2,6,1,3)\,,$$
and note that $\tau$ is in primal form.
Then we define our bijection as follows: for $\tau=(i_1\,i_2\, \dots \,i_k)$ in primal form and $(\tau,\sigma)\in T$, the image of $(j,(\tau,\sigma))$ is $\tilde\sigma = (i_j, i_{j+1},\dots,i_{j-1},\omega)\in S$, where $\omega$ is the list of the numbers not in $\tau$, keeping their relative order (and of course $j-1$ means $k$ if $j=1$).
For example, for $n=6$ and $\tau$ and $\sigma$ the same as before,
$$
(1,(\tau,\sigma)) \mapsto \tilde\sigma = (2,4,6,3,5,1) \quad {\rm and}\quad (3,(\tau,\sigma)) \mapsto \tilde\sigma = (6,3,2,4,5,1)\,.
$$
It is clear that the following is the inverse map: for $\tilde\sigma=(\tilde\sigma_1, \tilde\sigma_2, \dots, \tilde\sigma_k,\omega)$ (where $\omega$ is the $n-k$ remaining numbers listed in any order) we get $(j,(\tau,\sigma))\in \{1,2,\dots, k\}\times T$, where $\tau=(\tilde\sigma_1\,\tilde\sigma_2\,\dots\,\tilde\sigma_k)$, $j$ indicates the position of $\tilde\sigma_1$ in the primal form of $\tau$, and $\sigma$ is the permutation which has $\tau$ as a cycle and the terms of $\omega$ are placed in the remaining positions, keeping their relative order.
For instance, if $n=7$, $k=3$ and $\tilde\sigma = (4,6,2,1,7,3,5)$ then $\tau=(4\,6\,2)=(2\,4\,6)$, so $j=2$ and $\sigma=(1,4,7,6,3,2,5)$.
Finally, please note that the special case $k=1$ (the average number of fixed points is 1 regardless of $n$) is much simpler to express.
