La ley del semicírculo. · aparece en varios problemas de conteo. EugØne Charles Catalan, quien los ﬁdescubrióﬂen 1838 mientras estudiaba el problema de las sucesiones de parØntesis

La ley del semicírculo.

J. Armando Domínguez [email protected]

Facultad de Ciencias Físico-MatemáticasUniversidad Autónoma de Sinaloa

Escuela de Matrices AleatoriasCIMAT, Guanajuato, Gto.19-23 de noviembre de 2012

21 de noviembre de 2012J. Armando Domínguez [email protected]

Facultad de Ciencias Físico-MatemáticasUniversidad Autónoma de Sinaloa

Escuela de Matrices AleatoriasCIMAT, Guanajuato, Gto.19-23 de noviembre de 2012

() Semicírculo 21 de noviembre de 2012 1 / 1

Números de Catalan

Los números de Catalan forman una secuencia de números naturales queaparece en varios problemas de conteo. Eugéne Charles Catalan, quien los�descubrió� en 1838 mientras estudiaba el problema de las sucesiones deparéntesis bien formados. Leonhard Euler los obtuvo en 1751 los descubriómientras estudiaba el problema de la triangulación de polígonos convexos.En 1988, una universidad de Mongolia publicó que los números de Catalanse habían usado en China por Minggatu alrededor de 1730.

-Enumerative Combinatorics. Richard P. Stanley (1999) Volume 2.En su página de internethttp://math.mit.edu/~rstan/ec/catadd.pdf lleva un conteo de 201interpretaciones de los números de Catalán, hasta el 13 de julio de 2012.-Catalan numbers with applications. Koshy 2009.

J. Armando Domínguez Molina () Semicírculo 20 de noviembre de 2012 2 / 22

Números de Catalan

Los número de Catalan están de�nidos como

Cn =1

n+ 1

�2nn

�.

Veamos algunos ejemplos para n = 3. En este caso C3 = 5.Los números de Catalan cuentan el número de expresiones que contienen npares de paréntesis correctamente colocados, por ejemplo para n = 3

((( ))), ( )(( )), ( )( )( ), (( ))( ), (( )( ))


Números de Catalan

Ejemplo 1:Triangulación de un polígono convexo de n+ 2 lados.


Números de Catalan

Ejemplo 2:Un Camino de Dyck de longitud 2n es una trayectoria que inicia y �nalizaen el origen, con incrementos +1 o �1, y que se mantiene en los reales nonegativos.

Ejemplo 3: Momentos del semicírculoEjemplo 4: Saludos de mano, sin cruzarse, en una mesa redonda por 2npersonasEjemplo 5: n Semicírculos que no se crucen.


160 Catalan Numbers with Applications

Example 6.9 Find the number of ways 2n people, seated around a round table,can shake hands without their hands crossing, where n ≥ 0.Solution Figure 6.15 shows the various possible handshakes for 0 ≤ n ≤ 4.The answer in each case is a Catalan number.

n = 0 n = 1 n = 2

n = 3

n = 4

Figure 6.15 Possible Handshakes for 0 ≤ n ≤ 4

This problem can be restated as follows: Find the number of ways in which2n points on a circle can be joined by n chords in such a way that no two chordsintersect.

The Ubiquity of Catalan Numbers II 211

n = 0 n = 1 n = 2

n = 3

n = 4

Figure 7.13

between the set of semicircles in Example 7.8 and the set of well-formed sequencesof parentheses. Thus, the desired answer is once again the Catalan number Cn.

Notice that the semicircle problem can be restated as follows: Find the numberof ways 2n points on a horizontal line can be joined by nonintersecting arcs, whereeach arc connects two points and lies above the line, and n ≥ 0.

See Figure 7.14, where n = 3

Figure 7.14

Example 7.8 Revisited

Because there is a one-to-one correspondence between the set of semicircles inExample 7.9 and the set of well-formed sequences of parentheses (or the binarywords in Example 6.12), it follows that there is a bijection between the set ofsemicircles and the set of permutations in Example 7.8.

For example, consider the array of four semicircles. Scan it from leftto right. Enter a count for each left end of a semicircle and keep the same countfor its right end:

� �� 12 23 31 4 4

The Ubiquity of Catalan Numbers I 159

an even number En of peaks and an odd number On of peaks, both at even height.It can be shown† that

En ={

12 Cn if n is even12

(Cn + C�n/2�

)otherwise

and

On ={

12 Cn if n is even12

(Cn − C�n/2�

)otherwise

Example 6.8 Suppose we have an infinite supply of pennies and we would like tostack them up in rows. Find the number of different arrangements possible subjectto the following conditions:

• The bottom row consists of n pennies, each touching its two neighbors,except the ends, where n ≥ 1.

• A coin that does not belong to a row sits on the two coins below it.• Do not distinguish between heads and tails.

Solution Figure 6.14 shows the possible arrangements, where 1 ≤ n ≤ 4. Ingeneral, there are Cn such possible arrangements.

n = 1 n = 2

n = 3

n = 4

Figure 6.14 Possible Arrangements of Coins for 1 ≤ n ≤ 4

† See American Mathematical Monthly 114 (March 2007) for a solution by O. P. Lossers ofEindhoven University of Technology, The Netherlands.

Números de Catalan

Ejemplo 6: Un árbol binario con raiz donde cada vértice tiene o dos hijoso ninguno.

TeoremaHay Ck árboles binarios con k padres.

Imáginemos que nuestros árboles son como árboles genealógicos, dondecada padre tiene exactamente dos hijos, uno derecho y otro izquierdo. Elpadre de todos se llama padre principal.


Números de Catalan


Números de Catalan


(k+ 1) Bk = 2 (2k� 1) Bk�1 ) Bk =2 (2k� 1)

k+ 1Bk�1

Bk =h

2(2k�1)k+1

i h2(2k�3)

k

iBk�2

=h

2(2k�1)k+1

i h2(2k�3)

k

i h2(2k�5)

k�1

iBk�3

=h

2(2k�1)k+1

i h2(2k�3)

k

i� � �h

2(2(k�q)+1)k�q+2

iBk�q

� � � =h

2(2k�1)k+1

i h2(2k�3)

k

i� � �h

2(2+1)3

iB1

= 2k�1(2k�1)(2k�3)3(k+1)k(k�1)(k�2)��3

=1

k+ 1

�2kk

�


Números de CatalanDemostración por inducción

Demostraremos por inducción que si

(k+ 1) Bk = 2 (2k� 1) Bk�1,

entonces

Bk =1

k+ 1

�2kk

�.

Veamos si es cierto para k = 2 :

B2 =13 (

42) =

13

4!2!2! =

13

244 = 2.

Además (2+ 1) B2 = 2 (4� 1) B1 ) 3B2 = 6 ) B2 = 2.

Por lo tanto es cierta para k = 2.


Números de CatalanDemostración por inducción

Hipótesis de inducción:

Bk =1

k+ 1

�2kk

�, 8k � 2

Ahora

Bk+1 =2 (2 (k+ 1)� 1)

k+ 2Bk =

2 (2k+ 1)k+ 2

1k+ 1

�2kk

�=

2 (2k+ 1)k+ 2

1k+ 1

(2k)!k!k!

=2 (k+ 1)

k+ 2(2k+ 1) (2k)!

(k+ 1) k! (k+ 1) k!

=1

k+ 2(2k+ 2) (2k+ 1)!(k+ 1)! (k+ 1)!

=1

(k+ 1) + 1

�2 (k+ 1)

k+ 1

�.


Biyección

Con �nes de obtener una biyección que usaremos más adelante observemoslo siguiente:Consideremos un árbol binario con k padres. Recorramos el árbol binarioiniciando por la arista que une al padre inicial con su hijo de la derecha. Acada árbol binario le asociamos la 2k-tupla (ξ1, ..., ξ2k), la cualconstruimos de la siguiente manera: partiendo del padre inicial recorremosen sentido horario, si la arista por la que pasamos conecta al hijo de laderecha hacemos ξ i = 1 y si conecta con el hijo de la izquierda ξ i = �1,no se contabilizan los hijos por los que ya se hayan pasado.Considerando los cinco árboles binarios con tres padres a los que lesasociamos (1,�1, 1,�1, 1,�1), (1,�1, 1, 1,�1,�1), (1, 1,�1,�1, 1,�1), (1, 1, 1,�1,�1,�1) , (1, 1,�1, 1,�1,�1).


La ley del semicírculo

Ley del SemicírculoTeorema de Wigner. Sea An una matriz de Wigner, donde aij sonv.a.i.i.d, con Var

�aij�= 1, 1 � i < j � n, y aii son v.a.i.i.d. Entonces

FAn/p

n (x) D!n!∞

F (x) , c.s.,

donde F (x) es la ley del semicírculo.

Ley del Semicírculo

F0 (x) =1

2π

p4� x21[�2,2] (x) ,

1E (x) = 1 si x 2 E y 1E (x) = 0 en otro caso.


Demostración del teorema de Wigner

Sea Bn = An/p

n entonces y λ1, ..., λn sus eigenvalores

