Perles
Bonjour.
Combien de colliers différents de 32 perles peut-on assembler
aves des perles de cornaline et de turquoise ?
Combien de colliers différents de 32 perles peut-on assembler
aves des perles de cornaline et de turquoise ?
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Soit $\displaystyle n=32$ perles parmi lesquelles $c$ de cornaline et $t$ de turquoise. On a donc $\displaystyle c+t=n.$
Le nombre de permuations circulaires est le coefficient de $\displaystyle x^cy^t$ dans l'expression $\displaystyle {1 \over n} \sum_{d\mid n} (x^{n/d} + y^{n/d})^d \varphi(n/d).$
Cette expression vaut $\displaystyle {1 \over 32} \Big((x+y)^{32}\varphi(1) + (x^2+y^2)^{16} \varphi(2) + (x^4+y^4)^{8} \varphi(4) + (x^8+y^8)^{4} \varphi(8) + (x^{16}+y^{16})^{2} \varphi(16) +(x^{32}+y^{32}) \varphi(32) \Big)$ avec, par le calcul, $\displaystyle \varphi(1) = 1, \varphi(2) = 1, \varphi(4) = 2, \varphi(8) = 4, \varphi(16) = 8, \varphi(32) = 16.$
Cette expression vaut donc $\displaystyle x^{32} + x^{31} y + 16 x^{30} y^2 + 155 x^{29} y^3 + 1128 x^{28} y^4 + 6293 x^{27}y^5+ 28336 x^{26}y^6 + 105183 x^{25} y^7 + 328756 x^{24} y^{8} + ...$
Par exemple, pour $32$ perles de même nature, on trouve $2$ collier ; pour $1$ perle de nature différente des autres, on trouve $2$ colliers ; pour $2$ perles de même nature mais différentes des autres, on trouve $16$ permutations mais seulement $8$ colliers car chaque collier est vu recto-verso ; pour $3$ perles de même nature mais différentes des autres, on trouve $155$ permutations mais seulement $(155-1)/2 + 1 = 77+1=78$ colliers et donc $2 \times 78=156$ colliers pour les deux natures différentes. corrigé après la remarque ci-dessous.
On procède ainsi sur tous les coefficients et on somme. Je parie qu'on trouve le résultat de @GaBuZoMeu ;-).
Je te rappelle qu'il y a deux sortes de perles.
Il y a deux colliers mono-genre : le turquoise et le cornalin.
Il y a deux colliers avec une perle différente de toutes les autres :
celui ou l'intruse est turquoise et celui ou l'intruse cornaline.
GBZM applique le théorème de Polya sur le comptage d'orbites. (Mot clé : Théorème de Pòlya).
Le groupe qui agit sur l'ensemble des $2^{32}$ colliers fixes est le groupe diédrique $D_{32}$.
Je me suis mal exprimé. J'ai corrigé mon message.
En tout cas, ce théorème de Polya ne doit pas être tout à fait immédiat... je regarderai sur Wikipedia mais je doute pouvoir suivre.