permutation statistics

foreword

note that this presentation is aimed at the general audience of my peers to which it's addressed, and so explains a great deal that the dissertation will either assume to be understood by the reader or contain in references on prerequisites.

sequences

here, we will consider sequences \(a(n)\) that count structures with \(n\) nodes

nodes are considered 'labelled'; swapping the positions of two nodes produces a distinct object.

but in some cases (ie. when the structures are sets), there are no positions to swap

exponential generating functions

we encode sequences to their e.g.f.s by taking \(A(x)=\sum_{n=0}^\infty a(n)\frac{x^n}{n!}\)

analytic functions correspond uniquely with their series expansions, and we will retrieve sequences back out of them!

A generating function is a clothesline on which we hang up a sequence of numbers for display.

-Herbert S. Wilf, author of generatingfunctionology

specifically, we write \(a(n)=\left[\frac{x^n}{n!}\right]A(x)\) to mean \(\left(\frac d{dx}\right)^nA(x)\big|_{x=0}\).

(usually, I would introduce you to ordinary generating functions first, where we would just use \([x^n]A(x)\), but those count structures that partition unlabelled nodes (ie. units in a quantity); ie. the number of ways to partition \(n\) pence into 1p,2p,5p,10p coins is \([x^n]\frac1{(1-x)(1-x^2)(1-x^5)(1-x^{10})}\))

(however, we are somewhat short upon time; however, you will see arrays \(a(n,k)=\left[\frac{x^n}{n!}y^k\right]A(x,y)\) later on, which are e.g.f.-o.g.f. hybrids)

(though since you basically never see e.g.f.-e.g.f. arrays, so in the OEIS people refer to these hybrid e.g.f.-o.g.f.s as just e.g.f. of the array)

recapping some basic calculus

recall that \(\frac d{dx} x^n=nx^{n-1}\); for us, it will be more useful to think of it as \(\frac d{dx}\frac{x^n}{n!}=\frac{x^{n-1}}{(n-1)!}\), ie. \(\frac d{dx}(\underbrace{0,0,\ldots,0}_{n\ 0\text{s}},1)=(\underbrace{0,\ldots,0}_{n-1\ 0\text{s}},1)\); \(\left[\frac{x^n}{n!}\right]\)

recall that \(\frac {de^x}{dx}=e^x\); setting \(y=e^x\), this becomes \(\frac dy{d\log(y)}=y\). Reciprocating, \(\frac d{dy}\log(y)=\frac1y\), and (via the chain rule) \(\frac d{dy}\log\left(\frac1{1-y}\right)=\frac1{1-y}\).

\(\frac1{1-y}=1+y\frac1{1-y}\), so by induction (replacing the occurrence of the left side in the right side with the entire right side) \(\frac1{1-y}=1+y(1+y\frac1{1-y})=1+y(1+y(1+y(\ldots)))=1+y+y^2+\ldots\)

this tells us three important facts about e.g.f.s!

\(\left[\frac{x^n}{n!}\right]e^x=1\)

there is \(1\) way to put \(n\) objects into an unordered set

\(\left[\frac{x^n}{n!}\right]\frac1{1-x}=n!\)

there are \(n!\) ways (permutations) to put \(n\) objects into an ordered list

\(\left[\frac{x^n}{n!}\right]\log\left(\frac1{1-x}\right)=(n-1)!\)

there are \((n-1)!\) ways to put \(n\) objects into a cyclically-ordered list

(we group the \(n!\) permutations into equivalence classes of \(n\) each under the \(n\) cyclic shifts we can do to them)

we consider sets of structures to be their e.g.f.s, in a sense

as combinatorialists, we will name the sequences \(\mathrm{sets}(n)=1,\mathrm{cycles}(n)=(n-1)!,\mathrm{lists}(n)=n!\); if two sets of structures have sequences with the same \(n\)th term (ie. they have the same number of structures on \(n\) nodes), we say they are the same set, since there's a bijection between them that preserves cardinality (\(n\)).

this will make sense more concretely on the next page do not worry

Faà di Bruno's formula

the first reason why we will find e.g.f.s useful is that putting them inside each other is meaningful!

