Inverses de P´olyagt-alea.math.cnrs.fr/alea2015/transp/Rolin.pdfInverses de P´olya Olivier...

Inverses de Polya

Olivier Bodini1, Antoine Genitrini2 etNicolas Rolin1

1Universite Paris 13 – LIPN

2UPMC Paris – LIP6

ALEA 2015

N.ROLIN (Universite Paris 13 – LIPN) Inverses de Polya ALEA 2015 1 / 33

Multiset

{2, 2, 5} = {2, 5, 2} = {5, 2, 2}

{2, 2, 5} ⇐⇒ 20

Multiset ({nombres premiers})⇐⇒ {entiers > 1}

C’est l’une des constructions fondamentales deAnalytic Combinatorics.

N.ROLIN (Universite Paris 13 – LIPN) Inverses de Polya ALEA 2015 2 / 33

Introduction

Question{0, 1}n ⇐⇒ Multiset ({???})

Reponse{0, 1}n ⇐⇒ Multiset ({mots de Lyndon})

Les mots de Lyndon :0,1,01,001,011,0001,0011,0111,...= l’ensemble des mots qui sont plus petits que tousleurs suffixes non triviaux.

Exemple : Le mot x = 0110100110010110 = 011 . 01 . 0011 . 001011 . 0En effet 011 > 01 > 0011 > 001011 > 0.

N.ROLIN (Universite Paris 13 – LIPN) Inverses de Polya ALEA 2015 3 / 33

Introduction

Question{0, 1}n ⇐⇒ Multiset ({???})

Reponse{0, 1}n ⇐⇒ Multiset ({mots de Lyndon})

Les mots de Lyndon :0,1,01,001,011,0001,0011,0111,...= l’ensemble des mots qui sont plus petits que tousleurs suffixes non triviaux.

Exemple : Le mot x = 0110100110010110 = 011 . 01 . 0011 . 001011 . 0En effet 011 > 01 > 0011 > 001011 > 0.

N.ROLIN (Universite Paris 13 – LIPN) Inverses de Polya ALEA 2015 3 / 33

1 Methode symbolique

2 Inverses de Polya

3 Exemples

N.ROLIN (Universite Paris 13 – LIPN) Inverses de Polya ALEA 2015 4 / 33

Methode symbolique

Definitions

Une classe combinatoire C est un ensemble d’objets, avec une fonction detaille, note par | · | : C → N et telle que pour chaque entier n, lesous-ensemble Cn des objets de taille n est fini de cardinalite Cn.On definit la fonction generatrice ordinaire d’une classe combinatoire Cetant :

C(z) =∑n≥0

Cnzn =∑γ∈C

z |γ|.

N.ROLIN (Universite Paris 13 – LIPN) Inverses de Polya ALEA 2015 5 / 33

Methode symbolique

Methode symbolique

Petit dictionnaire des constructions

C = A+ B → C(z) = A(z) + B(z)

C = A ∗ B → C(z) = A(z)B(z)

C = Seq(A)→ C(z) = 11− A(z)

...

N.ROLIN (Universite Paris 13 – LIPN) Inverses de Polya ALEA 2015 6 / 33

Methode symbolique

Methode symbolique

Arbres de Motzkin (unaires-binaires) :

M = ∅ +•

M

•

M M+

M(z) = 1 + zM(z) + zM(z)2

Arbres de Catalan :

C =•

C C C . . .

C(z) = z1− C(z)

N.ROLIN (Universite Paris 13 – LIPN) Inverses de Polya ALEA 2015 7 / 33

Methode symbolique

Multiset

On note A = MSet(B) quand A est obtenu en formant tous lesmulti-ensembles d’elements de B (avec B0 = ∅).

A = MSet(B)⇒ A(z) = MSet(B(z)) =

+∞∏p=1

(1− zn)−Bn ,

exp(

+∞∑p=1

1p B(zp)

).

N.ROLIN (Universite Paris 13 – LIPN) Inverses de Polya ALEA 2015 8 / 33

Methode symbolique

Powerset

On note A = PSet(B) quand A est obtenu en formant tous les ensemblesd’elements de B.

A = PSet(B)⇒ A(z) = PSet(B(z)) =

+∞∏p=1

(1 + zn)Bn ,

exp(

+∞∑p=1

(−1)p−1

p B(zp)).

