Goncharov's Proof of the Probability having $k$ cycles of size $j$ in a random permutation

60 Views Asked by At

The following proof of Goncharov (page 13 of Logarithmic Combinatorial Structures, by Arratia, Barbour, and Tavare) proves that $$\mathbb{P}\left(C_{j}\left(n\right)=k\right)=\frac{j^{-k}}{k!}\sum_{l=0}^{\lfloor n/j \rfloor - k}\left(-1\right)^l \frac{j^{-l}}{l!},$$

where $C_{j}\left(n\right)$ is the number of cycles of length $i$ in a randomly chosen permutation in $S_n$.

enter image description here

Question 1: Regarding the highlighted part, what is "the $r$-fold intersection of properties, summing over all sets of $r$ distinct properties"? Since this example involves permutations and cycles, is there a more natural way to describe $S_r$?

Question 2: "For the other case, some two distinct properties have some element in common, so no permutation can have both of these properties, and the $r$-fold intersection is empty." Why can't a permutation have both of these properties?

1

There are 1 best solutions below

0
On BEST ANSWER

Consider distinct cycles $\alpha_1, \ldots, \alpha_r$ in $I$. The probability of the $r$-fold intersection of these $r$ distinct properties is $P(G_{\alpha_1} \cap G_{\alpha_2} \cap \cdots \cap G_{\alpha_r})$. They would like to sum these probabilities for all $\binom{|I|}{r}$ sets of $r$ distinct properties.


Suppose $\alpha_1$ and $\alpha_2$ are distinct but share an element, say $1$. A permutation $\pi$ cannot contain both cycles $\alpha_1$ and $\alpha_2$ because the element $1$ can only appear in exactly one cycle of $\pi$, i.e. $\pi$ has a decomposition of $\{1, \ldots, n\}$ into disjoint cycles.