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)$.
The fish doesnt think. The Fish doesnt think because the fish knows. Everything. - Goran Bregovic
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.
-
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 -
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.
The fish doesnt think. The Fish doesnt think because the fish knows. Everything. - Goran Bregovic -
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!
The fish doesnt think. The Fish doesnt think because the fish knows. Everything. - Goran Bregovic -
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).
The fish doesnt think. The Fish doesnt think because the fish knows. Everything. - Goran Bregovic -
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?
The fish doesnt think. The Fish doesnt think because the fish knows. Everything. - Goran Bregovic -
Première année de supérieur, en application de l'algèbre linéaire.
-
Merci!
The fish doesnt think. The Fish doesnt think because the fish knows. Everything. - Goran Bregovic -
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 ?
-
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. -
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.
-
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.
-
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.The fish doesnt think. The Fish doesnt think because the fish knows. Everything. - Goran Bregovic -
Il y a quelques années je m'étais penché sur un problème cousin :Il ne faut pas respirer la compote, ça fait tousser.
J'affirme péremptoirement que toute affirmation péremptoire est fausse -
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.
-
Ah ok. Merci je vois maintenant.
-
Tu te trompes.
-
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.
-
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.The fish doesnt think. The Fish doesnt think because the fish knows. Everything. - Goran Bregovic
-
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.
-
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$
-
C'est possible, je veux juste en avoir le cœur net. Je me donnerais le temps de dénombrer.
-
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 ...
... 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.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)The fish doesnt think. The Fish doesnt think because the fish knows. Everything. - Goran Bregovic -
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\}$
-
Mon dénombrement me donne bien $|C_4| = 84$. Ça va, merci tous les deux.
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.1K Toutes les catégories
- 7 Collège/Lycée
- 21.9K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 52 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 62 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 312 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 772 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres
In this Discussion
Qui est en ligne 43
+30 Invités