Да, тази книга я имах навремето. За броенето на герданите и подобни работи си има обща теория. Ключовата дума е лемата на Бърнсайд (
https://en.wikipedia.org/wiki/Burnside%27s_lemma). Нямам спомен как го е направил М. Гарднър, но сигурно мимикрира това по-долу, без да използва термини като стабилизатор, орбита, действие на група в/у множество. Общата теория може да се намери в нета, напр. като се тръгне от горния линка. В случая имаме групата $G$ от отражения и ротации, която действа в/у множеството $X$ от всички оцветявания в $a$ цвята на $n$ правилно наредени елемента $\{1,2,\dots,n\}$ в/у окръжност. Да ги наречем гердани, но различаваме тези, които се получават чрез въртене/отражение. Очевидно $|X|=a^n$. Ако $g\in G, x\in X$, то $gx=y$ е гердана $y$, който се получава от гердана $x$, като му се приложи съответната ротация/отражение $g$. Всъщност $G$ е точно диедралната група $D_n$, която има $2n$ елемента (n ротации и n отражения). Орбита $Gx\subset X$ на елемента $x\in X$ се нарича $Gx:=\{gx : g\in G\}$. Лесно се вижда, че орбитите на различните $x\in X$ или съвпадат или не се пресичат. Всъщност орбитата на някакво $x\in X$ може да се тълкува като онези елементи от $X$, които не се различават. Ако вземем един гердан и почнем да го въртим и отразяваме, всичко което се получава е неразличимо, един вид това е един и същи гердан. Стабилизатор на $g\in G$ се нарича подмножеството $X_g$ на $X$ от неподвижните точки при прилагане на $g$, т.е. $X_g := \{x\in X : gx=x\}$. Със $X/G$ се означава множеството на всички орбити. Лемата на Бърнсайд дава броя на тези орбити, изразени чрез стабилизаторите:
$$|X/G|=\frac{1}{|G|}\sum_{g\in G}|X_g|$$
Т.е. броя на орбитите е усреднената големина на стабилизатора по всички $g\in G$. Сега вижте отговора в поста по-горе. Имаме делене на $2n$, точно колкото е $|G|$. Последния член е сумата от стабилизаторите на отраженията. Затова има разлика при четни и нечетни $n$ - има принципно различни отражения. Първите членове са сумата от стабилизаторите на ротациите. Една ротция се определя от завъртане $r$ обратно на час. стрелка, $0\le r\le n-1$. При $а=0$ имаме (идентитета) броя на елементите на стабилизатора е $|X|=a^n$. Ako $(r,n)=1$, тази ротация оставя неподвижни само гердани с едноцветни мънисти, т.е. $|X_r|=a$. И тъй като има $\varphi(n)$ такива $r$-та - ето ви го члена $\varphi(n)a^{n/n}$
Нека сега $(r,n)=d$. Стабилизаторът $X_r$ състои от гердани, за които мънистата $d-k,2d-k,\dots, (n/d)d-k$ са едноцветни за всяко $k=0,1,\dots,d_i-1$. Броят на тези гердани е $a^{d}$, а всички ротации ($r$-та) за които $(r,n)=d$ са точно тези $r=\ell d, (\ell,d)=1$, т.е. $\varphi(n/d)$ на брой. От там идва и члена $\varphi(n/d) a^{d}$ (само са разменени $d$ и $n/d$, ама те и двата са делители, така че е същия запис).
Това е. Може да потърсите из нета Burnside lemma, Polya enumeration theorem, ето и още по-смляно
https://en.wikipedia.org/wiki/Necklace_(combinatorics) .
Меню
