We survey recent work on the enumeration of noncrossing configurations on the set of vertices of a convex polygon, such as triangulations, trees, and forests. Exact formulæ and limit laws are determined for several parameters of interest. In the second part of the talk we present results on the enumeration of chord diagrams (pairings of 2n vertices of a convex polygon by means of n disjoint pairs). We present limit laws for the number of components, the size of the largest component and the number of crossings. The use of generating functions and of a variation of Levy's continuity theorem for characteristic functions enable us to establish that most of the limit laws presented here are Gaussian. (Joint work by Marc Noy with Philippe Flajolet and others.)
7pt
Figure 1: (a) A connected noncrossing graph; (b) an arbitrary noncrossing graph.
Figure 2: (a) A tree; (b) a forest.
2n4 
n2 
D_{n}(t)=max  {  d_{i}i=0,...,n1  }  , 
l_{n}(t)=max  {  v_{i}v_{j}v_{i}v_{j}Î T_{n}  }  , 
E[D_{n}]~log_{2}n, and E[l_{n}]~a n, where a= 

+ 

 

~0.4654. 
z^{2} 

(z,w)=  (  1+2z(w1)  ) 

(z,w), where 

(z,w)=z 
æ ç ç è 
w+2 

(z,w)+ 

(z,w)^{2} 
ö ÷ ÷ ø 
, 
E[e_{n}]= 

~ 

A few tricks enable one to make Lagrange inversion applicable and to derive exact formulæsometimes involving summationsfor all coefficients. For example, the change of variable T=z+zy followed by Lagrange's formula yields:1.5pt
Configuration Generating function equation
Connected graphs C^{3}+C^{2}3zC+2z^{2}=0 , edges wC^{3}+wC^{2}(1+2w)zC+(1+w)z^{2}=0 Graphs G^{2}+(2z^{2}3z2)G+3z+1=0 , edges wG^{2}+((1+w)z^{2}(1+2w)z2w)G+w+(1+2w)z=0 , components G^{3}+(2w^{3}z^{2}3w^{2}z+w3)G^{2}+(3w^{2}z2w+3)G+w1=0 Trees T^{3}zT+z^{2}=0 , leaves T^{3}+(z^{2}wz^{2}z)T+z^{2}=0 Forests F^{3}+(z^{2}z3)F^{2}+(z+3)F1=0 , components F^{3}+(w^{3}z^{2}w^{2}z3)F^{2}+(w^{3}z+3)F1=0 Triangulations z^{4}T^{^}^{2}+(2z^{2}z)T^{^}+1=0 , ears z^{4}T^{^}^{2}+(1+2z(w1))(2z^{2}z) T^{^}+w(1+2z(w1))^{2}=0
Table 1: Generating function equations (z and w mark vertices and the secondary parameter).
T_{n}= 


and T_{n,k}= 





2^{n2k+j}. 
f(z)=c_{0}+c_{1} 
æ ç ç è 
1 

ö ÷ ÷ ø 

+O 
æ ç ç è 
1 

ö ÷ ÷ ø 
, entailing [z^{n}]f(z)= 

æ ç ç è 
1+O 
æ ç ç è 

ö ÷ ÷ ø 
ö ÷ ÷ ø 
. 
C_{n}~ 
æ ç ç è 

 

ö ÷ ÷ ø 
~10.39^{n} and G_{n}~ 

(99(2)^{1/2}140)^{1/2}× 

~11.65^{n}, 
f(z,w)=c_{0}(w)+c_{1}(w) 
æ ç ç è 
1 

ö ÷ ÷ ø 

+O 
æ ç ç è 
1 

ö ÷ ÷ ø 
; 
f_{n}(w)=g(w) 
æ ç ç è 

ö ÷ ÷ ø 

æ ç ç è 
1+O 
æ ç ç è 

ö ÷ ÷ ø 
ö ÷ ÷ ø 
, or 

= 

æ ç ç è 

ö ÷ ÷ ø 

æ ç ç è 
1+O 
æ ç ç è 

ö ÷ ÷ ø 
ö ÷ ÷ ø 
. 
M_{n,k}= 

C_{nk+1}~ 

I_{n}. 
C_{n}=(n1) 

C_{j}C_{nj} 
µ_{n}= 

(z,w) 
½ ½ ½ ½ 

= 

(  I(z)+h(z)2  )  , where h(z)=I(z)^{1}. 
g_{n}=1 

g_{k} 


^{1} =1 

+ 

+O(n^{3}), 
M_{n,k}= 

C_{nk}~ 

I_{n}, n®¥. 
µ_{n}=E[X_{n}]= 

and s_{n}^{2}=Var[X_{n}]= 

, respectively. 

P 
é ê ê ë 

£ x 
ù ú ú û 
= 

ó õ 

e 
