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.

babsgueye

Salut.

J'ai pas suivi l'autre discussion (à propos de train). Et je ne vois pas du tout d'où @GBZM sort sa formule (j'ai l'impression qu'il se mélange les pédales un peu dans ses explications).

Pour le sujet que je lis ici, je pense que $C_0 = 1,\,C_1 = p$ comme @soc a dit, $C_2 = p(p - 1),\,C_3 = p(p - 1)(p - 2)$ et pour la suite $C_n = (p - 2)C_{n-1}$ tout simplement.

Soc

La formule de récurrence proposée par GBZM est bien la bonne  $C_n=(p-2)C_{n-1}+(p-1)C_{n-2}$. Pour la comprendre:

* Si, là où l'on rajoute la dernière perle, il y a de chaque côté deux perles de couleurs différentes, alors il nous reste p-2 choix pour la nouvelle, d'où le terme $(p-2)C_{n-1}$.

* Pour compter le nombre de cas contraires, on prend un collier respectant les consignes de n-2 perles ($C_{n-2}$), ensuite on rajoute une perle de même couleur que la première (1 seul choix), et ensuite on rajoute la dernière perle (p-1 choix) d'où le terme $(p-1)C_{n-2}$.
(edit: ici, il faut bien comprendre que le fait de respecter la consigne impose le fait que dans le collier de n-2 la première et la dernière sont de couleurs différentes, donc on peut bien en insérer une de la même couleur que la première)

Pour la formule finale on s'appuie ensuite sur les suites récurrentes linéaires d'ordre 2, et l'on obtient $C_n = (p-1)^n + (p-1) (-1)^n$ comme cela a déjà été détaillé plus haut.

Médiat_Suprème

Il y a quelques années je m'étais penché sur un problème cousin :

Riemann_lapins_cretins

On fait tous la même erreur que babsgueye en réfléchissant vite mais on constate après coup qu'on oublie "la moitié" des coloriages en faisant juste l'ajout du dernier wagon.

babsgueye

Ah ok. Merci je vois maintenant.

babsgueye

Je pense qu'il faut quand mème s'assurer que $C_1 = p$, et que la relation de récurrence va donner $C_n = p(p - 1)^{n-1}$ au lieu de la formule donnée par @Lol_a. Je me trompe ?

GaBuZoMeu

Tu te trompes.

babsgueye

Tu peux m'expliquer ?

Ou bien c'est ce que tu as déjà fait ; je n'ai pas compris tes explications sur le collier $(c_0, c_1,\dots, c_n)$ comment tu l'appliques sur un collier à une perle.

Soc

Pour $C_1$, soit, comme GBZM, tu considères que la perle toute seule est consécutive à elle-même et comme elle est de la même couleur, cela ne convient pas et tu dis $C_1=0$, soit, comme moi, tu considères que la perle seule n'est consécutive de personne et dans ce cas tu dis $C_1=p$.

C'est juste un choix d'interprétation de ce qui signifie des "perles consécutives" pour un collier d'une seule perle et n'a pas d'importance pour le reste. Cela ne changera pas la relation de récurrence, mais cela changera le rang à partir duquel elle sera valide et donc avec quels termes tu vas l'initier. Dans les deux cas au final la formule est bien $C_n = (p-1)^n + (p-1) (-1)^n$ et cette formule a été expliquée dans le post de Lol_a.

babsgueye

J'ai bien vu le post de @Lol_a, mais lui il utilise pour finir ses calculs $C_1 = 0$, moi $C_1 = p$ comme tu dis.

Je pense que cela ne se limite pas seulement à un problème d'interprétation. Quelqu'un a tort l'autre a raison, parce que ça influe sur les valeurs des $(C_n)_{n\geq 4}$.

Pour se rassurer, on peut essayer de dénombrer $C_4$ avec les deux résultats des deux interprétations pour voir. On trouve 108 et 84 et je pense que 108 et bon résultat.

GaBuZoMeu

Tu te trompes encore une fois en pensant ça.

Si on choisit $C_1=p$, alors la relation de récurrence $C_n=(p-2)C_{n-1}+(p-1)C_{n-2}$ n'est valable que pour $n\geq 4$

babsgueye

C'est possible, je veux juste en avoir le cœur net. Je me donnerais le temps de dénombrer.

Soc

Peu importe ce que l'on décide pour $C_1$ dans les deux cas on est d'accord sur le fait que $C_2=p(p-1)$ et $C_3=p(p-1)(p-2)$ Donc en utilisant la relation de récurrence à partir de $C_4$ on trouve forcément le même terme général.

Ce qui change c'est que si l'on décide que $C_1=p$ alors la relation de récurrence ne fonctionne pas pour $C_3$, du coup on est dans ce cas obligé de commencer à $C_4$ et pas avant.

Cette relation ne fonctionne pas pour $C_3$ car ...

Soc a dit :

* Pour compter le nombre de cas contraires, on prend un collier respectant les consignes de n-2 perles ($C_{n-2}$), ensuite on rajoute une perle de même couleur que la première (1 seul choix), et ensuite on rajoute la dernière perle (p-1 choix) d'où le terme $(p-1)C_{n-2}$.

(edit: ici, il faut bien comprendre que le fait de respecter la consigne impose le fait que dans le collier de n-2 la première et la dernière sont de couleurs différentes, donc on peut bien en insérer une de la même couleur que la première)

... dans cette étape quand il n'y a plus qu'une pierre on ne peut pas en rajouter une de la même couleur que la première, en revanche pour ceux qui ont décidé que $C_1=0$ cela fonctionne encore. A partir de $C_4$ on n'a plus ce problème.

GaBuZoMeu

Je raisonnerais plutôt dans l'autre sens :

Je note $\mathcal C_n$ l'ensemble des colliers de $n$ perles satisfaisant la condition. Je note aussi $\mathcal P$ l'ensemble des couleurs ($\mathcal C_n$ est une partie de $\mathcal P^n$).

On part d'un collier de $\mathcal C_n$ ($n \geq 3$).

Si les perles $0$ et $n-2$ sont de couleurs différentes, on a en enlevant la perle $n-1$ un collier de $\mathcal C_{n-1}$, et tout collier de $\mathcal C_{n-1}$ est ainsi obtenu à partir de $p-2$ colliers de $\mathcal C_n$.

Si les perles $0$ et $n-2$ sont de même couleur, alors les perles $0$ et $n-3$ sont de couleurs différentes, on a en enlevant les perles $n-1$ et $n-2$ un collier de $\mathcal C_{n-2}$, et tout collier de $\mathcal C_{n-2}$ (si on a bien défini $C_1$ dans le cas $n=3$ !) est ainsi obtenu à partir de $p-1$ colliers de $\mathcal C_n$.

On établit en fait une bijection entre $\mathcal C_n$ et la réunion disjointe de $\{(\mathbf c,d)\in \mathcal C_{n-1}\times \mathcal P\mid d\not\in\{c_0,c_{n-2}\}\}$ et de $\{(\mathbf c,d)\in \mathcal C_{n-2}\times \mathcal P\mid d\neq c_0\}$

babsgueye

Mon dénombrement me donne bien $|C_4| = 84$. Ça va, merci tous les deux.