We begin with the definition of generating tree. Since we are interested in the study of permutations, we restrict the definition to these specific objects. We need the following preliminary construction.
Definition. Given a permutation \(\sigma\in\mathcal{S}^n\) and an integer \(m\in [n+1],\) we denote by \(\sigma^{*m}\) the permutation obtained from \(\sigma\) by appending a new final value equal to \(m\) and shifting by +1 all the other values larger than or equal to \(m\).
We say that a family of permutations \(\mathcal{C}\) grows on the right if for every permutation \(\sigma\in\mathcal{S}\) such that \(\sigma^{*m}\in\mathcal{C}\), for some \(m\in [|\sigma|+1]\), then \(\sigma\in\mathcal{C}\). From now until the end we will only consider families of permutations that grow on the right, without explicitly saying it every time.
Definition. The generating tree for a family of permutations \(\mathcal{C}\) is the infinite rooted tree whose vertices are the permutations of \(\mathcal{C}\) (each appearing exactly once in the tree) and such that permutations of size \(n\) are at level \(n\) (the level of a vertex being the distance from the root plus one). The children of some permutation \(\sigma\in\mathcal{C}\) correspond to the permutations obtained by appending a new final value to \(\sigma\).
We now give an example of a generating tree for the family of permutations avoiding the patterns 1423 and 4123.
Example. The first levels of the generating tree for \(\{1423,4123\}\)-avoiding permutations are drawn in the figure below. Note that every child of a permutation is obtained by appending a new final value. For instance, the permutation \(321\) on the left-hand side of the third level is obtained from the permutation \(21\) by appending a new final value equal to 1.
Definition. Let \(S\) be a set and assume there exists an \(S\)-valued statistics on the permutations of \(\mathcal{C},\) whose value determines the number of children in the generating tree and the values of the statistics for the children. Then we give labels to the objects of \(\mathcal{C}\) which indicate the value of the statistics. The associated succession rule is then given by the label \(\lambda\) of the root and, for any label \(k,\) the labels \(e_1(k),\dots,e_{h(k)}(k)\) of the \(h(k)\) children of an object labeled by \(k.\) In full generality, the associated succession rule is represented by the formula
\(
\begin{cases}
\text{Root label}: (\lambda) \\
(k)\to (e_1{\scriptstyle(k)}),\dots,(e_{h(k)}{\scriptstyle(k)}).
\end{cases}
\)
The set of labels appearing in a generating tree is denoted by \(\mathcal{L}\) and for all \(k\in\mathcal{L},\) the multiset of labels of the children \(\{e_1(k),\dots,e_{h(k)}(k)\}\) is denoted by \(\text{CL}(k).\)
We point out that we are not assuming that the children labels \(e_1(k),\dots,e_{h(k)}(k)\) appearing in the succession rule are distinct (notice for instance that the label \((k+1)\) is produced twice from the label \((k)\) in the example in the figure above). For each pair of labels \((k,k’)\in\mathcal{L}^2\), we denote by \(\text{mult}_{k}(k’)\) the number of indices \(i\) such that \( e_{i}(k)=k’.\)
There is a natural bijection between permutations in a family encoded by a generating tree and the set of paths in the tree starting at the root. We simply associate to the endpoint of each path the permutation appearing in that vertex. We may further identify each path in the tree with the list of labels appearing on this path, but this requires to distinguish the potential repeated labels in the succession rule. More precisely, for each label \(k\in\mathcal{L}\) and for each element \(k’\in\text{CL}(k)\) such that \(\text{mult}_{k}(k’)>1,\) we distinguish the repeated labels by painting them with different colors (say colors \(\{1,\dots,\text{mult}_{k}(k’)\}\)). Then the colored succession rule is represented as
\(
\begin{cases}
\label{eq:colored_succ_rule}
\text{Root label}: (\lambda) \\
(k)\to (e^*_1{\scriptstyle(k)}),\dots,(e^*_{h(k)}{\scriptstyle(k)}),
\end{cases}
\)
where the stars recall that the labels might be colored. We highlight that the colors and the values of the children labels depend only on the value of the parent label (and not on the color).
In this way, every permutation of size \(n\) is bijectively encoded by a sequence of \(n\) (colored) labels \((k_1^*=\lambda,k_2^*,\dots,k_n^*)\) such that every pair of two consecutive labels, \((k_i^*,k_{i+1}^*),\) \(1\leq i\leq n-1,\) is consistent with the colored succession rule, i.e. for all \(1\leq i\leq n-1,\) there exist \(j=j(i)\in [1,h(k_i)]\) such that \(k_{i+1}^*=e_{j}^*(k_i)\). We denote by \(\text{G}\) this bijection between sequences of colored labels and permutations in the generating tree.
We can now formally state our main result. We first state three assumptions for a family of permutations \(\mathcal{C}\) encoded by a generating tree as above.
Assumption 1.
The generating tree has \(\mathbb{Z}\)-valued labels. We further require that the labels appearing in the generating tree are elements of \(\mathbb{Z}_{\geq\beta}\) for some \(\beta\in\mathbb{Z}\), except for the root, where the label is equal to \(\lambda=\beta-1\).
Let now \((\alpha_y)_{y\in\mathbb{Z}_{\leq 1}}\) be a probability distribution on \(\mathbb{Z}_{\leq 1}\) and \((c_y)_{y\in\mathbb{Z}_{\leq 1}}\) be a sequence of non-negative integers such that \(c_y\geq 1\) if and only if \(\alpha_y>0\). Denote by \({\textbf{Y}}^*\) the corresponding colored \(\mathbb{Z}_{\leq 1}\)-valued random variable having value-distribution equal to \((\alpha_y)_{y\in\mathbb{Z}_{\leq 1}}\) (i.e. \(\text{P}({\textbf{Y}}^*=y)=\alpha_y\) for all \(y\in\mathbb{Z}_{\leq 1}\)) and color-distribution defined as follows: conditioning on \(\{{\textbf{Y}}^*=y\}\) then \({\textbf{Y}}^*\) is painted uniformly at random with a color in \([c_y]\). We denote by \({\textbf{Y}}\) the uncolored version of \({\textbf{Y}}^*\).
Consider now a sequence \(({\textbf{Y}}^*_j)_{j\geq 1}\) of i.i.d. copies of \({\textbf{Y}}^*\) (we denote by \({\textbf{Y}_j}\) the uncolored version of \(\textbf{Y}_j^*\)). We define the random colored walk \(({\textbf{X}}_i)_{i\geq 1}\) as a random walk with values equal to
\(
{\textbf{X}}_i:= (\beta-1)+\sum_{j=1}^{i-1}{\textbf{Y}}_j,\quad\text{for all}\quad i\in\mathbb{Z}_{\geq 1},
\)
and such that for all \(i\in \mathbb{Z}_{\geq 2}\), \({\textbf{X}}_i\) has the same color as \({\textbf{Y}}^*_{i-1}\).
Assumption 2. There exists a centered probability distribution \((\alpha_y)_{y\in\mathbb{Z}_{\leq 1}}\) on \(\mathbb{Z}_{\leq 1}\) with finite variance and a sequence of non-negative integers \((c_y)_{y\in\mathbb{Z}_{\leq 1}}\) such that the corresponding one-dimensional random walk \(({\textbf{X}}_i)_{i\geq 1}\) (defined above) satisfies
\(
\text{G}^{-1}({\sigma}_n)\stackrel{d}{=}({\textbf{X}}_{i}|({\textbf{X}}_{j})_{j\in[2,n]}\geq \beta,{\textbf{X}}_{n+1}=\beta)_{i\in[n]},
\)
where \(\sigma_n\) is a uniform permutation in \(\mathcal C\) of size \(n\).
For the third assumption we need to introduce the following definitions. We denote by \(K^*\) the set of all finite sequences of colored labels starting at \(\lambda\) and consistent with the colored succession rule. Moreover, \(K^*_n\) is the set of sequences in \(K^*\) of length \(n.\)
Definition. Given a sequence \((k_i^*)_{i\in[n]}\in K^*_n\) of (colored) labels in a generating tree, the corresponding sequence of colored jumps is the sequence \((y_i^*)_{i\in[n-1]}\) where \(y_i^*\) has value equal to \(k_{i+1}-k_i\) and inherits the same color as the label \(k_{i+1}^*\) (if it is colored).
Definition. A sequence of \(h\) colored jumps \((y^*_1,\dots,y^*_h)\) is consistent if it is equal to a factor of a sequence of jumps corresponding to an element of \(K^*\).
We denote by \(\mathcal{Y}^*_h\) the set of consistent sequences of \(h\) colored jumps.
Assumption 3. For all \(h \geq 1,\) there exists a function \(\text{Pat}:\mathcal{Y}^*_h \to\mathcal{S}^h\) and a constant \(c(h )\geq 0\) such that if a sequence of labels \((k_i^*)_{i\in[n]}\in K^*_n\) satisfies for some \(m\in[n+1-h ]\) the condition
\(k_i>c(h ),\quad\text{for all}\quad i\in[m,m+h -1],\)
then
\(\text{pat}_{[m,m+h -1]}\big(\text{G}((k_i^*)_{i\in[n]})\big)=\text{Pat}\big((y_i^*)_{i\in[m-1,m+h -2]}\big),\)
where \((y_i^*)_{i\in[n-1]}\) is the sequence of (colored) jumps associated to \((k_i^*)_{i\in[n]}\in K^*_n\).
In words, the consecutive pattern induced on the interval \([m,m+h -1]\) in the permutation \(\text{G}((k_i^*)_{i\in[n]})\) is uniquely determined through the function \(\text{Pat}\) by the factor of colored jumps \((y_i^*)_{i\in[m-1,m+h -2]}\) as long as the labels are large enough.
We can now state our main result.
Theorem. Let \(\mathcal{C}\) be a family of permutations that satisfies Assumptions 1, 2 and 3. Let \(({\textbf{Y}}^*_i)_{i\geq1}\) be a sequence of i.i.d. random variables distributed as \({\textbf{Y}}^*.\) Let \({\sigma}_n\) be a uniform random permutation in \(\mathcal{C}^n,\) for all \(n\in\mathbb{Z}_{>0}.\) Then, for all \(\pi\in\mathcal{S},\) we have the following central limit theorem,
\(\frac{\text{coc}(\pi,{\sigma}_n)-n\mu_{\pi}}{\sqrt n}\stackrel{d}{\longrightarrow}{\mathcal N}(0,\gamma_{\pi}^2),
\)
where \(\mu_{\pi}=\text{P}\left(\text{Pat}\left({\textbf{Y}}_1^*,\dots,{\textbf{Y}}^*_{|\pi|}\right)=\pi\right)\) and \(\gamma_{\pi}^2=\beta^2-\frac{\rho^2}{\sigma^2}\) with
\(\sigma^2=\text{Var}\left({\textbf{Y}}_1\right),\)\(\rho=\text{E}\left[\textbf{1}_{\left\{\text{Pat}\left({\textbf{Y}}_1^*,\dots,{\textbf{Y}}^*_{|\pi|}\right)=\pi\right\}}\cdot \sum_{j=1}^{|\pi|}\textbf{Y}_j\right],\)
\(
\beta^2=2\nu+\mu_\pi-(2|\pi|-1)\cdot\mu_\pi^2,\)
\(
\nu=\sum_{s=2}^{|\pi|}\sum_{\substack{
(y^*_i)_{i\in[|\pi|]},(\ell^*_i)_{i\in[|\pi|]}\in\text{Pat}^{-1}(\pi)\\
\text{s.t. } ({y}^*_s,\dots,{y}^*_{|\pi|})=({\ell}^*_1,\dots,{\ell}^*_{|\pi|-s+1})}}
\text{P}\left(
({\textbf{Y}}^*_{i})_{i\in[|\pi|+s-1]}=({y}^*_1,\dots,{y}^*_{|\pi|},{\ell}^*_{|\pi|-s+2},\dots,{\ell}^*_{|\pi|})\right).\)
A consequence of the above result is the local limit result below. It deals with the annealed and quenched Benjamini–Schramm convergence for permutations (see this article for more explanations), denoted by \(\stackrel{aBS}{\longrightarrow}\) and \(\stackrel{qBS}{\longrightarrow}\) respectively.
Corollary. Let \(\mathcal{C}\) be a family of permutations encoded by a generating tree that satisfies Assumptions 1, 2 and 3. There exists a random infinite rooted permutation \({\sigma}^\infty_{\mathcal{C}}\) such that
\({\sigma}_n\stackrel{qBS}{\longrightarrow}\mathcal{L}aw({\sigma}^\infty_{\mathcal{C}})\quad\text{and}\quad {\sigma}_n\stackrel{aBS}{\longrightarrow}{\sigma}^\infty_{\mathcal{C}}.\)