Collier de perles

Soc

Préambule.
Suite à la feuille d'exercices de dénombrement postée par JLT, je me suis posé la question d'une extension de l'exercice 3 dans le cas où le train est circulaire (pas pratique pour un train vous me direz). LOU16 m'a donné la solution en mp, que je vais partager ici (*) au cas où cet exercice vous plaise aussi.
(*) Dans le cas somme toute peu probable où elle n'apparaisse pas toute seule dans ce fil !

Exercice.
On dispose de perles de p couleurs différentes. De combien de façons différentes peut-on constituer un collier de n perles tel qu’il n’y ait pas 2 perles consécutives de la même couleur ? On considère que la position des perles est numérotée, par exemple le collier $(rouge;vert)$ est différent du collier $(vert;rouge)$.

Lol_a

On peut reprendre la même logique que pour le train. Ce qui change c'est que cette fois-ci pour peindre le dernier wagon il faut aussi s'assurer qu'il ne soit pas de la même couleur que le premier. Le nombre de couleurs disponibles pour le dernier wagon dépend est donc différent selon si le premier et l'avant-dernier wagon ont la même couleur ou non. Reste à compter le nombre de configuration possible pour chacun des cas et là il faut que j'y réfléchisse. Exercice intéressant en tout cas, merci.

Riemann_lapins_cretins

Si je ne dis pas de bêtises il y a Burnside en faisant agir Z/nZ sur les bons coloriages.
Un élément fixe par un élément $g$ qui engendre le sous-groupe d'ordre $d$ est le choix d'une liste de $\frac{n}{d}$ couleurs non successivement identiques (et avec le premier et le dernier élément distincts), ce qui ramène quasiment à l'exercice précédent.

Édit : ou j'ai mal compris et on ne suppose pas les coloriages identiques par rotation et la question est justement de connaître le cardinal des fameux fixateurs

Soc

Je ne connais pas la formule de Burnside, mais je crois pouvoir répondre à ta question en disant que dans cet exercice on numérote les perles et donc on considère (rouge;vert) comme différent de (vert;rouge).
En revanche, comme l'a dit Lol_a le raccord à l'exercice précédent n'est pas si trivial... si tant est qu'on parvienne à les relier.

Riemann_lapins_cretins

D'accord, la circularité n'est là que pour contraindre les deux extrêmes. Ce n'est pas un des grands problèmes de coloriages de colliers de perle.
En soupçonnant que la difficulté était ailleurs j'ai raisonné un peu vite et me suis dit qu'il suffisait de partir d'un train rectiligne de taille n-2 et d'y accoler la tête et la queue.

Soc

C'est effectivement plus simple que de chercher tous les colliers possibles de n perles avec p couleurs!

GaBuZoMeu

Bonjour,

Si on note $C_n$ le nombre de colliers à $n$ perles, on a $C_0=1$, $C_1=0$, $C_2=p(p-1)$, $C_3=p(p-1)(p-2)$ et après $C_n=(p-2)C_{n-1}+(p-1)C_{n-2}$.

Soc

Oui c'est effectivement cette relation de récurrence, que je trouve jolie car il n'est pas si facile de retomber sur ses pieds dans cet exercice et de ne pas oublier de cas ni d'en compter en double. Pour $C_1$ je dirais plutôt qu'il vaut $p$, mais c'est un cas pathologique pas vraiment intéressant (sauf si l'on pense initier la récurrence un cran plus tôt).

GaBuZoMeu

Si la condition pour le collier $(c_0,\ldots,c_{n-1})$ (chaque $c_i$ est une des $p$ couleurs) s'écrit $\forall i\in \{0,\ldots,n-1\}\ c_{i}\neq c_{(i+1)\bmod n}$, on a bien $C_1=0$.

Soc

Oui, j'ai bien compris que tu considérais que la perle seule était consécutive à elle-même Encore une fois cela n'a pas beaucoup d'importance.
Saurais-tu dire en quelle classe les suites récurrentes linéaires d'ordre 2 sont au programme?

Riemann_lapins_cretins

Première année de supérieur, en application de l'algèbre linéaire.

Soc

Merci!

Riemann_lapins_cretins

J'up ce sujet pour demander si quelqu'un aurait une résolution du problème par bijection, quite à faire du retro ingenering en exploitant la solution déjà trouvée pour avoir l'expression en fonction de $p$ et $n$ directement.

Math Coss

L'expression est une combinaison linéaire de $(p-1)^n$ et $(-1)^n$. Est-ce que quelqu'un aurait l'obligeance de calculer les coefficients ?

Lol_a

On peut obtenir une expression en fonction de $p$ et $n$ à partir de la relation de récurrence donnée plus haut.
On peut vérifier que $C_2 = (p-2)C_{1}+(p-1)C_{0}$ mais en revanche $C_3 = (p-2)C_{2}+(p-1)C_{1}$ donc la formule $C_n=(p-2)C_{n-1}+(p-1)C_{n-2}$ est vraie pour $n \geq 3$. On note aussi qu'on doit avoir $p >1$.
Le polynôme $X^2-(p-2)X - (p-1)$ (polynôme caractéristique de la suite $(C_n)_ {n \geq 1}$) a deux racines distinctes $-1$ et $p-1$ (relation coefficients-racines mais on peut aussi utiliser la méthode usuelle).
Ainsi, il existe deux réels $a$ et $b$ tels que pour $n \geq 1$, on ait : 
$C_n = a (p-1)^n + b (-1)^n$
Or, $C_1 = 0$ et $C_2 = p(p-1)$. $a$ et $b$ dont donc solutions du système ci-dessous : 
$\begin{cases} a(p-1) -b = 0 \\ a(p-1) ^2 + b = p(p-1) \end{cases}$
On résout (en se rappelant que $p>1$ donc $p\neq 1$) et on trouve : 
$\begin{cases}a = 1 \\ b = p-1 \end{cases}$
Ainsi, pour $n \geq 1$, $C_n = (p-1)^n + (p-1) (-1)^n$. 
On peut vérifier que ça marche pour $C_3$ (pas fais je cas général).

Riemann_lapins_cretins

Je pense que MC avait juste la flémme plus qu'un problème de méthode.

En tout cas je maintiens ma question de la preuve par bijection. J'aime bien les preuves par bijection.

Lol_a

Ah oui, je n'avais pas vu mais effectivement @Math Coss a répondu pendant que je rédigeais mon message.
Pour la bijection, aucune idée, désolée.

Riemann_lapins_cretins

Bah, je pense qu'il n'y a pas vraiment de bijection sur un ensemble commode à cause du $(-1)^{n}$.

Mais en fait toute preuve directe (sans passer par une relation de récurrence) m'intéresserait si un membre en trouve une. Je trouve qu'en combinatoire ce type de preuve fait souvent réfléchir à des choses profondes.

On peut ajouter si je ne me trompe pas que le nombre de coloriages d'une roulette à $n$ secteurs avec $p$ couleurs sans avoir deux cases successives de même couleur, en considérant que tous les coloriages déduits les uns des autres par rotation sont identiques, vaut : 

$$ \frac{1}{n} \sum_{d | n} \phi(\frac{n}{d})[(p-1)^{d} + (p-1)(-1)^{d}],$$ avec $\phi$ l'indicatrice d'Euler.

GaBuZoMeu

La relation de récurrence se montre assez facilement par bijection.

Riemann_lapins_cretins

Oui, mais ce n'est pas ce que je veux.

GaBuZoMeu

On n'a pas toujours ce qu'on veut, il faut s'y faire ...

Riemann_lapins_cretins

Peut-être que si, je demande juste, c'est bon oh, enfin, dites donc, bon.