Naszyjnik (kombinatoryka)

3 bransoletki z 3 czerwonymi i 3 zielonymi koralikami. Ten w środku jest chiralny , więc są 4 naszyjniki. Porównaj pudełko (6,9) w trójkącie.

11 bransoletek z 2 czerwonymi, 2 żółtymi i 2 zielonymi koralikami. Ten najbardziej na lewo i cztery najbardziej na prawo są chiralne, więc jest 16 naszyjników. Porównaj ramki (6,7) w trójkącie.

16 płytek z gry Tantrix , odpowiadających 16 naszyjnikom z 2 czerwonymi, 2 żółtymi i 2 zielonymi koralikami.

W kombinatoryce k -arowy naszyjnik o długości n jest klasą równoważności n -znakowych ciągów w alfabecie o rozmiarze k , przyjmując wszystkie obroty jako równoważne . Reprezentuje strukturę z n połączonych kołowo koralików, które mają k dostępnych kolorów.

Bransoletka k -ary , zwana także naszyjnikiem obrotowym ( lub swobodnym ) , to naszyjnik, w którym sznurki mogą być również równoważne przy odbiciu . To znaczy, biorąc pod uwagę dwa ciągi, jeśli każdy jest odwrotnością drugiego, należą one do tej samej klasy równoważności. Z tego powodu naszyjnik można również nazwać naszyjnikiem stałym , aby odróżnić go od naszyjnika obrotowego.

Formalnie naszyjnik można przedstawić jako orbitę grupy cyklicznej działającej na n -znakowych ciągach nad alfabetem o rozmiarze k , a bransoletkę jako orbitę grupy dwuściennej . Można policzyć te orbity, a tym samym naszyjniki i bransoletki, używając twierdzenia Pólyi o wyliczaniu .

Klasy równoważności

Liczba naszyjników

Główny artykuł: Naszyjnik wielomianowy

Tam są

${\ Displaystyle N_ {k} (n) = {\ Frac {1} {n}} \ suma _ {d \ mid n} \ varphi (d) k ^ {\ frac {n}{d}}}$

różne naszyjniki k -ary o $totientową$ n , gdzie jest funkcją Eulera . Wynika to bezpośrednio z twierdzenia Pólyi o wyliczeniu do działania grupy cyklicznej $}$ zbiorze wszystkich funkcji ${\ Displaystyle f: \ {1, \ ldots, n \} \ do \ {1, \ ldots, k \}}$ . Istnieje również

${\ Displaystyle L_ {k} (n) = {\ Frac {k!} {n}} \ suma _ {d \ mid n} \ varphi ( d)S({\frac {n}{d}},k)}$

$k$ naszyjniki o długości dokładnie różnymi kolorowymi koralikami , gdzie Stirlinga drugiego rodzaju (Zmienna k jest przeciążona i nie jest jasne, czy k odnosi się do rozmiaru alfabetu, czy do liczby odrębnych elementów naszyjnika.)

${\ Displaystyle N_ {k} (n)}$ (sekwencja A054631 w OEIS ) i ${\ Displaystyle L_ {k} (n)}$ (sekwencja A087854 w OEIS ) są powiązane poprzez współczynniki dwumianowe :

${\ Displaystyle N_ {k} (n) = \ suma _ {j = 1} ^ {k} {\ binom {k} j}}L_{j}(n)}$

I

${\ Displaystyle L_ {k} (n) = \ suma _ {j = 1} ^ {k} (-1)^{kj}{\binom {k}{j}}N_{j}(n)}$

Liczba bransoletek

Istnieje w sumie

${\ Displaystyle B_ {k} (n) = {\ rozpocząć {przypadki} {\ tfrac {1} {2}} N_ {k} (n) + {\ tfrac {1} {4}} (k + 1) k^{n/2}&{\text{jeśli }}n{\text{ jest parzysta}}\\[10px]{\tfrac {1}{2}}N_{k}(n)+{\tfrac {1}{2}}k^{(n+1)/2}&{\text{if }}n{\text{ jest nieparzyste}}\end{przypadki}}}$

różne k -ary bransoletki o długości n , gdzie N _k ( n ) to liczba k - ary naszyjników o długości n . Wynika to z metody Pólyi zastosowanej do działania grupy dwuściennej ${\ displaystyle D_ {n}}$ .

Przypadek różnych koralików

Możliwe układy bransoletek o długości n odpowiadające k -temu podziałowi całkowitemu ( ustaw podziały aż do obrotu i odbicia)

Dla danego zestawu n koralików, z których wszystkie są różne, liczba różnych naszyjników wykonanych z tych koralików, licząc obrócone naszyjniki jako takie same, wynosi n ! / n = ( n - 1)!. Dzieje się tak, ponieważ koraliki można uporządkować liniowo w n ! sposobów, a n kołowych przesunięć takiego uporządkowania daje ten sam naszyjnik. Podobnie liczba różnych bransoletek, licząc bransoletki obrócone i odbite jako takie same, wynosi n ! / 2 n , dla n ≥ 3.

Jeśli koraliki nie są różne i mają powtarzające się kolory, jest mniej naszyjników (i bransoletek). Powyższe wielomiany liczenia naszyjników podają liczbę naszyjników wykonanych ze wszystkich możliwych multisetów koralików. Wielomian inwentaryzacji wzoru Polya udoskonala wielomian zliczania, używając zmiennej dla każdego koloru koralików, tak aby współczynnik każdego jednomianu zliczał liczbę naszyjników na danym zestawie wielu koralików.

Naszyjniki aperiodyczne

Aperiodyczny naszyjnik o długości n jest klasą równoważności rotacji o rozmiarze n , tzn. żadne dwa odrębne obroty naszyjnika z takiej klasy nie są sobie równe.

Zgodnie z funkcją liczenia naszyjników Moreau , są

${\ Displaystyle M_ {k} (n) = {\ Frac {1} {n}} \ suma _ {d \ mid n} \ mu (d)k ^ {\frac {n}{d}}}$

różne k -ary aperiodyczne naszyjniki o długości n , gdzie μ jest funkcją Möbiusa . Te dwie funkcje liczenia naszyjników są powiązane przez: ${\ textstyle N_ {k} (n) = \ suma _ {d | n} M_ {k} (d)}}$ gdzie suma jest po wszystkich dzielnikach n , co jest równoważne przez Möbiusa inwersja do ${\ textstyle M_ {k} (n) = \ suma _ {d | n} N_ {k} (d) \ \ mu {\ bigl (}{\ tfrac {n}{d}} {\ bigr)} .}$

Każdy aperiodyczny naszyjnik zawiera jedno słowo Lyndona , tak więc słowa Lyndona tworzą przedstawicieli aperiodycznych naszyjników.

Zobacz też

• Słowo Lyndona
• Inwersja (matematyka dyskretna)
• Problem z naszyjnikiem
• Problem z pękającym naszyjnikiem
• Permutacja
• Dowody małego twierdzenia Fermata # Dowód przez liczenie naszyjników
• Liczba Forte , reprezentacja binarnych bransoletek o długości 12, używana w muzyce atonalnej .

Linki zewnętrzne

• Weisstein, Eric W. „Naszyjnik” . MathWorld .
• Ruskey, Frank (2006). „Informacje o naszyjnikach, słowa Lyndona, sekwencje De Bruijn” . Zarchiwizowane od oryginału w dniu 2006-10-02.
• Ruskey, Frank; Dziki, Carla; Wang, Terry Min Yih (1992). „Generowanie naszyjników”. Dziennik algorytmów . 13 (3): 414–430. doi : 10.1016/0196-6774(92)90047-G .