2

Choose a random permutation $\sigma \in \mathcal{S}_n$. What's the probability that it contains a $k$-cycle as you take $n \to \infty$?

I ran a couple examples and it seems to approach $1 - e^{-1/k}$. Can anyone explain this phenomenon?

MT_
  • 19,603
  • 9
  • 40
  • 81

1 Answers1

2

Permutations are counted by cycles using the exponential generating function

$$ \frac1{1-z}=\exp\log\frac1{1-z}=\exp\left(\sum_{j=0}^\infty\frac{z^j}j\right)\;, $$

where the $j$-th term corresponds to $j$-cycles (see Wikipedia). To count the number of permutations without $k$-cycles, we can drop the $k$-th term to obtain

$$ n![z^n]\exp\left(\sum_{j=0}^\infty\frac{z^j}j-\frac{z^k}k\right) = \frac1{1-z}\exp\left(-\frac{z^k}k\right)\;, $$

where $[z^n]$ denotes extraction of the coefficient of $z^n$. This coefficient is the sum of all coefficients up to $n$ in $\exp(-z^k/k)$. For $n\to\infty$, that becomes the sum of all coefficients, which is the value at $1$, i.e. $\mathrm e^{-1/k}$. Dividing by the number $n!$ of permutations in $S_n$ to obtain the probability for a random permutation not to contain a $k$-cycle cancels the factor $n!$, so the probability tends to $\mathrm e^{-1/k}$, and the complementary probability that a random permutation contains a $k$-cycle tends to $1-\mathrm e^{-1/k}$, in agreement with your results.

joriki
  • 238,052
  • Why do we get a $n![z^n]$ term on the LHS? It seems we just multiply both sides by $\exp(-\frac{z^k}{k})$, no? I'm probably just confused about what's going on here. I'm going to read over it a couple more times. – MT_ Jun 20 '16 at 18:28
  • @Soke: This is not a term -- as I wrote, $[z^n]$ is notation for extracting the coefficient of $z^n$, it's not a multiplication by $z^n$. The factor $n!$ is part of the definition of an exponential generating function, which counts a sequence $a_n$ using the series $\sum_n\frac{a_n}{n!}z^n$, so $a_n$ is $n!$ times the coefficient of $z^n$ (as opposed to an ordinary generating function, which is the same thing without the factors of $n!$). – joriki Jun 20 '16 at 18:58
  • @Soke: I just noticed I'd written $\mathrm e^{-k}$ in several places where it was supposed to be $\mathrm e^{-1/k}$; I fixed that. – joriki Jun 20 '16 at 19:01
  • Okay, I think I get more or less what's happening here now. I've never seen EGFs before, so I think that's where my confusing is coming from. – MT_ Jun 20 '16 at 19:10
  • 1
    I worked it out a bit more and understand it a lot better now the intuitino behind the formal power series. Thanks for the help. – MT_ Jun 20 '16 at 19:29
  • @joriki Nice work. Upvoted. (+1). – Marko Riedel Jun 20 '16 at 19:58
  • @MarkoRiedel: I learned from the master :-) – joriki Jun 20 '16 at 20:06
  • These are kind words. The reference is the book by Flajolet and Sedgewick. – Marko Riedel Jun 20 '16 at 20:07