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.