9
$\begingroup$

Let $k\in\mathbb{N}$ be a fixed natural number and $f_k(n)$ denotes the number of all permutations of $\left\{1,..,n\right\}$ that does not contain any cycle of length $k$. Find as simple as possible ( but not simpler ;) ) formula for $f_k(n)$ and count $\lim_{n\to \infty} \frac{f_k(n)}{n!}$

I was learning for the test and encountered this problem. It's very unusual I think, I completely don't know how to approach. Can anybody help?

$\endgroup$
3
  • $\begingroup$ Do you know how to solve this problem for $k = 1$? $\endgroup$ Jun 16, 2013 at 9:16
  • $\begingroup$ Hmm, for $k=1$ we have that $f_1(n)$ is the number of $n$-permutations without any cycle of length $1$ so I think $f_1(n)=!n$, where $!n$ is the number of $n$-permutations without any fixed points, hence $\lim_{n\to\infty}!n/n! = 1/e$, is it correct? $\endgroup$
    – xan
    Jun 16, 2013 at 9:37
  • $\begingroup$ Yes, but what arguments do you know justifying this, and can you generalize them? $\endgroup$ Jun 16, 2013 at 19:05

2 Answers 2

7
$\begingroup$

This can also be done using inclusion-exclusion. Calculate the number of permutations having at least one $k$-cycle.

The number of permutations with at least one $k$-cycle is $$\binom{n}{k, n-k} \frac{k!}{k} (n-k)! \frac{1}{1!}.$$ This expression simply represents the fact that we choose the $k$ elements that go on the cycle, that they can form $k!/k$ cycles and that the rest of the permutation can be anything. The factorial at the end represents the fact that there are no symmetries when we choose just one cycle.

In the above we have counted permutations with at least two $k$-cycles twice, so using inclusion-exclusion we add $$-\binom{n}{k, k, n-2k} \left(\frac{k!}{k}\right)^2 (n-2k)! \frac{1}{2!}.$$ The two factorial represents the fact that there are two permutations of the two $k$-cycles and the $(n-2k)!$ the fact that the rest of the permutation can be anything.

Now we have counted permutations with at least three $k$-cycles ${3\choose 1}-{3\choose 2} = 0$ times, so we add in $$\binom{n}{k, k, k, n-3k} \left(\frac{k!}{k}\right)^3 (n-3k)! \frac{1}{3!}.$$ We continue this way up to the maximum of $\lfloor n/k \rfloor$ $k$-cycles, obtaining $$n! \frac{1}{k \times 1!} - n! \frac{1}{k^2 \times 2!} + n! \frac{1}{k^3 \times 3!} - n! \frac{1}{k^4 \times 4!} +\cdots \pm n! \frac{1}{k^{\lfloor n/k \rfloor} \times {\lfloor n/k \rfloor}!} .$$ Simplifying and subtracting from $n!$ to get the permutations with no $k$-cycles, we obtain $$n! - n! \frac{1}{k \times 1!} + n! \frac{1}{k^2 \times 2!} - n! \frac{1}{k^3 \times 3!} + n! \frac{1}{k^4 \times 4!} -\cdots \pm n! \frac{1}{k^{\lfloor n/k \rfloor} \times {\lfloor n/k \rfloor}!} \\= n! \sum_{q=0}^{\lfloor n/k \rfloor} (-1)^q \frac{1}{k^q \times q!} ,$$ which is of course the same as in the generating function proof.

$\endgroup$
0
3
$\begingroup$

The exponential generating function of these permutations is given by $$ G(z) = \exp\left(-\frac{z^k}{k} + \log \frac{1}{1-z}\right) = \frac{1}{1-z} \exp\left(-\frac{z^k}{k}\right).$$

This implies that (assume $n\ge 1$) $$f_k(n) = n! [z^n] \frac{1}{1-z} \exp\left(-\frac{z^k}{k}\right) = n! \sum_{q=0}^{\lfloor n/k\rfloor} \frac{(-1)^q}{q! k^q}.$$ The asymptotics / the proportion of such permutations is thus $$\lim_{n\to\infty} \sum_{q=0}^{\lfloor n/k\rfloor} \frac{(-1/k)^q}{q!} = e^{-1/k}.$$

$\endgroup$
1
  • $\begingroup$ Can someone provide a reference for this exponential generating function? The only reference I know of is on the OEIS, but I can't find a book or article that proves it. $\endgroup$ Aug 21, 2020 at 0:45

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .