Collier de perles — Les-mathematiques.net The most powerful custom community solution in the world

Collier de perles

SocSoc
Modifié (3 Aug) dans Combinatoire et Graphes
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)$.

Réponses

  • 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.
  • Modifié (3 Aug)
    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
  • SocSoc
    Modifié (3 Aug)
    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.
  • Modifié (3 Aug)
    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.
  • C'est effectivement plus simple que de chercher tous les colliers possibles de n perles avec p couleurs!
  • 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}$.
  • 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).
  • Modifié (4 Aug)
    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$.
  • 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?
  • Première année de supérieur, en application de l'algèbre linéaire.
  • Merci!
  • 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.
  • 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 ?
  • Modifié (6 Aug)
    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).
  • 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.
  • 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.
  • Modifié (6 Aug)
    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.
  • La relation de récurrence se montre assez facilement par bijection.
  • Oui, mais ce n'est pas ce que je veux.
  • On n'a pas toujours ce qu'on veut, il faut s'y faire ... :)
  • Peut-être que si, je demande juste, c'est bon oh, enfin, dites donc, bon.
Connectez-vous ou Inscrivez-vous pour répondre.
Success message!