Algèbre T1
ω : B → R, à valeurs dans un anneau commutatif quelconque contenant Q. Le
poids de la fonction f est par définition ω(f ) =
a∈A ω(f (a)) ; en particulier,
le poids est constant sur les orbites sous G de B A . La formule d’énumération de
Polya, avec poids, nous dit que :
o∈O
ω(o) =
1
Card(G)
g∈G
b∈B
ω(b)
c 1 (g)
. . .
b∈B
ω(b)
n
cn(g)
(1)
où c i (g) désigne le nombre de cycles de longueur i dans la décomposition canonique
de g. Le type de g nous renseigne donc sur les coefficients c i .
La démonstration de cette formule utilise une version avec poids du lemme de
Burnside :
o∈O
ω(o) =
1
Card(G)
g∈G
g·f =f
ω(f )
(on retrouve la formule de Burnside classique en prenant pour ω la fonction
constante de valeur 1). De plus, si g = α 1 . . . α r est la décomposition en cycles, les
fonctions fixes par g sont en bijection avec les r-uplets (b 1 , . . . , b r ) ∈ B r (b i désigne
la valeur de f sur le cycle α i ). Le poids d’une telle fonction est ω(f ) =
ω(a i ) l i ,
où l i désigne la longueur du cycle α i . On termine la preuve en injectant cette
égalité dans la formule de Burnside (en exercice).
☞ Quelques commandes Maple utiles : mul ; on peut simplifier et ordonner une expression polynômiale P (x 1 , . . . , x n ) par la succession de commandes
sort(normal(P)).
12. La formule d’énumération de Polya permet de dénombrer des objets considérés
modulo certaines symétries. Par exemple, on s’intéresse aux colliers de n perles
différents que l’on peut réaliser avec des perles rouges ou bleues. Par définition,
deux tels objets sont considérés comme différents s’il ne sont pas égaux modulo
une permutation circulaire (le fermoir est invisible).
Dénombrer à la main les colliers à 5 perles. Combien y en a-t-il à 3 boules
rouges et 2 boules bleues ? Pour n = 10 par exemple, il est impossible de
dénombrer à la main : on utilise le formalisme de Polya exposé ci-dessus.
Définir une fonction Z renvoyant, en fonction du groupe de permutations G
et de la liste W des poids des éléments de B, le résultat de la formule de
Polya (1). On pourra utiliser la procédure typ écrite au cours du TP.I.
Un collier réalisé à partir de perles rouges ou bleues est une fonction de
{1, . . . , n} dans l’ensemble {rouge, bleu}. En prenant comme poids la fonction constante de valeur 1, puis en attribuant à rouge un poids « formel »
114
ω : B → R, à valeurs dans un anneau commutatif quelconque contenant Q. Le
poids de la fonction f est par définition ω(f ) =
a∈A ω(f (a)) ; en particulier,
le poids est constant sur les orbites sous G de B A . La formule d’énumération de
Polya, avec poids, nous dit que :
o∈O
ω(o) =
1
Card(G)
g∈G
b∈B
ω(b)
c 1 (g)
. . .
b∈B
ω(b)
n
cn(g)
(1)
où c i (g) désigne le nombre de cycles de longueur i dans la décomposition canonique
de g. Le type de g nous renseigne donc sur les coefficients c i .
La démonstration de cette formule utilise une version avec poids du lemme de
Burnside :
o∈O
ω(o) =
1
Card(G)
g∈G
g·f =f
ω(f )
(on retrouve la formule de Burnside classique en prenant pour ω la fonction
constante de valeur 1). De plus, si g = α 1 . . . α r est la décomposition en cycles, les
fonctions fixes par g sont en bijection avec les r-uplets (b 1 , . . . , b r ) ∈ B r (b i désigne
la valeur de f sur le cycle α i ). Le poids d’une telle fonction est ω(f ) =
ω(a i ) l i ,
où l i désigne la longueur du cycle α i . On termine la preuve en injectant cette
égalité dans la formule de Burnside (en exercice).
☞ Quelques commandes Maple utiles : mul ; on peut simplifier et ordonner une expression polynômiale P (x 1 , . . . , x n ) par la succession de commandes
sort(normal(P)).
12. La formule d’énumération de Polya permet de dénombrer des objets considérés
modulo certaines symétries. Par exemple, on s’intéresse aux colliers de n perles
différents que l’on peut réaliser avec des perles rouges ou bleues. Par définition,
deux tels objets sont considérés comme différents s’il ne sont pas égaux modulo
une permutation circulaire (le fermoir est invisible).
Dénombrer à la main les colliers à 5 perles. Combien y en a-t-il à 3 boules
rouges et 2 boules bleues ? Pour n = 10 par exemple, il est impossible de
dénombrer à la main : on utilise le formalisme de Polya exposé ci-dessus.
Définir une fonction Z renvoyant, en fonction du groupe de permutations G
et de la liste W des poids des éléments de B, le résultat de la formule de
Polya (1). On pourra utiliser la procédure typ écrite au cours du TP.I.
Un collier réalisé à partir de perles rouges ou bleues est une fonction de
{1, . . . , n} dans l’ensemble {rouge, bleu}. En prenant comme poids la fonction constante de valeur 1, puis en attribuant à rouge un poids « formel »
114