if \(a(n)=\left[\frac{x^n}{n!}\right]A(x)\) counts [structure a]s with \(n\) nodes, and \(b(n)=\left[\frac{x^n}{n!}\right]B(x)\) counts [structure b]s with \(n\) nodes, then \(a(b)(n)=\left[\frac{x^n}{n!}\right]A(B(x))\) counts [structure a]s whose nodes are replaced with [structure b]s which in turn contain nodes

note that when \(b(0)\ne0\), \(a\)'s sum must be finite in order for \(a(b)\)'s terms to converge, since you can otherwise have infinitely many terms by finding [structure a]s and filling them with empty [structure b]s from \(b(0)\)

aforepromised concreteness: with the functions defined before, \(\mathrm{sets}(\mathrm{cycles})n=\left[\frac{x^n}{n!}\right]\left(\exp\left(\log\left(\frac1{1-x}\right)\right)=\frac1{1-x}\right)=\mathrm{lists}(n)\), ie. we have a surjection between sets of cycles and lists.

we can add in a \(y\) coefficient that counts the cycles! \(\mathrm{Sets}(y\mathrm{Cycles}(x))=\exp\left(y\log\left(\frac1{1-x}\right)\right)=\frac1{(1-x)^y}\), then the coefficient \(\left[\frac{x^n}{n!}y^k\right]\) inside this counts permutations with \(n\) nodes and \(k\) cycles.

the generalised binomial theorem

the binomial theorem says \((1+x)^n=\sum_{k=0}^\infty{n\choose k}x^k\) (when \(|x|\lt1\), however we only care about it as a generating function so radius of convergence is unimportant to us).

in fact, by writing \({n\choose k}=\frac{n!}{k!(n-k)!}\) and then using \(x!=\Gamma(x+1)=\int_{t=0}^\infty\frac{t^x}{e^t}\ dt\) (holds for \(x=0\); doing integration by parts shows it abides by the same recurrence relation, and (importantly) can be evaluated at \(x\) that are negative or noninteger) we can continue it backwards.

(btw this nice plot is from a nice writeup by Peter Luschny on this subject, where he goes on a tangent about how Sage (on the right) is bad for making it zero in one quartile; this has bitten me in the back sometimes)

for \(-n\) a negative integer, the integral diverges (due to any neighbourhood of \(t=0\) contributing infinitely much) so a fool would say that in this case \((-n)!=\infty\), but we can take the coefficient of \(\infty\) (the coefficient \([x^{-1}](-n+x)!\) in the expansion; for those who have done complex integration, the residue of \(x!\) at \(x=-n\)) as \(\frac{(-1)^{n-1}}{(n-1)!}\).

so if we treat the negative parts in \({-n\choose k}=\frac{(-n)!}{k!(-n-k)!}\) as being residues instead of numbers (cancel out the \(\infty\)s), we can rearrange it into \((-1)^k{n+k-1\choose k}\).

things we can do with \(\frac1{(1-x)^y}\)

this extension of the binomial coefficient continues to abide by the binomial theorem! \(\frac1{(1-x)^n}=\sum_{k=0}^\infty{n+k-1\choose k}x^k\). (Replacing \(x\) with \(-x\) on the left side replaces \(x^k\) with \((-x)^k\) on the right side, conveniently cancelling out the \((-1)^k\) we already had.)

this has a combinatorial meaning in ordinary o.g.f.s btw

\([x^k](1+x)^n={n\choose k}\) is the number of ways to make a set of \(k\) elements by drawing from a set of \(n\).

\([x^k]\frac1{(1-x)^n}={n+k-1\choose k}\) is the number of ways to make a multiset of \(k\) elements by drawing with replacement from a set of \(n\).

this comes up so often in combinatorics that sometimes people define \(\left(\!{n\choose k}\!\right)={n+k-1\choose k}\) (pronounced \(n\) multichoose \(k\)) for it to clean up formulas

anyway, we are interested in \(\frac1{(1-x)^y}\) as an e.g.f., not o.g.f.!

