The statistics of random permutations, such as the cycle structure of a random permutation are of fundamental importance in the analysis of algorithms, especially of sorting algorithms, which operate on random permutations. Suppose, for example, that we are using quickselect (a cousin of quicksort) to select a random element of a random permutation. Quickselect will perform a partial sort on the array, as it partitions the array according to the pivot. Hence a permutation will be less disordered after quickselect has been performed. The amount of disorder that remains may be analysed with generating functions. These generating functions depend in a fundamental way on the generating functions of random permutation statistics. Hence it is of vital importance to compute these generating functions.
The article on random permutations contains an introduction to random permutations.
Permutations are sets of labelled cycles. Using the labelled case of the Flajolet–Sedgewick fundamental theorem and writing
\scriptstylel{P}
\scriptstylel{Z}
\operatorname{SET}(\operatorname{CYC}(l{Z}))=l{P}.
Translating into exponential generating functions (EGFs), we have
\exp\left(log
1 | |
1-z |
\right)=
1 | |
1-z |
where we have used the fact that the EGF of the combinatorial species of permutations (there are n! permutations of n elements) is
\sumn\ge
n! | |
n! |
zn=
1 | |
1-z |
.
This one equation allows one to derive a large number of permutation statistics. Firstly, by dropping terms from
\scriptstyle\operatorname{SET}
\scriptstyle\operatorname{SET}2
\scriptstyle\operatorname{CYC}(l{Z})
Instead of removing and selecting cycles, one can also put different weights on different size cycles. If
b:N → R
b(\sigma)=\sumc\in\sigmab(c),
defining the value of b for a permutation
\sigma
g(z,u)=1+\sumn\ge\left(
\sum | |
\sigma\inSn |
ub(\sigma)\right)
zn | |
n! |
= \exp\sumk\geub(k)
zk | |
k |
This is a "mixed" generating function: it is an exponential generating function in z and an ordinary generating function in the secondary parameter u. Differentiating and evaluating at u = 1, we have
\partial | |
\partialu |
g(z,u)|u=1=
1 | |
1-z |
\sumk\geb(k)
zk | |
k |
= \sumn\ge\left(
\sum | |
\sigma\inSn |
b(\sigma)\right)
zn | |
n! |
This is the probability generating function of the expectation of b. In other words, the coefficient of
zn
Sn
1/n!
This article uses the coefficient extraction operator [''z''<sup>''n''</sup>], documented on the page for formal power series.
See main article: Telephone number (mathematics). An involution is a permutation σ so that σ2 = 1 under permutation composition. It follows that σ may only contain cycles of length one or two, i.e. the exponential generating function g(z) of these permutations is
g(z)=\exp\left(z+
1 | |
2 |
z2\right).
This gives the explicit formula for the total number
I(n)
I(n)=n![zn]g(z)=n!\suma+2b=n
1 | |
a! 2b b! |
=n!
\lfloorn/2\rfloor | |
\sum | |
b=0 |
1 | |
(n-2b)! 2b b! |
.
Dividing by n! yields the probability that a random permutation is an involution.These numbers are known as telephone numbers.
This generalizes the concept of an involution. An mth root of unity is a permutation σ so that σm = 1 under permutation composition. Now every time we apply σ we move one step in parallel along all of its cycles. 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. Hence m must be a multiple of all cycle sizes d, i.e. the only possible cycles are those whose length d is a divisor of m. It follows that the EGF g(x) of these permutations is
g(z)=\exp\left(\sumd\mid
zd | |
d |
\right).
When m = p, where p is prime, this simplifies to
n![zn]g(z)=n!\suma+pb=n
1 | |
a! pb b! |
=n!
\lfloorn/p\rfloor | |
\sum | |
b=0 |
1 | |
(n-pb)! pb b! |
.
This one can be done by Möbius inversion. Working with the same concept as in the previous entry we note that the combinatorial species
l{Q}
l{Q}= \operatorname{SET}\left(\sumd\mid\operatorname{CYC}=d(l{Z})\right).
Qk(z)=\exp\left(\sumd\mid
zd | |
d |
\right).
pn,d
qn,k
\sumd|kpn,d=qn,k.
\sumd|kqn, x \mu(k/d)=pn,.
Q(z)=\sumd\mid\mu(k/d) x Qd(z) =\sumd\mid\mu(k/d)\exp\left(\summ\mid
zm | |
m |
\right).
n![zn]Q(z).
This formula produces e.g. for k = 6 the EGF
Q(z)= {\rme}z-{\rm
z+1/2z2 | |
e} |
-{\rm
z+1/3z3 | |
e} |
+{\rm
z+1/2 z2+1/3z3+1/6z6 | |
e} |
with the sequence of values starting at n = 5
20,240,1470,10640,83160,584640,4496030,42658440,371762820,3594871280,\ldots
For k = 8 we get the EGF
Q(z)= -{\rm
z+1/2z2+1/4z4 | |
e} |
+{\rm
z+1/2z2+1/4z4+1/8z 8 | |
e} |
5040,45360,453600,3326400,39916800,363242880,3874590720,34767532800,\ldots
Finally for k = 12 we get the EGF
Q(z)= {\rm
z+1/2z2 | |
e} |
-{\rm
z+1/2z2+1/4z4 | |
e} |
-{\rm
z+1/2z 2+1/3{z | |
e} |
3+1/6z6}+{\rm
z+1/2z2+1/3z3+1/4z4+1 /6z6+1/12z12 | |
e} |
420,3360,30240,403200,4019400,80166240,965284320,12173441280,162850287600,\ldots
See main article: Derangement. Suppose there are n people at a party, each of whom brought an umbrella. At the end of the party everyone picks an umbrella out of the stack of umbrellas and leaves. What is the probability that no one left with his/her own umbrella? 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
\exp\left(-z+\sumk\ge
zk | |
k |
\right) =
e-z | |
1-z |
.
Multiplication by
1/(1-z)
e-z
D(n)
D(n)=n!
n | |
\sum | |
k=0 |
(-1)k | |
k! |
≈
n! | |
e |
.
Hence there are about
n!/e
1/e.
This result may also be proved by inclusion–exclusion. Using the sets
Ap
\begin{matrix}1\lep\len\end{matrix}
\left|cuppAp\right|= \sump\left|Ap\right| - \sump<q\left|Ap\capAq\right| + \sump<q<r\left|Ap\capAq\capAr\right| - … \pm \left|Ap\cap … \capAs\right|.
This formula counts the number of permutations that have at least one fixed point.The cardinalities are as follows:
\left|Ap\right|=(n-1)! , \left|Ap\capAq\right|=(n-2)! , \left|Ap\capAq\capAr\right|=(n-3)! , \ldots
Hence the number of permutations with no fixed point is
n! - {n\choose1}(n-1)! + {n\choose2}(n-2)! - {n\choose3}(n-3)! + … \pm {n\choosen}(n-n)!
or
n!\left(1-
1 | |
1! |
+
1 | |
2! |
-
1 | |
3! |
+ … \pm
1 | |
n! |
\right)=n!
n | |
\sum | |
k=0 |
(-1)k | |
k! |
and we have the claim.
There is a generalization of these numbers, which is known as rencontres numbers, i.e.the number
D(n,m)
[n]
k=1
g(z,u)
g(z,u)=\exp\left(-z+uz+\sumk\ge
zk | |
k |
\right)=
e-z | |
1-z |
euz.
It follows that
[um]g(z,u)=
e-z | |
1-z |
zm | |
m! |
and hence
D(n,m)=n![zn][um]g(z,u)=
n! | |
m! |
[zn-m]
e-z | |
1-z |
=
n! | |
m! |
n-m | |
\sum | |
k=0 |
(-1)k | |
k! |
.
This immediately implies that
D(n,m)={n\choosem}D(n-m,0) and
D(n,m) | |
n! |
≈
e-1 | |
m! |
for n large, m fixed.
If P is a permutation, the order of P is the smallest positive integer n for which
Pn
A theorem of Goh and Schmutz[1] states that if
\mun
log\mun\simc\sqrt{
n | |
logn |
where the constant c is
infty | ||
2\sqrt{2\int | loglog\left( | |
0 |
e | |
1-e-t |
\right)dt} ≈ 1.1178641511899
We can use the same construction as in the previous section to compute the number of derangements
D0(n)
D1(n)
g(z,u)=\exp\left(-uz+ulog
1 | |
1-z |
\right)= \exp(-uz)\left(
1 | |
1-z |
\right)u.
Now some very basic reasoning shows that the EGF
q(z)
D0(n)
q(z)=
1 | |
2 |
x g(z,-1)+
1 | |
2 |
x g(z,1) =
1 | |
2 |
\exp(-z)
1 | + | |
1-z |
1 | |
2 |
\exp(z)(1-z).
We thus have
D0(n)=n![zn]q(z)=
1 | |
2 |
n!
n | |
\sum | |
k=0 |
(-1)k | |
k! |
+
1 | |
2 |
n!
1 | |
n! |
-
1 | |
2 |
n!
1 | |
(n-1)! |
1 | |
2 |
n!
n | |
\sum | |
k=0 |
(-1)k | |
k! |
+
1 | |
2 |
(1-n) \sim
1 | |
2e |
n!+
1 | |
2 |
(1-n).
Subtracting
D0(n)
D(n)
D1(n)=
1 | |
2 |
n!
n | |
\sum | |
k=0 |
(-1)k | |
k! |
-
1 | |
2 |
(1-n).
D0(n)
D1(n)
n-1.
See main article: 100 prisoners problem.
A prison warden wants to make room in his prison and is considering liberating one hundred prisoners, thereby freeing one hundred cells. He therefore assembles one hundred prisoners and asks them to play the following game: he lines up one hundred urns in a row, each containing the name of one prisoner, where every prisoner's name occurs exactly once. The game is played as follows: every prisoner is allowed to look inside fifty urns. 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. The prisoners have a few moments to decide on a strategy, knowing that once the game has begun, they will not be able to communicate with each other, mark the urns in any way or move the urns or the names inside them. Choosing urns at random, their chances of survival are almost zero, but there is a strategy giving them a 30% chance of survival, assuming that the names are assigned to urns randomly – what is it?
First of all, the survival probability using random choices is
\left(
{99\choose49 | |
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. The urns may thereafter be considered to contain numbers rather than names. Now clearly the contents of the urns define a permutation. The first prisoner opens the first urn. If he finds his name, he has finished and survives. Otherwise he opens the urn with the number he found in the first urn. The process repeats: the prisoner opens an urn and survives if he finds his name, otherwise he opens the urn with the number just retrieved, up to a limit of fifty urns. The second prisoner starts with urn number two, the third with urn number three, and so on. This strategy is precisely equivalent to a traversal of the cycles of the permutation represented by the urns. Every prisoner starts with the urn bearing his number and keeps on traversing his cycle up to a limit of fifty urns. The number of the urn that contains his number is the pre-image of that number under the permutation. Hence the prisoners survive if all cycles of the permutation contain at most fifty elements. We have to show that this probability is at least 30%.
Note that this assumes that the warden chooses the permutation randomly; if the warden anticipates this strategy, he can simply choose a permutation with a cycle of length 51. To overcome this, the prisoners may agree in advance on a random permutation of their names.
We consider the general case of
2n
n
n
g(z,u)= \exp\left(z+
z2 | |
2 |
+
z3 | |
3 |
+ … +u
zn+1 | |
n+1 |
+u
zn+2 | |
n+2 |
+ … \right)
1 | |
1-z |
\exp\left((u-1)\left(
zn+1 | |
n+1 |
+
zn+2 | |
n+2 |
+ … \right)\right),
[z2n][u]g(z,u),
n
2(n+1)>2n
[z2n][u]g(z,u)= [z2n][u]
1 | |
1-z |
\left(1+(u-1)\left(
zn+1 | |
n+1 |
+
zn+2 | |
n+2 |
+ … \right)\right),
[z2n][u]g(z,u)= [z2n]
1 | |
1-z |
\left(
zn+1 | |
n+1 |
+
zn+2 | |
n+2 |
+ … \right)
2n | |
= \sum | |
k=n+1 |
1 | |
k |
=H2n-Hn.
Finally, using an integral estimate such as Euler–Maclaurin summation, or the asymptotic expansion of the nth harmonic number, we obtain
H2n-Hn\sim log2-
1 | |
4n |
+
1 | |
16n2 |
-
1 | |
128n4 |
+
1 | |
256n6 |
-
17 | |
4096n8 |
+ … ,
[z2n][u]g(z,u)<log2 and 1-[z2n][u]g(z,u)>1-log2=0.30685281,
A related result is that asymptotically, the expected length of the longest cycle is λn, where λ is the Golomb–Dickman constant, approximately 0.62.
This example is due to Anna Gál and Peter Bro Miltersen;consult the paper by Peter Winkler for more information, andsee the discussion on Les-Mathematiques.net.Consult the references on 100 prisoners for links to these references.
The above computation may be performed in a more simple and direct way, as follows: first note that a permutation of
2n
n
pk=\Pr[thereisacycleoflengthk],
\Pr[thereisacycleoflength>n]=
2n | |
\sum | |
k=n+1 |
pk.
For
k>n
k
{{2n}\choosek} ⋅
k! | |
k |
⋅ (2n-k)!.
{{2n}\choosek}
k
k! | |
k |
k
(2n-k)!
k
k>n
pk=
{{2n | |
\choose |
k} ⋅
k! | |
k |
⋅ (2n-k)!}{(2n)!}=
1k. | |
We conclude that
\Pr[thereisacycleoflength>n]=
2n | |
\sum | |
k=n+1 |
1k | |
= |
H2n-Hn.
There is a closely related problem that fits the method presented here quite nicely. Say you have n ordered boxes. Every box contains a key to some other box or possibly itself giving a permutation of the keys. You are allowed to select k of these n boxes all at once and break them open simultaneously, gaining access to k keys. What is the probability that using these keys you can open all n boxes, where you use a found key to open the box it belongs to and repeat.
The mathematical statement of this problem is as follows: pick a random permutation on n elements and k values from the range 1 to n, also at random, call these marks. What is the probability that there is at least one mark on every cycle of the permutation? The claim is this probability is k/n.
The species
l{Q}
l{Q}=\operatorname{SET} \left(\sumq\ge\operatorname{CYC}=q
q | |
(l{Z}) x \sum | |
p=1 |
{q\choosep}l{U}p \right).
The index in the inner sum starts at one because we must have at least onemark on every cycle.
Translating the specification to generating functions we obtain thebivariate generating function
G(z,u)= \exp\left(\sumq\ge
zq | |
q |
q | |
\sum | |
p=1 |
{q\choosep}up\right).
This simplifies to
\exp\left(\sumq\ge
zq | |
q |
(u+1)q -\sumq\ge
zq | |
q |
\right)
\exp\left(log | 1 |
1-(u+1)z |
-log
1 | |
1-z |
\right) =
1-z | |
1-(u+1)z |
.
(1-z)\sumq\ge(u+1)qzq.
[zn]G(z,u)=(u+1)n-(u+1)n-1
[uk][zn]G(z,u)={n\choosek}-{n-1\choosek}.
Divide by
{n\choosek}
1-
(n-1)! | |
k!(n-1-k)! |
k!(n-k)! | |
n! |
=1-
n-k | |
n |
=
k | |
n |
.
G(z,u)
Applying the Flajolet–Sedgewick fundamental theorem, i.e. the labelled enumeration theorem with
G=Sm
\operatorname{SET}=m(\operatorname{CYC}(l{Z}))
we obtain the generating function
gm(z)=
1 | |
|Sm| |
\left(log
1 | |
1-z |
\right)m=
1 | |
m! |
\left(log
1 | |
1-z |
\right)m.
The term
(-1)n+mn! [zn]gm(z)=s(n,m)
yields the signed Stirling numbers of the first kind, and
gm(z)
n![zn]gm(z)=\left[\begin{matrix}n\ m\end{matrix}\right].
We can compute the OGF of the signed Stirling numbers for n fixed, i.e.
sn(w)
n | |
= \sum | |
m=0 |
s(n,m)wm.
Start with
gm(z)=\sumn\ge
(-1)n+m | |
n! |
s(n,m)zn
which yields
(-1)mgm(z)wm=\sumn\ge
(-1)n | |
n! |
s(n,m)wmzn.
Summing this, we obtain
\summ\ge(-1)mgm(z)wm= \summ\ge\sumn\ge
(-1)n | |
n! |
s(n,m)wmzn= \sumn\ge
(-1)n | |
n! |
zn
n | |
\sum | |
m=0 |
s(n,m)wm.
Using the formula involving the logarithm for
gm(z)
sn(w)
(1-z)w=\sumn\ge{w\choosen}(-1)nzn= \sumn\ge
(-1)n | |
n! |
sn(w)zn.
Comparing the coefficients of
zn
sn(w)=w (w-1) (w-2) … (w-(n-1))=(w)n,
a falling factorial. The computation of the OGF of the unsigned Stirling numbers of the first kind works in a similar way.
In this problem we use a bivariate generating function g(z, u) as described in the introduction. The value of b for a cycle not of size m is zero, and one for a cycle of size m. We have
\partial | |
\partialu |
g(z,u)|u=1=
1 | |
1-z |
\sumk\geb(k)
zk | = | |
k |
1 | |
1-z |
zm | |
m |
or
1 | |
m |
zm +
1 | |
m |
zm+1 +
1 | |
m |
zm+2 + …
This means that the expected number of cycles of size m in a permutation of length n less than m is zero (obviously). A random permutation of length at least m contains on average 1/m cycles of length m. In particular, a random permutation contains about one fixed point.
The OGF of the expected number of cycles of length less than or equal to m is therefore
1 | |
1-z |
m | |
\sum | |
k=1 |
zk | |
k |
and [zn]
1 | |
1-z |
m | |
\sum | |
k=1 |
zk | |
k |
=Hm for n\gem
where Hm is the mth harmonic number. Hence the expected number of cycles of length at most m in a random permutation is about ln m.
The mixed GF
g(z,u)
g(z,u)=\exp\left(-z+uz+log
1 | |
1-z |
\right)=
1 | |
1-z |
\exp(-z+uz).
Let the random variable X be the number of fixed points of a random permutation.Using Stirling numbers of the second kind, we have the following formula for the mth moment of X:
E(Xm)=E\left(
m | |
\sum | |
k=0 |
\left\{\begin{matrix}m\ k\end{matrix}\right\}(X)k\right)
m | |
= \sum | |
k=0 |
\left\{\begin{matrix}m\ k\end{matrix}\right\}E((X)k),
where
(X)k
g(z,u)
E((X)k)= [zn]\left(
d | |
du |
\right)kg(z,u)|u=1= [zn]
zk | |
1-z |
\exp(-z+uz)|u=1=[zn]
zk | |
1-z |
,
which is zero when
k>n
k<=n
E(Xm)=
n | |
\sum | |
k=0 |
\left\{\begin{matrix}m\ k\end{matrix}\right\}.
Suppose you pick a random permutation
\sigma
k
k
E[Fk]
For every divisor
d
k
d
d
k.
ud.
E[F6].
We get
g(z,u)=\exp\left(uz-z+u2
z2 | |
2 |
-
z2 | |
2 |
+ u3
z3 | |
3 |
-
z3 | |
3 |
+u6
z6 | |
6 |
-
z6 | |
6 |
+log
1 | |
1-z |
\right)
which is
1 | |
1-z |
\exp\left(uz-z+u2
z2 | |
2 |
-
z2 | |
2 |
+ u3
z3 | |
3 |
-
z3 | |
3 |
+u6
z6 | |
6 |
-
z6 | |
6 |
\right).
Once more continuing as described in the introduction, we find
\left. | \partial |
\partialu |
g(z,u)\right|u=1= \left.
z+z2+z3+z6 | |
1-z |
\exp\left(uz-z+u2
z2 | |
2 |
-
z2 | |
2 |
+ u3
z3 | |
3 |
-
z3 | |
3 |
+u6
z6 | |
6 |
-
z6 | |
6 |
\right)\right|u=1
which is
z+z2+z3+z6 | |
1-z |
.
E[F6]=4
n\ge6
The general procedure is
g(z,u)=\exp\left(\sumd\mid\left(ud
zd | |
d |
-
zd | |
d |
\right)+log
1 | \right)= | |
1-z |
1 | |
1-z |
\exp\left(\sumd\mid\left(ud
zd | |
d |
-
zd | |
d |
\right)\right).
\left. | \partial |
\partialu |
g(z,u)\right|u=1= \left.
\sumd\midzd | |
1-z |
\exp\left(\sumd\mid\left(ud
zd | |
d |
-
zd | |
d |
\right)\right)\right|u=1=
\sumd\midzd | |
1-z |
.
E[Fk]
\tau(k)
k
n\gek.
1
n=1
n
k
k
We construct the bivariate generating function
g(z,u)
b(k)
b(k)
Note that
g(z,u)
g(z,u)=\left(
1 | |
1-z |
\right)u
and generates the unsigned Stirling numbers of the first kind.
We have
\partial | |
\partialu |
g(z,u)|u=1=
1 | |
1-z |
\sumk\geb(k)
zk | = | |
k |
1 | |
1-z |
\sumk\ge
zk | = | |
k |
1 | |
1-z |
log
1 | |
1-z |
.
Hn
logn
(Note that Section One hundred prisoners contains exactly the same problem with a very similar calculation, plus also a simpler elementary proof.)
Once more, start with the exponential generating function
g(z,u)
l{P}
n/2
u
g(z,u)=\exp\left(u
infty | |||||
\sum | |||||
|
zk | |
k |
| |||||
+ \sum | |||||
k=1 |
zk | |
k |
\right).
There can only be one cycle of length more than
n | |
2 |
n![uzn]g(z,u)=n!
| |||||
[z | |||||
k=1 |
zk | |
k |
infty | |||||
\right) \sum | |||||
|
zk | |
k |
n![zn]\exp\left(log
1 | |
1-z |
-
| |||||
\sum | |||||
|
infty | |||||
\right) \sum | |||||
|
zk | |
k |
n![zn]
1 | |
1-z |
\exp\left(-
| |||||
\sum | |||||
|
infty | |||||
\right) \sum | |||||
|
zk | |
k |
= n![zn]
1 | |
1-z |
infty | |
\sum | |
m=0 |
(-1)m | |
m! |
\left(
| |||||
\sum | |||||
|
\right)m+1
The exponent of
z
m+1
\lfloor | n |
2 |
\rfloor
m>0
[zn].
It follows that the answer is
n![zn]
1 | |
1-z |
| |||||
\sum | |||||
|
= n!
n | |||||
\sum | |||||
|
1 | |
k |
.
The sum has an alternate representation that one encounters e.g. in the OEIS .
n | |
\sum | |
k=1 |
1 | |
k |
-
| |||||
\sum | |||||
k=1 |
1 | |
k |
n | |
= \sum | |
k=1 |
1 | |
k |
-
| |||||
2\sum | |||||
k=1 |
1 | |
2k |
n | |
= \sum | |
k=1\atopk even |
(1-2)
1 | |
k |
+
n | |
\sum | |
k=1\atopk odd |
1 | |
k |
n | |
n!\sum | |
k=1 |
(-1)k+1 | |
k |
\simn!log2.
We can use the disjoint cycle decomposition of a permutation to factorize it as a product of transpositions by replacing a cycle of length k by k − 1 transpositions. E.g. the cycle
(1 2 34)
(1 2) (2 3) (3 4)
b(k)
k-1
g(z,u)=\left(
1 | |
1-uz |
\right)1/u
and
\partial | |
\partialu |
g(z,u)|u=1=
1 | |
1-z |
\sumk\ge(k-1)
zk | = | |
k |
z | |
(1-z)2 |
-
1 | |
1-z |
log
1 | |
1-z |
.
Hence the expected number of transpositions
T(n)
T(n)=n-Hn
where
Hn
nth
logn
Note that
g(z,u)
(-1)mn! [zn][um]g(z,u)=\left[\begin{matrix}n\ n-m\end{matrix}\right]
To see this, note that the above is equivalent to
(-1)n+mn! [zn][um]g(z,u)|u=1/u|z=uz=\left[\begin{matrix}n\ m\end{matrix}\right]
and that
[um]g(z,u)|u=1/u|z=uz= [um]\left(
1 | |
1-z |
\right)u=
1 | |
m! |
\left(log
1 | |
1-z |
\right)m,
which we saw to be the EGF of the unsigned Stirling numbers of the first kind in the section on permutations consisting of precisely m cycles.
We select a random element q of a random permutation
\sigma
b(k)
k2
\partial | |
\partialu |
g(z,u)|u=1=
1 | |
1-z |
\sumk\gek2
zk | = | |
k |
1 | |
1-z |
z | |
(1-z)2 |
=
z | |
(1-z)3 |
.
Hence the expected length of the cycle that contains q is
1 | |
n |
[zn]
z | |
(1-z)3 |
=
1 | |
n |
1 | |
2 |
n(n+1)=
1 | |
2 |
(n+1).
This average parameter represents the probability that if we again select a random element of
[n]
b(k)
m
m=k
\partial | |
\partialu |
g(z,u)|u=1=
1 | |
1-z |
\sumk\geb(k)
zk | = | |
k |
1 | |
1-z |
m
zm | |
m |
=
zm | |
1-z |
.
It follows that the probability that a random element lies on a cycle of length m is
1 | |
n |
[zn]
zm | |
1-z |
=\begin{cases}
1 | |
n |
,&ifn\gem\ 0,&otherwise. \end{cases}
Select a random subset Q of [''n''] containing m elements and a random permutation, and ask about the probability that all elements of Q lie on the same cycle. This is another average parameter. The function b(k) is equal to
\begin{matrix}{k\choosem}\end{matrix}
\begin{matrix}{k\choosem}\end{matrix}
\begin{matrix}{k\choosem}=0\end{matrix}
\partial | |
\partialu |
g(z,u)|u=1=
1 | |
1-z |
\sumk\ge{k\choosem}
zk | = | |
k |
1 | |
1-z |
1 | |
m |
zm | = | |
(1-z)m |
1 | |
m |
zm | |
(1-z)m+1 |
.
Averaging out we obtain that the probability of the elements of Q being on the same cycle is
{n\choosem}-1[zn]
1 | |
m |
zm | |
(1-z)m+1 |
= {n\choosem}-1
1 | |
m |
[zn-m]
1 | |
(1-z)m+1 |
or
1 | |
m |
{n\choosem}-1{(n-m) + m\choosem}=
1 | |
m |
.
In particular, the probability that two elements are on the same cycle is 1/2.
We may use the Flajolet–Sedgewick fundamental theorem directly and compute more advanced permutation statistics. (Check that page for an explanation of how the operators we will use are computed.) For example, the set of permutations containing an even number of even cycles is given by
\operatorname{SET}(\operatorname{CYC}\operatorname{odd
Translating to exponential generating functions (EGFs), we obtain
\exp\left(
1 | |
2 |
log
1+z | |
1-z |
\right) \cosh\left(
1 | |
2 |
log
1 | |
1-z2 |
\right)
or
1 | |
2 |
\exp\left(
1 | |
2 |
\left(log
1+z | |
1-z |
+log
1 | |
1-z2 |
\right)\right) +
1 | |
2 |
\exp\left(
1 | |
2 |
\left(log
1+z | |
1-z |
-log
1 | |
1-z2 |
\right)\right).
This simplifies to
1 | |
2 |
\exp\left(
1 | |
2 |
log
1 | \right) + | |
(1-z)2 |
1 | |
2 |
\exp\left(
1 | |
2 |
log(1+z)2\right)
or
1 | |
2 |
1 | |
1-z |
+
1 | |
2 |
(1+z) = 1+z+
1 | |
2 |
z2 | |
1-z |
.
This says that there is one permutation of size zero containing an even number of even cycles (the empty permutation, which contains zero cycles of even length), one such permutation of size one (the fixed point, which also contains zero cycles of even length), and that for
n\ge2
n!/2
Consider what happens when we square a permutation. Fixed points are mapped to fixed points. Odd cycles are mapped to odd cycles in a one-to-one correspondence, e.g.
(1 8 9 11 13)
(1 9 13 8 11)
(5 13 6 9)
(5 6) (9 13)
\operatorname{SET}(\operatorname{CYC}\operatorname{odd}(l{Z})) \operatorname{SET}\operatorname{even}(\operatorname{CYC}=2(l{Z})) \operatorname{SET}\operatorname{even}(\operatorname{CYC}=4(l{Z})) \operatorname{SET}\operatorname{even}(\operatorname{CYC}=6(l{Z})) …
which yields the EGF
\exp\left(
1 | |
2 |
log
1+z | |
1-z |
\right) \prodm\ge\cosh
z2m | = \sqrt{ | |
2m |
1+z | |
1-z |
The types of permutations presented in the preceding two sections, i.e. permutations containing an even number of even cycles and permutations that are squares, are examples of so-called odd cycle invariants, studied by Sung and Zhang (see external links). The term odd cycle invariant simply means that membership in the respective combinatorial class is independent of the size and number of odd cycles occurring in the permutation. In fact we can prove that all odd cycle invariants obey a simple recurrence, which we will derive. First, here are some more examples of odd cycle invariants.
This class has the specification
\operatorname{SET}(\operatorname{CYC}\operatorname{odd}(l{Z})) \left(\operatorname{SET}=3(\operatorname{CYC}=2(l{Z}))+ \operatorname{CYC}=2(l{Z})\operatorname{CYC}=4(l{Z})+ \operatorname{CYC}=6(l{Z}) \right)
and the generating function
\sqrt{ | 1+z |
1-z |
The first few values are
0,0,0,0,0,225,1575,6300,56700,425250,4677750,46777500,608107500,\ldots
This class has the specification
\operatorname{SET}(\operatorname{CYC}\operatorname{odd}(l{Z})) \left(\operatorname{SET}\ge(\operatorname{CYC}=2(l{Z}))+ \operatorname{SET}\ge(\operatorname{CYC}=4(l{Z}))+ \operatorname{SET}\ge(\operatorname{CYC}=6(l{Z}))+ … \right)
and the generating function
\sqrt{ | 1+z |
1-z |
There is a semantic nuance here. We could consider permutations containing no even cycles as belonging to this class, since zero is even. The first few values are
0,1,3,15,75,405,2835,22155,199395,1828575,\ldots
This class has the specification
\operatorname{SET}(\operatorname{CYC}\operatorname{odd}(l{Z})) \operatorname{SET}(\operatorname{CYC}=2(l{Z})+\operatorname{CYC}=4(l{Z}))
and the generating function
\sqrt{ | 1+z |
1-z |
The first few values are
1,2,6,24,120,600,4200,28560,257040,2207520,24282720,258128640,\ldots
Observe carefully how the specifications of the even cycle component are constructed. It is best to think of them in terms of parse trees. These trees have three levels. The nodes at the lowest level represent sums of products of even-length cycles of the singleton
l{Z}
g(z)=h(z)\sqrt{
1+z | |
1-z |
where
h(z)
1 | |
1+z |
g(z)=h(z)
1 | |
\sqrt{1-z2 |
is even, too, and hence
1 | |
1+z |
g(z)=
1 | |
1-z |
g(-z) or (1-z) g(z)=(1+z) g(-z).
Letting and extracting coefficients, we find that
g2m+1 | |
(2m+1)! |
-
g2m | |
(2m)! |
= -
g2m+1 | |
(2m+1)! |
+
g2m | |
(2m)! |
or 2
g2m+1 | |
(2m+1)! |
=2
g2m | |
(2m)! |
which yields the recurrence
g2m+1=(2m+1)g2m.
A link to the Putnam competition website appears in the section External links.The problem asks for a proof that
\sum | |
\pi\inSn |
\sigma(\pi) | |
\nu(\pi)+1 |
=(-1)n+1
n | |
n+1 |
,
where the sum is over all
n!
[n]
\sigma(\pi)
\pi
\sigma(\pi)=1
\pi
\sigma(\pi)=-1
\pi
\nu(\pi)
\pi
Now the sign of
\pi
\sigma(\pi)=\prodc\in\pi(-1)|c|-1,
where the product is over all cycles c of
\pi
Hence we consider the combinatorial class
\operatorname{SET}(-l{Z}+l{V}l{Z}+ \operatorname{CYC}=1(l{Z})+l{U}\operatorname{CYC}=2(l{Z})+
2\operatorname{CYC} | |
l{U} | |
=3 |
(l{Z})+
3\operatorname{CYC} | |
l{U} | |
=4 |
(l{Z})+ … )
where
l{U}
l{V}
g(z,u,v)= \exp\left(-z+vz+\sumk\geuk-1
zk | |
k |
\right)
\exp\left(-z+vz+
1 | log | |
u |
1 | |
1-uz |
\right)= \exp(-z+vz)\left(
1 | |
1-uz |
\right)1/u.
Now we have
n![zn]g(z,-1,v)=n![zn]\exp(-z+vz)(1+z)=
\sum | |
\pi\inSn |
\sigma(\pi)v\nu(\pi)
and hence the desired quantity is given by
n![zn]
1 | |
\int | |
0 |
g(z,-1,v)dv=
\sum | |
\pi\inSn |
\sigma(\pi) | |
\nu(\pi)+1 |
.
Doing the computation, we obtain
1 | |
\int | |
0 |
g(z,-1,v)dv=\exp(-z)(1+z)\left(
1 | |
z |
\exp(z)-
1 | |
z |
\right)
or
\left( | 1 |
z |
+1\right)\left(1-\exp(-z)\right)=
1 | |
z |
+1-\exp(-z)-
1 | |
z |
\exp(-z).
Extracting coefficients, we find that the coefficient of
1/z
n
n![zn]\left(-\exp(-z)-
1 | |
z |
\exp(-z)\right)= n!\left(-(-1)n
1 | |
n! |
-(-1)n+1
1 | |
(n+1)! |
\right)
or
(-1)n+1\left(1-
1 | |
n+1 |
\right)=(-1)n+1
n | |
n+1 |
,
which is the desired result.
As an interesting aside, we observe that
g(z,u,v)
n x n
d(n)=\det(An)= \begin{vmatrix} a&&b&&b&& … &&b\\ b&&a&&b&& … &&b\\ b&&b&&a&& … &&b\\ \vdots&&\vdots&&\vdots&&\ddots&&\vdots\\ b&&b&&b&& … &&a \end{vmatrix}.
where
a,b\ne0
\det(A)=
\sum | |
\pi\inSn |
\sigma(\pi)
n | |
\prod | |
i=1 |
Ai,.
Now the value of the product on the right for a permutation
\pi
afbn-f
\pi
d(n)=bnn![zn]g\left(z,-1,
a | |
b |
\right)= bnn![zn]\exp\left(
a-b | |
b |
z\right)(1+z)
which yields
bn\left(
a-b | |
b |
\right)n+bnn\left(
a-b | |
b |
\right)n-1= (a-b)n+nb(a-b)n-1
and finally
d(n)=(a+(n-1)b)(a-b)n-1.
Here we seek to show that this difference is given by
(-1)n(n-2)!
Recall that the sign
\sigma(\pi)
\pi
\sigma(\pi)=\prodc\in\pi(-1)|c|-1
\pi
It follows that the combinatorial species
l{Q}
l{Q}= \operatorname{SET}(l{V}\operatorname{CYC}1(l{Z}) +l{U}l{V}\operatorname{CYC}=2
2l{V}\operatorname{CYC} | |
(l{Z})) +l{U} | |
=3 |
3l{V}\operatorname{CYC} | |
(l{Z}) +l{U} | |
=4 |
4l{V}\operatorname{CYC} | |
(l{Z}) +l{U} | |
=5 |
(l{Z}) + …)
l{U}
l{V}
Translating to generating functions we have
Q(z,u,v)= \exp\left(v
z | |
1 |
+vu
z2 | |
2 |
+
| ||||
vu |
+
| ||||
vu |
+
| ||||
vu |
+ … \right).
Q(z,u,v)=\exp\left(
v | \left( | |
u |
zu | |
1 |
+
z2u2 | |
2 |
+
z3u3 | |
3 |
+
z4u4 | |
4 |
+
z5u5 | |
5 |
+ … \right)\right)
\exp\left( | v |
u |
log
1 | |
1-uz |
\right) =\left(
1 | |
1-uz |
| ||||
\right) |
.
Now the two generating functions
Q1(z,v)
Q2(z,v)
Q1(z,v)=
1 | |
2 |
Q(z,+1,v)+
1 | |
2 |
Q(z,-1,v)=
1 | \left( | |
2 |
1 | |
1-z |
| |||||
\right) | \left( |
1 | |
1+z |
\right)-v
Q2(z,v)=
1 | |
2 |
Q(z,+1,v)-
1 | |
2 |
Q(z,-1,v)=
1 | \left( | |
2 |
1 | |
1-z |
| |||||
\right) | \left( |
1 | |
1+z |
\right)-v.
We require the quantity
G(z,v)=\left.
d | |
dv |
(Q1(z,v)-Q2(z,v))\right|v=1
\left. | d | \left( |
dv |
1 | |
1+z |
\right)-v\right|v=1= -\left.log
1 | \left( | |
1+z |
1 | |
1+z |
\right)-v\right|v=1=-(1+z)log
1 | |
1+z |
.
Finally, extracting coefficients from this generating function, we obtain
-n![zn](1+z)log
1 | |
1+z |
=-n!\left(
(-1)n | |
n |
+
(-1)n-1 | |
n-1 |
\right)
-n!(-1)n-1\left(-
1 | |
n |
+
1 | |
n-1 |
\right) =n!(-1)n
n-(n-1) | |
n(n-1) |
n!(-1)n
1 | |
n(n-1) |
=(-1)n(n-2)!
Similar statistics are available for random endomorphisms on a finite set.[2] [3]