Halsband (kombinatorik)

De 3 armbanden med 3 röda och 3 gröna pärlor. Den i mitten är kiral , så det finns 4 halsband. Jämför box(6,9) i triangeln.

De 11 armbanden med 2 röda, 2 gula och 2 gröna pärlor. Den längst till vänster och de fyra längst till höger är kirala, så det finns 16 halsband. Jämför box(6,7) i triangeln.

16 brickor från spelet Tantrix , motsvarande de 16 halsbanden med 2 röda, 2 gula och 2 gröna pärlor.

I kombinatorik är ett k -ary- halsband med längden n en ekvivalensklass av n - teckensträngar över ett alfabet av storleken k , vilket tar alla rotationer som ekvivalenta. Den representerar en struktur med n cirkulärt förbundna pärlor som har k tillgängliga färger.

Ett k -ary -armband , även kallat ett omsättnings- (eller gratis ) halsband , är ett halsband så att strängar också kan vara likvärdiga under reflektion. Det vill säga, givet två strängar, om var och en är motsatsen till den andra, tillhör de samma ekvivalensklass. Av denna anledning kan ett halsband också kallas ett fast halsband för att skilja det från ett omsättningshalsband.

Formellt kan man representera ett halsband som en omloppsbana av den cykliska gruppen som verkar på n -teckensträngar över ett alfabet av storlek k , och ett armband som en omloppsbana av den dihedriska gruppen . Man kan räkna dessa banor, och därmed halsband och armband, med hjälp av Pólyas uppräkningssats .

Ekvivalensklasser

Antal halsband

Det finns

N_{k}(n)={\frac {1}{n}}\summa _{d\mid n}\ varphi (d)k^{\frac {n}{d}}

olika k -ary-halsband med längden n , där $\varphi$ är Eulers totientfunktion . Detta följer direkt av Pólyas uppräkningssats tillämpad på verkan av den cykliska gruppen $C_{n}$ som verkar på mängden av alla funktioner $f:\{1,\ldots ,n\}\to \{1,\ldots ,k\}$ . Det finns också

L_{k}(n)={\frac {k!}{n}}\sum _{d\mid n}\varphi ( d)S({\frac {n}{d}},k)

olika halsband med längd n med exakt k olikfärgade pärlor, där $S(n,k)$ är stirlingtalet av den andra sorten . (Variabeln k är överbelastad och det är oklart om k hänvisar till alfabetets storlek eller till antalet distinkta element i halsbandet.)

$N_{k}(n)$ (sekvens A054631 i OEIS ) och $L_{k}(n)$ (sekvens A087854 i OEIS ) är relaterade via binomialkoefficienterna : _

N_{k}(n)=\summa _{j=1}^{k}{\binom {k}{ j}}L_{j}(n)

och

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

Antal armband

Det finns totalt

B_{k}(n)={\begin{cases}{\tfrac {1}{2}}N_{k}(n)+{\tfrac {1}{4}}(k+ 1)k^{n/2}&{\text{om }}n{\text{ är jämn}}\\[10px]{\tfrac {1}{2}}N_{k}(n)+{ \tfrac {1}{2}}k^{(n+1)/2}&{\text{om }}n{\text{ är udda}}\end{case}}

olika k -ary-armband med längden n , där Nk ( n ) är antalet k -ary-halsband med längden n _. Detta följer av Pólyas metod tillämpad på verkan av den dihedrala gruppen $D_{n}$ .

Fall av distinkta pärlor

Möjliga mönster av armband med längd n som motsvarar den k -te heltalspartitionen ( ställ in partitioner till rotation och reflektion)

För en given uppsättning av n pärlor, alla distinkta, är antalet distinkta halsband gjorda av dessa pärlor, om man räknar roterade halsband som samma, n ! / n = ( n − 1)!. Detta beror på att pärlorna kan beställas linjärt i n ! sätt, och de n cirkulära skiftningarna av en sådan beställning ger alla samma halsband. På samma sätt är antalet distinkta armband, om man räknar roterade och reflekterade armband som samma, n ! / 2 n , för n ≥ 3.

Om pärlorna inte alla är distinkta och har upprepade färger, så finns det färre halsband (och armband). Ovanstående halsbandsräknande polynom ger antalet halsband gjorda av alla möjliga multiuppsättningar av pärlor. Polyas mönsterinventeringspolynom förfinar räknepolynomet, med hjälp av variabel för varje pärlfärg, så att koefficienten för varje monomial räknar antalet halsband på en given multiuppsättning av pärlor.

Aperiodiska halsband

Ett aperiodiskt halsband med längden n är en rotationsekvivalensklass med storlek n , dvs inga två distinkta rotationer av ett halsband från en sådan klass är lika.

Enligt Moreaus halsbandsräkningsfunktion finns det

M_{k}(n)={\frac {1}{n}}\summa _{d\mid n}\ mu (d)k^{\frac {n}{d}}

olika k -ary aperiodiska halsband med längden n , där μ är Möbius-funktionen . De två halsbandsräkningsfunktionerna är relaterade till: ${\textstil N_{k}(n)=\summa _{d|n}M_{k}(d),}$ där summan är över alla divisorer av n , vilket är ekvivalent med Möbius inversion till ${\textstil M_{k}(n)=\summa _{d|n}N_{k}(d)\,\mu {\bigl (}{\tfrac {n}{d}}{\bigr )} .}$

Varje aperiodiskt halsband innehåller ett enda Lyndon-ord så att Lyndon-ord bildar representanter för aperiodiska halsband.

Se även

Lyndon ord
Inversion (diskret matematik)
Problem med halsband
Problem med att dela halsband
Permutation
Bevis på Fermats lilla teorem#Bevis genom att räkna halsband
Forte-nummer , en representation av binära armband med längd 12 som används i atonal musik .

externa länkar

Weisstein, Eric W. "Halsband" . MathWorld .
Ruskey, Frank (2006). "Information om halsband, Lyndon-ord, De Bruijn-sekvenser" . Arkiverad från originalet 2006-10-02.
Ruskey, Frank; Savage, Carla; Wang, Terry Min Yih (1992). "Genererar halsband". Journal of Algorithms . 13 (3): 414–430. doi : 10.1016/0196-6774(92)90047-G .