Counting permutations in $S_n$ with $1,2,..,k$ all in same cycle The number of permutations in $S_n$ for which the first $k$ items $1,2,...,k$ are all in the same cycle can be shown (by a somewhat tedious argument) to be $n!/k.$ I'm looking for less computational ways to see why this is so. Or for any references/links about this count.
For my computational proof I assumed each cycle in the full cycle decomposition begins with its least element, and that the cycles are arranged in order of their least elements from left to right. The first cycle then has to have length $r$ with $k \le r \le n,$ and begins with the $1.$ There are then $\binom{r-1}{k-1}$ ways to place the remaining $2,3,...,k$ items in this first cycle. Any spots not yet filled must be filled from the $n-k$ items beyond $k$ and after that, with the $r$ cycle filled in, there will remain $n-r$ items to be permuted in any way. Looked at another way, there are $n-k$ items left to fill in both the unfilled positions in the $r$ cycle and all other positions. This gives $\binom{r-1}{k-1}\cdot (n-k)!$ ways that the first cycle has length $r.$ This is to be summed from $r=k$ to $n$ for the full count, and after multiplying by $k$ and rearranging things (and applying the factorial version of binomial coefficients) the $n!/k$ answer became equivalent to a known binomial sum, wherein one sums $\binom{a}{a}+\binom{a+1}{a}+ \cdots + \binom{b}{a}$ and gets $\binom{b+1}{a+1}.$
As can be seen this is a somewhat longwinded argument to establish the claimed count. But since it came out such a simple expression in terms of $n$ and $k,$ I thought there might be some way of looking at the counting question so as to see the result more simply.
 A: With  $q$ the  total number  of elements  on the  cycle that  contains
$1,2,\ldots,k$ we get the formula
$$\sum_{q=k}^n \frac{q!}{q} {n-k\choose q-k} (n-q)!$$
which says that there are $(q-1)!$ cycles on the $q$ elements, we must
choose the  remaining $q-k$ elements  for the cycle from  the elements
other than the first $k$ and  combine this with any permutation of the
remaining elements.  (Actually we combine with  any factorization into
cycles of  the remaining elements but  there are $(n-q)!$ of  these by
the  obvious   bijection  with  the  factorizations   into  cycles  of
$S_{n-q}.$)
This is
$$\sum_{q=k}^n (q-1)! {n-k\choose q-k} (n-q)!
= \sum_{q=0}^{n-k}  {n-k\choose q} (q+k-1)! (n-k-q)!.$$
Observe that when we multiply  two exponential generating functions of
the sequences $\{a_n\}$ and $\{b_n\}$ we get that
$$ A(z) B(z) = \sum_{n\ge 0} a_n \frac{z^n}{n!} 
\sum_{n\ge 0} b_n \frac{z^n}{n!}
= \sum_{n\ge 0} 
\sum_{k=0}^n \frac{1}{k!}\frac{1}{(n-k)!} a_k b_{n-k} z^n\\
= \sum_{n\ge 0} 
\sum_{k=0}^n \frac{n!}{k!(n-k)!} a_k b_{n-k} \frac{z^n}{n!}
= \sum_{n\ge 0} 
\left(\sum_{k=0}^n {n\choose k} a_k b_{n-k}\right)\frac{z^n}{n!}$$
i.e. the  product of the  two generating functions is  the exponential
 generating function of $$\sum_{k=0}^n {n\choose k} a_k b_{n-k}.$$
Here we have
$$A(z) = \sum_{q\ge 0} (q+k-1)! \frac{z^q}{q!}
= (k-1)! \sum_{q\ge 0}  {q+k-1\choose q} z^q
= (k-1)! \frac{1}{(1-z)^k}$$
and
$$B(z) = \sum_{q\ge 0} q! \frac{z^q}{q!} = \frac{1}{1-z}.$$
The result is therefore
$$ (n-k)! [z^{n-k}] A(z) B(z)
\\ = (n-k)! [z^{n-k}] (k-1)! \frac{1}{(1-z)^{k+1}}
= (n-k)! (k-1)! {n\choose k}
= \frac{n!}{k}.$$
