Moments of number of fixed points in Ewens permutations

combinatoricspermutation-cyclespermutationsprobabilityrandom

In Ewens permutations a permutation of the first $n$ integers,
$\pi : \{1, \ldots, n\} \mapsto \{1, \ldots, n\}$, is drawn at random with probability,
$$
P(\pi) = \frac{\alpha^{L(\pi)}}{Z_{\alpha, n}}
$$

where $Z_{\alpha, n}$ is a normalising constant, $\alpha \in (0, \infty)$ is a parameter, $n \in \mathbb{N}$, and $L(\pi)$ is the number of cycles of the permutation $\pi$. When $\alpha=1$, the model reduces to uniform random permutations.

Let $S(\pi): = |\{i \in \{1, \ldots, n\} \, : \, \pi(i) = i \}|$ be the number of fixed points of the permutations.
I would need to characterise the moments of this variable,
$$
E[S (S-1) (S-2) \cdots (S-k) ]
$$

for any $k \in \mathbb{N}_0$, where $E$ is the expectation with respect to $P$. When $k=0$, this quantity corresponds to the expected size of the match set, this has been characterised here Number of fixed points in permutations with Ewen distribution.

Best Answer

Note that $S(S-1)\cdots(S-k+1)$ is the number of ordered $k$-tuples of fixed points. By linearity of expectation, $$ E[S(S-1)\cdots(S-k+1)] = n(n-1)\cdots(n-k+1) p,$$ where $p$ is the probability that any given ordered $k$-tuple is fixed. Taking the given $k$-tuple to be $n-k+1,\dots,n-1,n$, we clearly have $$p = \sum_{\pi \in S_{n-k}} \frac{\alpha^{L(\pi)}}{Z_{\alpha,n}} = \frac{Z_{\alpha,n-k} \alpha^k}{Z_{\alpha,n}}.$$ As in the linked question, the normalization constant is explicitly $$Z_{\alpha,n} = \alpha(\alpha+1) \cdots (\alpha+n-1).$$ Plugging in, $$E[S(S-1)\cdots(S-k+1)] = \frac{n(n-1)\cdots(n-k+1) \alpha^k}{(\alpha+n-1)(\alpha+n-2)\cdots(\alpha+n-k)}.$$

EDIT. As to the formula for $Z_{\alpha,n}$, here are two proofs. One is via (unsigned) Stirling numbers $|s(n,k)|$. Wikipedia defines them in two ways: one as the number of permutations of $n$ elements with $k$ cycles, the other as the coefficient of $x^k$ in $x(x+1)\cdots(x+n-1)$. Wikipedia shows that both satisfy the same recurrence and initial values, so they are the same, and that equality is what you want. Alternatively, here is a quick proof via generating functions and the binomial theorem. The number of permutations with cycle type $1^{c_1} 2^{c_2} \cdots n^{c_n}$ is $n! / (1^{c_1} c_1! \cdots n^{c_n} c_n!)$. Hence the exponential generating function is \begin{align*} \sum_{n \geq 0} Z_{\alpha,n} X^n/n! &= \sum_{n \geq 0} \sum_{\pi \in S_n} \alpha^{L(\pi)} X^n / n! \\ &= \sum_{n \geq 0} \sum_{c_1 + 2c_2 + \cdots + n c_n = n} \alpha^{c_1 + \cdots + c_n} X^{c_1 + 2c_2 + \cdots + nc_n} / (1^{c_1} c_1! \cdots n^{c_n} c_n!) \\ &= \prod_{i \geq 1} \sum_{c \geq 0} \alpha^c X^{ic} / (i^c c!) \\ &= \prod_{i \geq 1} \exp\left(\alpha X^i / i\right) \\ &= (1-X)^{-\alpha} \\ &= \sum_{n \geq 0} (-X)^n \binom{-\alpha}{n}.\end{align*} Comparing coefficients of $X^n$ gives $Z_{\alpha,n} = \alpha(\alpha+1)\cdots(\alpha+n-1)$, as claimed.

EDIT 2. Actually, come to think of it, this is more direct. For each permutation $\sigma \in S_{n-1}$ we define $n$ permutations $\sigma, \sigma(1,n), \sigma(2,n), \dots, \sigma(n-1,n) \in S_n$. Of these one has one more cycle and the other $n-1$ have the same number of cycles, and all together we get each element of $S_n$ exactly once, so $$Z_{\alpha,n} = \alpha Z_{\alpha,n-1} + (n-1) Z_{\alpha,n-1} = (\alpha+n-1)Z_{\alpha,n-1}.$$ Also $Z_{\alpha,0} = 1$, so the formula holds by induction.

Related Question