FBn (x) =# fλi � x : i = 1, ..., ng

n

βk (Bn) =Z

xkdFBn (x)

=1n

n

∑i=1

λki =

1n

tr�

Bkn

�=

1n

trn��

An/p

n��ko

=1

n1+ k2

tr�

Akn

�


Demostración del teorema de WignerDe la traza a las grá�cas cíclicas

βk (Bn) =1

n1+ k2

tr�

Akn

�=

1

n1+ k2

n

∑i1,i2,...,ik=1

ai1i2 ai2i3 ...aiki1

=1

n1+ k2

∑i

A (i) ,

donde A (i) = ai1i2 ai2i3 ...aiki1 , i = (i1, ..., ik) 2 f1, ..., ngk


Grá�cas cíclicas

Una grá�ca es una terna (E, V, ϕ) , V 6= 0, V es el conjunto de vértices, Ees conjunto de aristas.ϕ : E ! V �V, i.e. para e 2 E, F (e) = (v1, v2) .v1 y v2 se llaman vérticessi v1 = v2 ϕ (e) es un lazoSi ϕ (e1) y ϕ (e2) tienen los mismos vértices se llaman aristas coincidenteso paralelas.Sea i 2 f1, ..., ngk , i.e, i = (i1, ..., ik) . A cada i le asignaremos unagrá�ca de la siguiente manera:trácese una línea horizontal y marque los números i1, ..., ik en ella.Considere los números distintos como vértices. fi1, ..., ikg = fi01, ..., i0tg ,1 � t � k y dibuje las k aristas ej de ij a ij+1, j = 1, ..., k, ik+1 = i1.

Denotaremos este tipo de grá�ca como grá�ca-Γk,t.



Podemos separar las grá�cas-Γk,t en tres categorías.

Categoría 1: Γ1. Cada arista tiene una, y solo una, arista paralela endirección opuesta.

Observación. Si k es impar no hay grá�cas Γk,t en Γ1.Categoría 2: Γ2. Grá�cas con por lo menos una arista simple.Categoría 3: Γ3. El resto de las grá�cas.

Lema

Si t > k2 entonces Γk,t /2 Γ3.

Corolario

Si Γk,t 2 Γ3 entonces t � k2 .





Observación. Si k es impar no hay grá�cas Γk,t en Γ1.

Categoría 2: Γ2. Grá�cas con por lo menos una arista simple.Categoría 3: Γ3. El resto de las grá�cas.

Lema


Corolario






Observación. Si k es impar no hay grá�cas Γk,t en Γ1.Categoría 2: Γ2. Grá�cas con por lo menos una arista simple.

Categoría 3: Γ3. El resto de las grá�cas.

Lema


Corolario







Lema


Corolario







Lema


Corolario







Lema


Corolario




Lema


Demostración. Caso I: k part = k

2 + 1 ) Γk, k2+1 2 Γ1 o Γk, k

2+1 2 Γ2

t > k2 + 1 ) Γk,t 2 Γ2

Caso II. k impart > k

2 ) t � k�12 + 1 ) Γk,t 2 Γ2 �



Corolario

Hay a lo más nk2 grá�cas en Γ3.

Observación

En Γ2 hay menos de nk < ∞.

Pregunta¿Cuántas habrá en Γ1?



LemaContar grá�cas en Γ1 es equivalente a contar sucesiones características de�1�s

ObservaciónLa grá�cas en Γ1 son árboles orientado con raíz de k aristas.


Biyección

Se pueden identi�car estos árboles con sucesiones características quetienen de elementos dicotómicos como sigue. A cada árbol orientado conraíz de k aristas se le asocia la 2k-tupla (ξ 01, ..., ξ 02k) construida de lasiguiente manera: si en el i-ésimo paso del recorrido la arista en turno esrecorrida por primera vez entonces ξ 0i = 1 y si ya se había pasado ellaentonces ξ 0i = �1. Esto establece una biyección entre los árbolesorientados con raíz de k aristas y el subconjunto T2k de f�1, 1g2k queconsiste de los elementos (ξ1, ..., ξ2k) tales que

ξ 0i = �1sl = ξ1 + � � �+ ξ l , 1 � l � 2k,sl � 0 ) ξ1 = 1

s2k = 0 ) ξ2k = �1


Biyección

Los árboles Árboles binarios con k/2 padres tienen la misma sucesióncaracterística


Documents

La ley del semicírculo. · aparece en varios problemas de conteo. EugØne Charles Catalan, quien los ﬁdescubrióﬂen 1838 mientras estudiaba el problema de las sucesiones de parØntesis