Inverses de Pólyagt-alea.math.cnrs.fr/alea2015/transp/Rolin.pdfInverses de Pólya Olivier Bodini1, Antoine Genitrini2 et Nicolas Rolin1 1Université Paris 13 – LIPN 2UPMC Paris

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.


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.


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.


1 Methode symbolique

2 Inverses de Polya

3 Exemples


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 |γ|.


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)

...


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)


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)

).


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)).


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

)


Inverses de Polya


2 Inverses de Polya

3 Exemples


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 ,


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 ,


Inverses de Polya

Transformee d’Euler inverse dans OEIS


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


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


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


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

)={



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

)={



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

)={



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)

))


Exemples


2 Inverses de Polya

3 Exemples


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.


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...


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...


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.


Exemples


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.


Exemples


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


Exemples


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


Exemples


A < B < C < D < E

α = B

A

C

•

C A B

β = A

E

D

•

E A D

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


Exemples

A < B < C < D < E•

E A D

•

C A B

•

C A B

•

E A DC A BC A B


Exemples

A < B < C < D < E

•

E A D

•

C A B

•

C A B

•

E A D

C A BC A B


Exemples

A < B < C < D < E

•

E A D

•

C A B

•

C A B

•

E A DC A B

C A B


Exemples

A < B < C < D < E

•

E A D

•

C A B

•

C A B

•

E A DC A BC A B


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 .


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 .


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))


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


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).


Documents

Inverses de Pólyagt-alea.math.cnrs.fr/alea2015/transp/Rolin.pdfInverses de Pólya Olivier Bodini1, Antoine Genitrini2 et Nicolas Rolin1 1Université Paris 13 – LIPN 2UPMC Paris