N.ROLIN (Universite Paris 13 – LIPN) Inverses de Polya ALEA 2015 9 / 33

Methode symbolique

Cycle

On note A = Cyc(B) quand A est obtenu en prenant les sequences de B,mais en ne comptant qu’un seul representant d’un shift circulaire.

A = Cyc(B)⇒ A(z) = Cyc(B(z)) =+∞∑p=1

ϕ(p)p ln

( 11− B(zp)

),

ou ϕ est l’indicatrice d’Euler.

ϕ(p) = p∏k|p

(1− 1

k

)

N.ROLIN (Universite Paris 13 – LIPN) Inverses de Polya ALEA 2015 10 / 33

Inverses de Polya

1 Methode symbolique

2 Inverses de Polya

3 Exemples

N.ROLIN (Universite Paris 13 – LIPN) Inverses de Polya ALEA 2015 11 / 33

Inverses de Polya

Multiset et transformee d’Euler

Soit A(z) = MSet(B(z)).Transformee d’Euler :

An = 1n

(Cn +

n−1∑k=1

CkAn−k

)ou

Cn =∑d |n

dBd ,

N.ROLIN (Universite Paris 13 – LIPN) Inverses de Polya ALEA 2015 12 / 33

Inverses de Polya

Transformee d’Euler inverse

Soit A(z) = MSet(B(z)).Transformee d’Euler inverse :

Bn = 1n∑d |n

µ

(nd

)Cd

ou

Cn = nAn −n−1∑k=1

CkAn−k ,

N.ROLIN (Universite Paris 13 – LIPN) Inverses de Polya ALEA 2015 13 / 33

Inverses de Polya

Transformee d’Euler inverse dans OEIS

N.ROLIN (Universite Paris 13 – LIPN) Inverses de Polya ALEA 2015 14 / 33

Inverses de Polya

Multiset inverse

TheoremeL’inverse compositionel de l’operateur multiset est :

MSet−1(A(z)) =+∞∑k=1

µ(k)k ln(A(zk)),

ou µ est la fonction de Mobius.

∑k|iµ(k) =

