# §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 and 32

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

 32.14.2 $F(s)=\exp\left(-\int_{s}^{\infty}(x-s)w^{2}(x)\mathrm{d}x\right),$ ⓘ Symbols: $\mathrm{d}\NVar{x}$: differential of $x$, $\exp\NVar{z}$: exponential function, $\int$: integral, $x$: real and $F(s)$: distribution function Referenced by: §32.14 Permalink: http://dlmf.nist.gov/32.14.E2 Encodings: TeX, pMML, png See also: Annotations for 32.14 and 32

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

 32.14.3 $\displaystyle w(x)$ $\displaystyle\sim\mathrm{Ai}\left(x\right),$ $x\to+\infty$, ⓘ Symbols: $\mathrm{Ai}\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 and 32 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 and 32

where $\mathrm{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\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.