Precise results for Ewens distribution {#s:ew}
======================================

When we weight by $c(\pi) = \#$ left-to-right maxima in $\pi$, we obtain the Ewens distribution. In this section, we work out the optimal best choice strategy for all $N$.

Let ${\{N\}!}$ be the polynomial in ${\theta}$ defined by $${\{N\}!} =  {\theta}({\theta}+1)({\theta}+2) \cdots ({\theta}+(N-1)).$$

The following result justifies our “${\theta}$-analogue” notation.

We have $${\{N\}!} = \sum_{\pi \in {\mathfrak{S}}_N} \theta^{\# \text{left-to-right maxima in } \pi}.$$ Hence, the coefficients of ${\theta}$ in ${\{N\}!}$ are Stirling numbers (of the type used to count permutations by number of cycles).

This is straightforward to prove using induction since we may extend each permutation $\pi$ of $N-1$ by placing one of the values $1, 2, \ldots, N-1$ in the last position and arranging the complementary values according to $\pi$ (this does not create a new left-to-right maximum so contributes $(N-1)
{\{N-1\}!}$ to ${\{N\}!}$) or by simply appending the value $N$ to the last position of $\pi$ (which does create a new left-to-right maximum, so contributes ${\theta}{\{N-1\}!}$ to ${\{N\}!}$).

The equivalence between the number of cycles and number of left-to-right maxima (attributed to Rényi) is accomplished by writing the cycle notation for a permutation using the maximum element in a 