{1 quand i = 10 quand i > 1

N.ROLIN (Universite Paris 13 – LIPN) Inverses de Polya ALEA 2015 15 / 33

Inverses de Polya

Preuve du multiset inverse

Rappel :MSet(A(z)) = exp

(+∞∑p=1

1p B(zp)

)MSet−1(A(z)) =

+∞∑k=1

µ(k)k ln(A(zk))

Preuve.MSet−1 ◦MSet(A(z)) =

+∞∑i=1

A(z i )i∑k|iµ(k)

MSet ◦MSet−1(A(z)) = exp(

+∞∑i=1

ln(A(z i ))i

∑k|iµ(k)

)

On utilise ∑k|iµ(k) =

{1 quand i = 10 quand i > 1

N.ROLIN (Universite Paris 13 – LIPN) Inverses de Polya ALEA 2015 16 / 33

Inverses de Polya

Powerset inverse

TheoremeL’inverse compositionel de l’operateur powerset est :

PSet−1(A(z)) =+∞∑k=1

f (k)k ln(A(zk)),

ou f [A067856] est la fonction verifiant :

∑k|i

(−1)k−1f( i

k

)={

1 quand i = 10 quand i > 1

N.ROLIN (Universite Paris 13 – LIPN) Inverses de Polya ALEA 2015 17 / 33

Inverses de Polya

Preuve du powerset inverse

Rappel :PSet(B(z)) = exp

(+∞∑p=1

(−1)p−1

p B(zp))

PSet−1(A(z)) =+∞∑k=1

f (k)k ln(A(zk))

Preuve.

PSet−1 ◦PSet(A(z)) =+∞∑i=1

A(z i )i∑k|i

(−1)k−1f(

ik

)PSet ◦PSet−1(A(z)) = exp

(+∞∑i=1

ln(A(z i ))i

∑k|i

(−1)k−1f(

ik

))

On utilise que ∑k|i

(−1)k−1f( i

k

)={

1 quand i = 10 quand i > 1

N.ROLIN (Universite Paris 13 – LIPN) Inverses de Polya ALEA 2015 18 / 33

Inverses de Polya

Cycle inverse

TheoremeL’inverse compositionel de l’operateur cycle est :

Cyc−1(A(z)) = 1− exp(−(+∞∑

k=1

g(k)k A(zk)

)),

ou g [A023900] est la fonction verifiant :

∑k|i

g(k)ϕ( i

k

)={

1 quand i = 10 quand i > 1

N.ROLIN (Universite Paris 13 – LIPN) Inverses de Polya ALEA 2015 19 / 33

Inverses de Polya

Preuve du cycle inverse

Rappel :Cyc(A(z)) =

+∞∑p=1

ϕ(p)p ln

(1

1−B(zp)

)Cyc−1(A(z)) = 1− exp

(−(+∞∑

k=1

g(k)k A(zk)

))Preuve.

Cyc−1 ◦Cyc(A(z)) = 1− exp

−+∞∑i=1

ln(

11−A(zi )

)i

∑k|i

g(k)ϕ(

ik

)Cyc ◦Cyc−1(A(z))) =

+∞∑i=1

A(z i )i∑k|i

g(k)ϕ(

ik

)On utilise que ∑

k|ig(k)ϕ

( ik

)={

1 quand i = 10 quand i > 1

N.ROLIN (Universite Paris 13 – LIPN) Inverses de Polya ALEA 2015 20 / 33

Inverses de Polya

Recapitulatif

operateur inverse

Multiset exp(

+∞∑p=1

1p B(zp)

)+∞∑k=1

µ(k)k ln(A(zk))

Powerset exp(

+∞∑p=1

(−1)p−1

p B(zp))

+∞∑k=1

f (k)k ln(A(zk))

Cycle+∞∑p=1

ϕ(p)p ln

(1

1−B(zp)

)1− exp

(−(+∞∑

k=1

g(k)k A(zk)

))

N.ROLIN (Universite Paris 13 – LIPN) Inverses de Polya ALEA 2015 21 / 33

Exemples

1 Methode symbolique

2 Inverses de Polya

3 Exemples

N.ROLIN (Universite Paris 13 – LIPN) Inverses de Polya ALEA 2015 22 / 33

Exemples

Mots de Lyndon

Soit les langage des mots a k lettres Sk(z) :

Sk(z) = 11− kz .

On y applique le MSet−1 :

Lk(z) = MSet−1(Sk(z)) =+∞∑i=1

µ(i)i ln

( 11− kz i

)

Lk(z) =+∞∑n=1

∑p|n

µ( np )kp

n zn

Ce sont les mots de Lyndon.

N.ROLIN (Universite Paris 13 – LIPN) Inverses de Polya ALEA 2015 23 / 33

Exemples

Mots de ???

On peut appliquer le MSet−1 a Lk(z) + 1.

Dans le cas k = 2 on obtient une suite commencant par :

2, 1, 2, 3, 6, 9, 18, 30, 56, 99, 186, 335, 630, ...

Interpretation ouverte...

N.ROLIN (Universite Paris 13 – LIPN) Inverses de Polya ALEA 2015 24 / 33

Exemples

Mots de ???

On peut appliquer le MSet−1 a Lk(z) + 1.

Dans le cas k = 2 on obtient une suite commencant par :

2, 1, 2, 3, 6, 9, 18, 30, 56, 99, 186, 335, 630, ...

Interpretation ouverte...

N.ROLIN (Universite Paris 13 – LIPN) Inverses de Polya ALEA 2015 24 / 33

Exemples

Multiset inverse des arbres de Catalan

Serie generatrice des arbres de Catalan C :

C(z) = 1−√−4 z + 12z .

On y applique le MSet−1 :

Suite qui semble positive croissante : 1, 1, 1, 3, 8, 25, 75, 245, 800, ...,qui coıncide avec la suite [A022553] de OEIS.

N.ROLIN (Universite Paris 13 – LIPN) Inverses de Polya ALEA 2015 25 / 33

Exemples

Multiset inverse des arbres de Catalan

Serie generatrice des arbres de Catalan C :

C(z) = 1−√−4 z + 12z .

On y applique le MSet−1 :Suite qui semble positive croissante : 1, 1, 1, 3, 8, 25, 75, 245, 800, ...,qui coıncide avec la suite [A022553] de OEIS.

N.ROLIN (Universite Paris 13 – LIPN) Inverses de Polya ALEA 2015 25 / 33

Exemples

Multiset inverse des arbres de Catalan

MSet−1(C) : cycles primitifs d’arbres de Catalan.[primitif = pas de symetrie circulaire]

A

E

C

D

B

A,B,C ,D,E ∈ C

N.ROLIN (Universite Paris 13 – LIPN) Inverses de Polya ALEA 2015 26 / 33

Exemples

Multiset inverse des arbres de Catalan

On va transformer cannoniquement un cycle primaire d’arbres de Catalanen arbre de Catalan. On choisit un ordre total sur les arbres de Catalan.On choisit le representant le plus grand dans l’ordre lexicographique et onle place fils gauche.Ex : A < B < C < D < E

A

E

C

D

B

•

E A B D C

N.ROLIN (Universite Paris 13 – LIPN) Inverses de Polya ALEA 2015 27 / 33

Exemples

Multiset inverse des arbres de Catalan

A < B < C < D < E

α = B

A

C

•

C A B

β = A

E

D

•

E A D

A quel arbre de Catalan correspond {α, α, β} ?

N.ROLIN (Universite Paris 13 – LIPN) Inverses de Polya ALEA 2015 28 / 33

Exemples

A < B < C < D < E•

E A D

•

C A B

•

C A B

•

E A DC A BC A B

N.ROLIN (Universite Paris 13 – LIPN) Inverses de Polya ALEA 2015 29 / 33

Exemples

A < B < C < D < E

•

E A D

•

C A B

•

C A B

•

E A D

C A BC A B

N.ROLIN (Universite Paris 13 – LIPN) Inverses de Polya ALEA 2015 29 / 33

Exemples

A < B < C < D < E

•

E A D

•

C A B

•

C A B

•

E A DC A B

C A B

N.ROLIN (Universite Paris 13 – LIPN) Inverses de Polya ALEA 2015 29 / 33

Exemples

A < B < C < D < E

•

E A D

•

C A B

•

C A B

•

E A DC A BC A B

N.ROLIN (Universite Paris 13 – LIPN) Inverses de Polya ALEA 2015 29 / 33

Exemples

Series de Dirichlet

On veut regarder ce que ces resultats donnent dans le cadre de classescombinatoires ou la taille des objets se multiplie.|(a, b)| = |a|· |b|

On definit la fonction generatrice de Dirichletd’une classe combinatoire C etant :

C(s) =∑n≥1

Cnns .

N.ROLIN (Universite Paris 13 – LIPN) Inverses de Polya ALEA 2015 30 / 33

Exemples

Series de Dirichlet

On veut regarder ce que ces resultats donnent dans le cadre de classescombinatoires ou la taille des objets se multiplie.|(a, b)| = |a|· |b|

On definit la fonction generatrice de Dirichletd’une classe combinatoire C etant :

C(s) =∑n≥1

Cnns .

N.ROLIN (Universite Paris 13 – LIPN) Inverses de Polya ALEA 2015 30 / 33

Exemples

Multiset de series de Dirichlet

On dispose aussi du multiset sur les series de Dirichlet :

multiset

MSet(C(s)) = exp(∑

p≥1

C(ps)p

)

Extension de MSet−1 aux series de Dirichlet immediate :multiset inverse

MSet−1(C(s)) =∑

k≥1

µ(k)k ln(C(ks))

N.ROLIN (Universite Paris 13 – LIPN) Inverses de Polya ALEA 2015 31 / 33

Exemples

Nombres premiers

Notamment pour Cn = 1ζ(s) =

∑n≥1

1ns .

Si on cherche la serie generatrice correspondante a l’indicatrice desnombres premiers P(s), on peut prendre le MSet−1 de ζ(s) :

P(s) :=∑

n premier

1ns =

∑k≥1

µ(k) ln(C(ks))k

N.ROLIN (Universite Paris 13 – LIPN) Inverses de Polya ALEA 2015 32 / 33

Conclusion

Conclusion

On a obtenu:une etude des inverses des operateurs combinatoires (multiset, cycle,powerset).les formules exactes pour les series generatrices associees.une preuve bijective sur les arbres de Catalan (explicationcombinatoire de MSet−1 des arbres de Catalan).une extension aux series generatrices de Dirichlet.

Perspectives :etudier le phenomene du MSet−1(MSet−1) qui reste une suited’entiers positifs.analyser les asymptotiques MSet−1(A(z)) connaissant A(z).

N.ROLIN (Universite Paris 13 – LIPN) Inverses de Polya ALEA 2015 33 / 33