\(\left[\frac{x^n}{n!}\right]\frac1{(1-x)^y}=n!\left(\!{y\choose n}\!\right)=\frac{(y+n-1)!}{(y-1)!}=\underbrace{y(y+1)(y+2)\ldots(y+n-1)}_{n\ \text{factors}}\).

this also has its own syntax, \(y^\overline n\) (as opposed to \(y^\underline n=\frac{y!}{(y-n)!}=\underbrace{y(y-1)(y-2)\ldots(y-n+1)}_{n\ \text{factors}}\)).

so, to recap, the number of \(n\)-element \(k\)-cycle permutations is \(\left[\frac{x^n}{n!}y^k\right]\frac1{(1-x)^y}=[y^k]y^\overline n\).

logarithmic differentiation: a cool trick you may know from probability

given the o.g.f. \(F(x)\) of a p.d.f. \(f(n)=\mathrm P(X=n)\), taking the random variable's expectation (average of possible outputs, weighted by probability) \(\mathrm E[X]=\sum_{n=0}^\infty nf(n)\) can be done by evaluating \(F'(1)\).

meanwhile, for us, since we're dealing with not-quite-probability distributions that don't sum to \(1\), we need to divide by the sum of the weights, which is \(F(1)\).

the expression \(\frac{F'(1)}{F(1)}\) (the expected value of a randomly-chosen element of the set counted by \(F\)) has another representation, as \(\frac d{dx}\log F(x)\big|_{x=1}\).

note that in general, higher-order moments can be taken; for instance, \(\mathrm E[X^2=X^\underline 1+X^\underline 2]=\frac{F'(1)}{F(1)}+\frac{F''(1)}{F(1)}\), and \(\mathrm E[X^3=X^\underline 1+3X^\underline 2+X^\underline 3]=\frac{F'(1)}{F(1)}+3\frac{F''(1)}{F(1)}+\frac{F'''(1)}{F(1)}\).

so, if we want to know the total number of cycles in all \(n\)-permutations, we need only take \(\log\left(\left[\frac{x^n}{n!}\right]\frac d{dy}\frac1{(1-x)^y}\right)\big|_{y=1}\) (and so for the expectation of a random \(n\)-permutation only \([x^n]\)); the \(\frac d{dy}\) in question is \(\frac{\log(\frac1{1-x})}{(1-x)^y}\), so by setting \(y=1\) we have \(\frac{\log(\frac1{1-x})}{1-x}\). We know from before that \([x^i]\) in the numerator is \(\frac1i\), and division by \(1-x\) takes the partial sum of an o.g.f.'s sequence, so the expected cycle count is \(\sum_{i=1}^n\frac1i=H_n\).

selectively ignoring most of the derivatives we have to do

we can also be tautological sneakier, and write out \(\frac1{(1-x)^y}=\exp\left(y\log\left(\frac1{1-x}\right)\right)=\exp\left(\sum_{i=1}^\infty y\frac{x^i}i\right)=\prod_{i=1}^\infty\exp\left(y\frac{x^i}i\right)=\prod_{i=1}^\infty\sum_{j=0}\frac{y^j\frac{x^{ij}}{i^j}}{j!}\).

here, the exponent of \(y\) in the \(i\)th multiplicand is the number of length-\(i\) cycles in a given permutation; we can replace each multiplicand's \(y\) with \(y_i\) to keep track of cycle counts for each length separately.

we can then choose a particular length \(l\), and set all \(y_{i\ne l}\) to \(1\) to only keep track of the \(y_l\).

\[\left(\sum_{j=0}\frac{y_l^j\frac{x^{lj}}{l^j}}{j!}\right)\prod_{i=1\atop i\ne l}^\infty\sum_{j=0}\frac{\frac{x^{ij}}{i^j}}{j!}=\frac{\exp\left(y_l\frac{x^l}l\right)}{\exp\left(\frac{x^l}l\right)}\frac1{1-x}=\frac{\exp\left((y_l-1)\frac{x^l}l\right)}{1-x}\]

to recap, this is now an e.g.f. from which the coeff-extraction \(\left[\frac{x^n}{n!}y_l^k\right]\) tells you the number of \(n\)-permutations with \(k\) \(l\)-cycles. (for \(l=1\) this is (n,k), for \(l=2\) (n,k))

differentiating with respect to \(y_l\) then setting \(y_l\) gives us \(\frac1l\frac{x^l}{1-x}\), which tells us that \(\mathrm E[\#(\mathrm{length-}l\ \mathrm{cycles\ in\ }n\mathrm{-perm})]=\begin{cases}\frac1l&n\ge l\\0&\mathrm{else}\end{cases}\).

this gives the previous fact (that the expected count of all cycles in an \(n\)-perm is \(H_n\)) as a corollary, since we can just sum the expectations over \(l\), even though the random variables defined by different \(l\)s aren't independent of each other. (However, expectations are special in this regard; for orders \(o>1\), we can't get the \(o\)th moment of a sum in terms of the \(\le o\)th moments of the constituent codependent variables, since then we also have to consider .)

a "D-finite" recurrence

it will be increasingly useful to use a notation for \({n\brack k}=[y^k]y^\overline n\) just like \({n\choose k}=[y^k](1+y)^n\) (pronounced 'n cycle k' like 'n choose k').

( was the first to propose this in 1935; Donald Knuth gave a review of various notation proposals (which is also a good introduction to the subject of Stirling numbers, in the contexts in which he used them), in which he concluded this was most appropriate for most purposes, and (being the author of TeX) implemented it there as {n\brack k}.)

the cycle numbers have a recurrence, much alike the choose numbers' \({n+1\choose k}={n\choose k-1}+{n\choose k}\)!

note that this recurrence can be interpreted as "to make a \(k\)-subset of an \(n+1\)-set, consider the \(n+1\)th element separately and either (add it onto a \(k-1\)-subset of an \(n\)-set) or (discard it and use a \(k\)-subset of an \(n\)-set)"; we want something analogous for permutations!

the analogue in question is \({n+1\brack k}=n{n\brack k}+{n\brack k-1}\); this is equivalent to the recurrence \(y^\overline{n+1}=(n+x)y^\overline n\) about the row o.g.f., or the differential equation \(f_x=xf_x+yf\) which (together with boundary conditions) characterises the e.g.f. \(f=\frac1{(1-x)^y}\), both of which are routine to derive/verify

the combinatorial interpretation is we can make a permutation in \({n+1\brack k}\) by adding an \(n+1\)th element

to a permutation in \({n\brack k}\) in \(n\) ways, inside one of the existing cycles

(ie. the permutation maps it to one of the \(n\) existing elements, and maps that existing element's existing preimage to it)

to a permutation in \({n\brack k-1}\) in one way, mapped to itself

note that this tells us that the centre of mass of the triangle is shifted right by \(\frac1n\) in the \(n\)th row, ie. it also explains the expected cycle-count, but if I told you this first it would be too easy and you wouldn't listen to the longer one about cycle counts by length

higher moments from higher-order derivatives

for \(n\ge o\), \(n^\underline o[x^n]f(x)=[x^{n-o}]\left(\frac d{dx}\right)^of(x)\), which means that for a random variable \(X\) whose probability distribution has p.g.f. \(f(x)\), \(\mathrm E[X^\underline o]=\left(\frac d{dx}\right)^of(x)\big|_{x=1}\).

we know from before that \(\frac d{dy}\log\left(\frac1{(1-x)^y}\right)=\frac{\log(\frac1{1-x})}{(1-x)^y}\), which tells us that \(\frac d{dy}y^\overline n=y^\overline n(H_{y+n-1}-H_{y-1})\).

it is useful to write \(y^\overline n=\frac{(y+n-1)!}{(y-1)!}\), then we can get out a formula for the factorial's power series from \(x!=x\cdot(x-1)!\); by taking the logarithmic derivative of both sides (writing \(f(x)=\log(x!)\)) we have \(f'(x)=\frac1x+f'(x-1)\); differentiating some more, \(f^{(n)}(x)=\frac{(-1)^{n-1}(n-1)!}{x^n}+f^{(n)}(x-1)\).

that is to say, \(f^{(n)}(x)=(-1)^{n-1}(n-1)!H^{(n)}_x+c_n\), where \(H^{(n)}_x=\sum_{k=0}^x\frac1{k^n}\) is a generalised harmonic number (and the sum is analytically continued to noninteger terms).

finding the \(c_n\) (actually unnecessary for us)

in fact, \(\lim_{x\to\infty}\frac d{dx}H_x=0\) (due to \(\lim_{x\to\infty}H_x-\log(x)=0\), their respective monotonicities and the latter's smoothness), so the \(c_2\) must be such that \(f^{(2)}(x)\sim0\); in fact, \(\lim_{x\to\infty}H^{(n)}_x=\zeta(n)\) for \(n>1\).

for \(n=1\), meanwhile, Stirling's approximation tells us \[f(x)=\left(x+\frac12\right)\log(x)-x+c+O(x^{-1})\\ \Downarrow\\ f'(x)=\log(z)+\frac1{2z}+O(z^{-2})\] and so \(f'(x)=H_x+?\) together with \(H_x=\log(x)+\gamma+O(x^{-2})\) forces us to choose \(?=-\gamma\).

these two facts give \(f^{(n)}(x)=(n-1)!(-1)^{n-1}\left(H^{(n)}_x-\begin{cases}\gamma&n=1\\\zeta(n)&\mathrm{else}\end{cases}\right)\).

so, about \(x=x_0\) with radius of convergence \(\min(|x_0+1|,|x_0+2|,\ldots)\), \(x!=\exp\left(\sum_{n=0}^\infty((-1)^{n-1}(n-1)!H^{(n)}_{x_0}+c_n)(x-x_0)^n\right)\).

the reason for the \(c_n\)s being unnecessary is that we're concerned with fractions of factorials, where they get cancelled; \(\frac{(x+x_{\mathrm{num}})!}{(x+x_{\mathrm{den}})!}=\exp\left(\sum_{n=0}^\infty((-1)^{n-1}(n-1)!(H^{(n)}_{x_{\mathrm{num}}}-H^{(n)}_{x_{\mathrm{den}}}))x^n\right)\).

we plug this into Faà di Bruno to get out \[\frac{\left(\frac d{dx}\right)^n\frac{(x+x_{\mathrm{num}})!}{(x+x_{\mathrm{den}})!}}{\frac{(x+x_{\mathrm{num}})!}{(x+x_{\mathrm{den}})!}}=\sum_{p\in\mathrm{perms}(n)}\prod_{c\in p}H^{(|c|)}_{d+x}-H^{(|c|)}_{n+x}\]

which is useful to us, since for the random variable \(C_n\) the number of cycles in an \(n\)-permutation, it gives us \[\mathbb E\left[{C_n\choose k}\right]=\sum_{p\in\mathrm{perms}(k)}\prod_{c\in p}(-1)^{|c|-1}H^{(|c|)}_n\] directly

(the \(c\in p\) iterates over cycles; the sign of each product's contribution equals the sign of the permutation it corresponds with)

as a corollary, this gives that \(\mathrm{Var}[C_n]=H_n-H^{(2)}_n\), ie. we have a central limit theorem on random permutations; the standard deviation of cycle count grows only like the sqrt of expectation!

higher moments (contd.)

we in fact have a simpler (and possibly more surprising) characterisation of \(\mathbb E\left[{C_n\choose k}\right]\) than that; consider the sum over \(S_n\) instead of the average, ie. \(S_{n,k}:=n![\mathbb E\left[{C_n\choose k}\right]=\sum_{i=0}^n\binom ik{n\brack i}\) (counting ways to form a permutation with \(\ge k\) cycles, then choose \(k\) of the cycles).

if we keep these chosen cycles, and concatenate the rest (shifted to have their maximal element first, then ordered in ascending order of maximal element) to a single list, append an \(n+1\)th element to it and join it back into a cycle, we construct a permutation of \([n+1]\) with \(k+1\) cycles, ie. we have \(S_{n,k}={n+1\brack k+1}\).

(this is somewhat akin to the 'hockey stick' identity for binomial coefficients; see this math.se post (in which this is \((1a)\)) and my page for further discussion (including illustrative proofs by generating functions) and many other such analogues)