is a weight function that depends only on the size k of the cycle and for brevity we write defining the value of b for a permutation
This article uses the coefficient extraction operator [zn], documented on the page for formal power series.
It follows that σ may only contain cycles of length one or two, i.e. the exponential generating function g(z) of these permutations is[1] This gives the explicit formula for the total number
A cycle of length d applied d times produces the identity permutation on d elements (d fixed points) and d is the smallest value to do so.
This problem is equivalent to counting permutations with no fixed points (called derangements), and hence the EGF, where we subtract out fixed points (cycles of length 1) by removing the term z from the fundamental relation is Multiplication by
The corresponding EGF is obtained by marking cycles of size one with the variable u, i.e. choosing b(k) equal to one for
This is the least common multiple of the lengths of the cycles of P. A theorem of Goh and Schmutz[2] states that if
is the expected order of a random permutation of size n, then where the constant c is We can use the same construction as in the previous section to compute the number of derangements
To do this we need to mark all cycles and subtract fixed points, giving Now some very basic reasoning shows that the EGF
If he or she does not find his or her name in one of the fifty urns, all prisoners will immediately be executed, otherwise the game continues.
First of all, the survival probability using random choices is so this is definitely not a practical strategy.
The 30% survival strategy is to consider the contents of the urns to be a permutation of the prisoners, and traverse cycles.
To keep the notation simple, assign a number to each prisoner, for example by sorting their names alphabetically.
This strategy is precisely equivalent to a traversal of the cycles of the permutation represented by the urns.
, we find that which yields Finally, using an integral estimate such as Euler–Maclaurin summation, or the asymptotic expansion of the nth harmonic number, we obtain so that or at least 30%, as claimed.
A related result is that asymptotically, the expected length of the longest cycle is λn, where λ is the Golomb–Dickman constant, approximately 0.62.
The above computation may be performed in a more simple and direct way, as follows: first note that a permutation of
Thus, We conclude that There is a closely related problem that fits the method presented here quite nicely.
You are allowed to select k of these n boxes all at once and break them open simultaneously, gaining access to k keys.
, to the set we obtain the generating function The term yields the signed Stirling numbers of the first kind, and
The computation of the OGF of the unsigned Stirling numbers of the first kind works in a similar way.
Hence the expected number of cycles of length at most m in a random permutation is about ln m. The mixed GF
a positive integer and ask about the expected number of fixed points in the result.
has the closed form and generates the unsigned Stirling numbers of the first kind.
(Note that Section One hundred prisoners contains exactly the same problem with a very similar calculation, plus also a simpler elementary proof.)
again generates the unsigned Stirling numbers of the first kind, but in reverse order.
We have Hence the expected length of the cycle that contains q is This average parameter represents the probability that if we again select a random element of
In fact we can prove that all odd cycle invariants obey a simple recurrence, which we will derive.
The nodes at the lowest level represent sums of products of even-length cycles of the singleton
of even and odd permutations by cycle count are given by and We require the quantity which is Finally, extracting coefficients from this generating function, we obtain which is which is in turn This concludes the proof.