Combinatoire 2

Permutations (suite)

Ce notebook utilise le noyau SageMath-7.5.1 (lancer avec sage --notebook jupyter).

La décomposition en cycles

Regardons la permutation $$\sigma={123456789\choose 7 4 6 2 9 1 3 8 5},$$ et itérons la.

Elle envoie 1 sur 7, 7 sur 3, 3 sur 6, et 6 sur 1. Si on continue, on tourne en rond. En partant de 2, on arrive sur 4, puis on revient sur 2. De même, 5 va sur 9 et 9 sur 5. Quant à 8, il ne bouge pas.

On dit que $\sigma$ se compose des cycles $(1,7,3,6), (2,4), (5,9),(8)$.

In [1]:
# On utilise sage ici
p = Permutation([7,4,6,2,9,1,3,8,5])
p.to_cycles()
Out[1]:
[(1, 7, 3, 6), (2, 4), (5, 9), (8,)]
In [2]:
# Il faut des [], sinon sage interprète les tuples comme des cycles
q = Permutation((7,4,6,2,9,1,3,8,5))
q.to_cycles()
Out[2]:
[(1, 3, 8, 5, 7, 4, 6, 2, 9)]

On peut s'amuser à visualiser les cycles sous forme de graphes en utilisant les capacités graphiques de sage :

In [3]:
def to_graph(p):
    edges = []
    for c in p.to_cycles():
        for i in range(len(c)): edges.append((c[i],c[(i+1) % len(c)]))
    return DiGraph(edges,loops=True)
In [4]:
to_graph(p)
Out[4]:
In [5]:
# Pour coder ces fonctions en pur Python, on pourrait s'y prendre ainsi
def to_cycles(p):
    cc = []; not_seen = range(1,len(p)+1)
    while not_seen:
        c = []; i = not_seen[0]
        while i not in c: 
            not_seen.remove(i)
            c.append(i); i=p[i-1]
        cc.append(c)
    return map(tuple,cc)
            
    

    
def from_cycles(cc):
    d = {}
    for c in cc:
        r = len(c)
        e ={c[i]:c[(i+1) % r] for i in range(r)}
        d.update(e)
    return tuple([d[i] for i in sorted(d)])
In [6]:
to_cycles(p)
Out[6]:
[(1, 7, 3, 6), (2, 4), (5, 9), (8,)]
In [7]:
from_cycles(_)
Out[7]:
(7, 4, 6, 2, 9, 1, 3, 8, 5)

L'ordre d'une permutation $\sigma$ est le plus petit entier $k>0$ tel que $\sigma^k=id$. C'est donc le p.p.c.m. des longueurs de ses cycles.

Les longueurs des cycles d'une permutation $\sigma\in{\mathfrak S}_n$ forment son type cyclique. C'est une partition de l'entier $n$, une liste non ordonnée d'entiers positifs de somme $n$. Par exemple, le type cyclique de $7 4 6 2 9 1 3 8 5$ est la partition $\mu = (4,2,2,1)$ (notation en liste décroissante), ou encore $\mu= 1^12^24^1$ (notation en exposants).

Deux permutations $\sigma$ et $\sigma'$ sont dites conjuguées s'il existe une permutation $\tau$ telle que $$\sigma'=\tau\sigma\tau^{-1}.$$

La conjugaison est une relation d'équivalence, dont les classes s'appellent naturellement classes de conjugaison.

Théorème

Deux permutations sont conjuguées si et seulement si elles ont le même type cyclique.

En effet, $$\sigma'(i)=j \Leftrightarrow \tau\sigma\tau^{-1}(i)=j \Leftrightarrow \sigma(\tau^{-1}(i))=\tau^{-1}(j)$$ de sorte que les cycles de $\sigma'$ s'obtiennent en renumérotant ceux de $\sigma$ avec $\tau$.

In [8]:
q = Permutation([3,2,6,1,4,7,9,8,5])
In [9]:
r = q.left_action_product(p.left_action_product(q.inverse()))
In [10]:
r.to_cycles()
Out[10]:
[(1, 2), (3, 9, 6, 7), (4, 5), (8,)]
In [11]:
p.to_cycles()
Out[11]:
[(1, 7, 3, 6), (2, 4), (5, 9), (8,)]

Le cardinal d'une classe de conjugaison

Pour trouver le nombre de permutations de type cyclique $\mu=1^{m_1}2^{m_2}\cdots n^{m_n}$, examinons les remplissages de $m_1$ cycles de longueur 1, $m_2$ cycles de longueur 2, etc., par $n!$ permutations de ${\mathfrak S}_n$, et comptons ceux qui définissent la même permutation.

Par exemple, pour $\mu=1^42^34^2$, on regarde les $18!$ remplissages du type $$(1)(2)(3)(4) (56)(78) (9\ 10) (11\ 12\ 13\ 14)(15\ 16\ 17\ 18)$$ Il y a beaucoup de remplissages qui définissent la même permutation. On peut permuter entre eux les cycles de même longueur. Il faudra donc diviser par $4!\times3!\times 2!$. Et chaque cycle de longueur $k$ peut aussi être permuté circulairement $k$ fois: on doit donc encore diviser par $1^4\times 2^3\times 4^2$.

Le nombre de permutations de ${\mathfrak S}_{18}$ de type $1^42^34^2$ est donc $$\frac{18!}{1^4 4! 2^3 3! 4^2 2!}$$

In [12]:
factorial(18)/(factorial(4)*2**3*factorial(3)*4**2*factorial(2))
Out[12]:
173675502000

D'une manière générale, le nombre de permutations de de type cyclique $\mu=1^{m_1}2^{m_2}\cdots n^{m_n}$ dans ${\mathfrak S}_n$ est $$c_\mu = \frac{n!}{1^{m_1}m_1! 2^{m_2}m_2!\cdots n^{m_n}m_n! }.$$

Une série génératrice multivariée

En contemplant cette formule, on peut penser au développement en série de l'exponentielle $$e^x = \sum_{n\ge 0} \frac{x^n}{n!}$$ et avoir envie de former la somme formelle $$ C(X) = \sum_{n\ge 0}\sum_{1m_1+2m_2+\cdots+nm_n=n}\frac{x_1^{m_1} x_2^{m_1}\cdots x_n^{m_n}}{1^{m_1}m_1! 2^{m_2}m_2!\cdots n^{m_n}m_n!}$$ avec une suite $X=(x_1,x_2,\ldots,x_n,\ldots)$ de variables, car elle se factorise en $$ C(X) = \sum_{m_1\ge 0}\frac{x_1^{m_1}}{1^{m_1}m_1!} \sum_{m_2\ge 0}\frac{x_2^{m_2}}{2^{m_2}m_2!}\cdots \sum_{m_n\ge 0}\frac{x_n^{m_n}}{n^{m_n}m_n!}\cdots = \exp\left(\frac{x_1}{1}\right) \exp\left(\frac{x_2}{2}\right)\cdots \exp\left(\frac{x_n}{n}\right)\cdots$$ de sorte que finalement $$C(X) = \sum_{n\ge 0}\frac1{n!}\sum_{\mu\vdash n}c_\mu X^\mu = \exp\left(\sum_{k\ge 1}\frac{x_k}{k}\right).$$

Cette expression permet de répondre à de nombreuses questions.

Nombres de Strirling de première espèce

Par exemple, quel est le nombre $c(n,k)$ de permutations de ${\mathfrak S}_n$ ayant exactement $k$ cycles ? Pour le savoir, il suffit de poser $x_m=tx^m$ ($m\ge 1$) dans la série $C(X)$ et de regarder le coefficient de $t^kx^n$ : $$C(tx,tx^2,tx^3,\ldots)= \sum_{n\ge 0}\left(\sum_{k=1}^nc(n,k)t^k\right)\frac{x^n}{n!}$$ Or, en utilisant $$\ln\left(\frac1{1-x}\right) = \sum_{n\ge 1}\frac{x^n}{n},$$ on trouve $$C(tx,tx^2,tx^3,\ldots) = \exp\left(t\sum_{k\ge 1}\frac{x^k}{k}\right)=\exp\left(t\ln\left(\frac1{1-x}\right)\right) =(1-x)^{-t}$$ et on connaît le développement (formule du binôme généralisé) $$(1-x)^{-t} = \sum_{n\ge 0}(t)^n \frac{x^n}{n!}$$ où $$(t)^n = t(t+1)(t+2)\cdots (t+n-1).$$

Ainsi, $c(n,k)$ est le coefficient de $t^k$ dans $(t)^n$. Ces nombres sont appelés nombres de Stirling de première espèce non signés, et sont souvent notés $\left[ n\atop k\right]$.

Les nombres de Stirling de première espèce signés sont les coffficients de $$(t)_n =t(t-1)(t-2)\cdots(t-n+1)=\sum_{k=1}^ns(n,k)t^k.$$

In [13]:
# sage
print [stirling_number1(5,k) for k in range(6)]
[0, 24, 50, 35, 10, 1]

Le problème du chevalier de Montmort

On peut aussi résoudre la question des dérangements. Un dérangement est une permutation sans point fixe. La probabilité pour que, $n$ personnes ayant laissé leurs chapeaux au vestiaire et les reprenant en ordre aléatoire, aucune n'ait son propre chapeau sur la tête, est $\frac{d_n}{n!}$, où $d_n$ est le nombre de dérangements.

La série génératrice des types cycliques des dérangements d'obtient en posant $x_1=0$ dans $C(X)$, et si on ne s'intéresse qu'à leur nombre, on pose $x_n=x^n$ pour $n\ge 2$, ce qui donne $$\sum_{n\ge 0}d_n\frac{x^n}{n!}= \exp\left(\sum_{k\ge 2}\frac{x^k}{k}\right)=\exp\left(-x+\ln\left(\frac1{1-x}\right)\right)=\frac{e^{-x}}{1-x},$$ un résultat classique (ce problème, connu comme le problème des rencontres, ou problème du chevalier de Montmort, a été posé pour la première fois par Pierre Rémond de Montmort en 1708, qui l'a résolu en 1713, en même temps que Nicolas Bernoulli).

Les involutions sans point fixe

Une involution sans point fixe est une permutation qui n'a que des cycles de longueur 2. Il n'en existe donc que pour les tailles paires. Le nombre $i_{2n}$ d'involutions sans point fixe a pour série génératrice exponentielle $$\sum_{n\ge 0}i_{2n}\frac{x^{2n}}{2n!} = e^{\frac12x^2}=\sum_{n\ge 0}\frac{x^{2n}}{2^n n!}$$ de sort que $$i_{2n} =\frac{2n!}{2^nn!} = 1\times 3\times 5\times\cdots\times (2n-1),$$ nombre qui est souvent noté $(2n)!!$.

Cycles, inversions et signature

Si on multiplie deux décompositions réduites, de longeurs $r$ et $s$, soit le résultat est une décomposition réduite, de longueur $r+s$, soit il ne l'est pas, auquel cas les transpositions élémentaires s'éliminent par paires. Le nombre d'inversions de $\sigma\tau$ est donc congru modulo 2 à ${\rm inv}(\sigma) +{\rm inv}(\tau)$, ce qu'on peut écrire $$(-1)^{{\rm inv}(\sigma\tau)}=(-1)^{{\rm inv}(\sigma) }(-1)^{{\rm inv}(\tau) }$$ Ce signe est appelé signature d'une permutation, et noté $$\varepsilon(\sigma) = (-1)^{{\rm inv}(\sigma) }$$ ou encore ${\rm sgn}(\sigma)$.

Une permutation de signature 1 est dite paire, et impaire sinon.

Comme le nombre d'inversions d'une permutation est le même que celui de son inverse, $$\varepsilon(\tau\sigma\tau^{-1})=\varepsilon(\sigma).$$

La décomposition en cycles d'une permutation $\sigma$ peut se voir comme une écriture de $\sigma$ en un produit de permutations qui n'ont qu'un seul cycle. Les cycles en question étant disjoints, ces permutations commutent deux à deux.

La signature d'une permutation est donc le produit des signatures de ses cycles. Comme le cycle $(1,2,\ldots,k)$ possède exactement $k-1$ inversions, la signature de tout $k$-cycle est donc $(-1)^{k-1}$.

L'existence de la signature peut aussi se voir en considérant l'action des permutations sur le polynôme $$\Delta_n(x_1,\ldots,x_n) = \prod_{i

$\Delta_n$ est en fait un déterminant (dit de Vandermonde), et c'est la découverte de la signature qui a conduit à l'invention des déterminants.

Le triangle Stirling1

Il est facile de donner une récurrence pour le nombre $\left[n\atop k\right]$ de permutations de ${\mathfrak S}_n$ ayant $k$ cycles.

Pour fabriquer une telle permutation, on peut soit partir d'une permutation de $n-1$ ayant $k-1$ cycles, et laisser $n$ tout seul, ce qui donne $\left[n-1\atop k-1\right]$ possibilités, soit partir d'une permutation de $n-1$ ayant $k$ cycles, et insérer $n$ dans l'un des cycles. Il y a $n-1$ manières de le faire, correspondant aux $n-1$ choix possibles de son prédécesseur dans un cycle. Donc, $$\left[n\atop k\right]=\left[n-1\atop k-1\right]+(n-1)\left[n-1\atop k\right],$$ avec les conditions initiales $\left[n\atop 0\right]=0$ pour $n\ge 1$ (et la convention $\left[0\atop 0\right]=1$).

In [ ]: