Collier de perles
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 !
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)$.
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)$.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
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
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.
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.
Saurais-tu dire en quelle classe les suites récurrentes linéaires d'ordre 2 sont au programme?
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).
En tout cas je maintiens ma question de la preuve par bijection. J'aime bien les preuves par bijection.
Pour la bijection, aucune idée, désolée.
(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)
J'affirme péremptoirement que toute affirmation péremptoire est fausse
... 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.