# §32.14 Combinatorics

Let $S_{N}$ be the group of permutations $\boldsymbol{\pi}$ of the numbers $1,2,\dots,N$26.2). With $1\leq m_{1}<\dots, $\boldsymbol{\pi}(m_{1}),\boldsymbol{\pi}(m_{2}),\dots,\boldsymbol{\pi}(m_{n})$ is said to be an increasing subsequence of $\boldsymbol{\pi}$ of length $n$ when $\boldsymbol{\pi}(m_{1})<\boldsymbol{\pi}(m_{2})<\dots<\boldsymbol{\pi}(m_{n})$. Let $\ell_{N}(\boldsymbol{\pi})$ be the length of the longest increasing subsequence of $\boldsymbol{\pi}$. Then

 32.14.1 $\lim_{N\to\infty}\mathrm{Prob}\left(\frac{\ell_{N}(\boldsymbol{\pi})-2\sqrt{N}% }{N^{1/6}}\leq s\right)=F(s),$ Symbols: $\boldsymbol{\pi}(m)$: permutations, $\ell_{N}(\boldsymbol{\pi})$: length and $F(s)$: distribution function Permalink: http://dlmf.nist.gov/32.14.E1 Encodings: TeX, pMML, png See also: Annotations for 32.14

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

 32.14.2 $F(s)=\mathop{\exp\/}\nolimits\!\left(-\int_{s}^{\infty}(x-s)w^{2}(x)\mathrm{d}% x\right),$

and $w(x)$ satisfies $\mbox{P}_{\mbox{\scriptsize II}}$ with $\alpha=0$ and boundary conditions

 32.14.3 $\displaystyle w(x)$ $\displaystyle\sim\mathop{\mathrm{Ai}\/}\nolimits\!\left(x\right),$ $x\to+\infty$, Symbols: $\mathop{\mathrm{Ai}\/}\nolimits\!\left(\NVar{z}\right)$: Airy function, $\sim$: asymptotic equality and $x$: real Permalink: http://dlmf.nist.gov/32.14.E3 Encodings: TeX, pMML, png See also: Annotations for 32.14 32.14.4 $\displaystyle w(x)$ $\displaystyle\sim\sqrt{-\tfrac{1}{2}x},$ $x\to-\infty$, Symbols: $\sim$: asymptotic equality and $x$: real Permalink: http://dlmf.nist.gov/32.14.E4 Encodings: TeX, pMML, png See also: Annotations for 32.14

where $\mathop{\mathrm{Ai}\/}\nolimits$ 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\times n$ Hermitian matrices; see Tracy and Widom (1994).

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