What's New
About the Project
NIST
32 Painlevé TranscendentsApplications

§32.14 Combinatorics

Let SN be the group of permutations π of the numbers 1,2,,N26.2). With 1m1<<mnN, π(m1),π(m2),,π(mn) is said to be an increasing subsequence of π of length n when π(m1)<π(m2)<<π(mn). Let N(π) be the length of the longest increasing subsequence of π. Then

32.14.1 limNProb(N(π)-2NN1/6s)=F(s),

where the distribution function F(s) is defined here by

32.14.2 F(s)=exp(-s(x-s)w2(x)dx),

and w(x) satisfies PII with α=0 and boundary conditions

32.14.3 w(x) Ai(x),
x+,
32.14.4 w(x) -12x,
x-,

where Ai denotes the Airy function (§9.2).

The distribution function F(s) given by (32.14.2) arises in random matrix theory where it gives the limiting distribution for the normalized largest eigenvalue in the Gaussian Unitary Ensemble of n×n Hermitian matrices; see Tracy and Widom (1994).

See Forrester and Witte (2001, 2002) for other instances of Painlevé equations in random matrix theory.