Marjonlarni (kombinatorika) - Necklace (combinatorics)

Uzunlikdagi bilakuzuklarning mumkin bo'lgan naqshlari n
ga mos keladi k-chi butun sonli qism
(bo'limlarni o'rnatish qadar aylanish va aks ettirish)
3 bilakuzuklar 3 ta qizil va 3 ta yashil munchoqlar bilan. O'rtada bo'lgan chiral, shuning uchun 4 bor marjonlarni.
Uchburchakdagi (6,9) katakchani solishtiring.
11 bilakuzuklar 2 qizil, 2 sariq va 2 yashil munchoq bilan. Eng chap va to'rtta o'ng tomon chiraldir, shuning uchun 16 ta marjonlarni.
Uchburchakdagi (6,7) katakchani solishtiring.
16 Tantrix plitkalarga, 16 ga to'g'ri keladi marjonlarni 2 ta qizil, 2 ta sariq va 2 ta yashil munchoqlar bilan.

Yilda kombinatorika, a k-ary marjon uzunlik n bu ekvivalentlik sinfi (ekvivalentlik munosabati mavjud bo'lgan guruhlash) ning n- belgi torlar ustidan alifbo hajmi k, barchasini olib aylanishlar ekvivalent sifatida. Bu bilan tuzilmani ifodalaydi n dumaloq bog'langan boncuklar k mavjud ranglar.

A k-ary bilaguzuk, shuningdek, a deb nomlanadi tovar aylanmasi (yoki ozod) marjon, bu bo'yinbog ', shuning uchun iplar aks ettirishda teng bo'lishi mumkin. Ya'ni, ikkita satr berilgan, agar ularning har biri boshqasining teskari tomoni bo'lsa, ular bir xil ekvivalentlik sinfiga tegishli. Shu sababli marjonni a deb ham atash mumkin sobit marjon uni oborot marjonidan farqlash uchun.

Rasmiy ravishda, marjonlarni an shaklida ifodalash mumkin orbitada ning tsiklik guruh aktyorlik kuni n- belgi qatorlari va bilaguzuk dihedral guruh. Ushbu orbitalarni va shuning uchun marjonlarni va bilakuzuklarni sanash mumkin Polya sanab chiqish teoremasi.

Ekvivalentlik darslari

Marjonlarni soni

Lar bor

boshqacha kuzunlikdagi bo'yinbog'lar n, qayerda bu Eylerning totient funktsiyasi.[1] Bu to'g'ridan-to'g'ri quyidagidan kelib chiqadi Polya sanab chiqish teoremasi tsiklik guruh harakatiga nisbatan qo'llaniladi barcha funktsiyalar to'plami bo'yicha harakat qilish .Bu erda ham bor

uzunlikdagi turli xil marjonlarni n aniq bilan k turli xil rangli boncuklar, qaerda ular Ikkinchi turdagi stirling raqami.

(ketma-ketlik A054631 ichida OEIS ) va (ketma-ketlik A087854 ichida OEIS ) orqali bog'langan Binomial koeffitsientlar:

va

Bilakuzuklar soni

Hammasi mavjud

boshqacha k- uzunlikdagi bilakuzuklar n, qayerda Nk(n) ning soni kuzunlikdagi bo'yinbog'larn. Bu Polaning harakatiga nisbatan qo'llanilgan usulidan kelib chiqadi dihedral guruh .

Alohida boncuklar holati

Berilgan to'plam uchun n munchoqlar, barchasi aniq, aylantirilgan marjonlarni bir xil deb hisoblagan holda, ushbu munchoqlardan yasalgan alohida marjonlarni soni n!/n = (n - 1) !. Buning sababi shundaki, boncuklar chiziqli ravishda buyurtma qilinishi mumkin n! yo'llari va n bunday buyurtmaning dumaloq siljishlari barchasi bir xil marjonlarni beradi. Xuddi shu tarzda, aylantirilgan va aks ettirilgan bilaguzuklarni bir xil deb hisoblash, aniq bilakuzuklar soni n!/2n, uchun n ≥ 3.

Agar boncuklar bir-biridan farq qilmasa, takrorlangan ranglarga ega bo'lsa, unda kamroq marjonlarni (va bilakuzuklar) mavjud. Yuqoridagi marjonlarni hisoblash polinomlari barcha mumkin bo'lgan miqdordagi marjonlarni beradi multisets boncuklardan. Polya naqshli inventarizatsiya polinomiyasi munchoqning har bir rangi uchun o'zgaruvchidan foydalanib, hisoblash polinomini aniqlaydi, shunda har bir monomial koeffitsient berilgan ko'p qirrali boncukta marjonlarni sonini hisoblaydi.

Aperiodik marjonlarni

An aperiodik marjon uzunlik n aylanishdir ekvivalentlik sinfi o'lchamga ega n, ya'ni marjonlarni bunday sinfdan ikki xil aylanishi teng bo'lmaydi.

Ga binoan Moroning marjonlarni hisoblash funktsiyasi, lar bor

boshqacha k- uzunlikdagi aperiodik marjonlarni n, qayerda m bo'ladi Mobius funktsiyasi. Marjonlarni hisoblashning ikkita funktsiyasi quyidagilarga bog'liq: bu erda yig'indisi barcha bo'linuvchilar ustidan n, bu bilan teng Möbius inversiyasi ga

Har bir aperiodik marjonda bitta bittadan iborat Lyndon so'zi shuning uchun Lyndon so'zlari shakllanadi vakillar aperiodik marjonlarni.

Shuningdek qarang

Adabiyotlar

  1. ^ Vayshteyn, Erik V. "Marjon". MathWorld.

Tashqi havolalar