شمارش با لم برنساید و روش پولیا (گردنبندها)

تعداد گردنبندهای n مهره‌ای با k رنگ را می‌شمارد، وقتی چرخاندن (و برگرداندن) گردنبند آن را عوض نکند: میانگین تعداد رنگ‌آمیزی‌هایی که هر تقارن ثابت نگه می‌دارد، و هر تقارن با c دور، k^c رنگ‌آمیزی را ثابت نگه می‌دارد.

چند گردنبند n مهره‌ای با k رنگ وجود دارد؟ k^n رنگ‌آمیزی هست، ولی رنگ‌آمیزی‌هایی که با چرخاندن (یا برگرداندن) گردنبند به هم تبدیل می‌شوند یک گردنبندند. پس باید مدارهای گروه تقارن‌ها را بشماریم.

ادامه‌ی توضیح ↓

زمان: O(n log n)
حافظه: O(n)
گریمالدی، فصل ۱۶

ورودی:

n=6 · k=2 · flips=0خروجی PDF

گردنبند ۶ مهره‌ای با ۲ رنگ، فقط با چرخش: (۶۴ + ۲ + ۴ + ۸ + ۴ + ۲) ÷ ۶ = ۱۴.

from math import gcd
def necklaces(n, k, flips):
# Count the colourings of n beads in a ring with k colours, where turning (and, if flips = 1, flipping) the ring
# does not make a new necklace. Burnside: the count is the average number of colourings each symmetry fixes.
rows = [] # for the picture: symmetry, its number of cycles, the colourings it fixes
total = 0
for r in range(n):
c = gcd(r, n) # turning by r splits the beads into gcd(r, n) cycles
fixed = k ** c
total = total + fixed
rows.append(["turn " + str(r), c, fixed])
group = n
if flips == 1:
for i in range(n):
if n % 2 == 1:
c = (n + 1) // 2 # an axis through one bead and the gap opposite it
elif i % 2 == 0:
c = n // 2 + 1 # an axis through two opposite beads
else:
c = n // 2 # an axis through two opposite gaps
fixed = k ** c
total = total + fixed
rows.append(["flip " + str(i), c, fixed])
group = 2 * n
count = total // group
return count

ناوردا: یک رنگ‌آمیزی تحت یک تقارن ثابت است اگر و تنها اگر روی هر دور آن تقارن یک‌رنگ باشد.

شروع اجرا

total—

group—

count—

جدول هنوز خالی است.

متغیرهای محلی

flips0

نارنجی = در همین گام عوض شد

Call stack

necklaces()خط 4

گام ۱ از ۳۸

توضیح

مسئله

لم برنساید

تعداد مدارها برابر است با میانگین تعداد رنگ‌آمیزی‌هایی که هر عضو گروه ثابت نگه می‌دارد:

تعداد گردنبندها = (1/|G|) Σ_g fix(g)

روش پولیا

یک تقارن مهره‌ها را به دورهایی تقسیم می‌کند؛ رنگ‌آمیزی ثابت است اگر و تنها اگر روی هر دور یک‌رنگ باشد. پس تقارنی با c دور، k^c رنگ‌آمیزی را ثابت نگه می‌دارد.

چرخش به اندازه‌ی r: gcd(r, n) دور.
بازتاب: اگر n فرد باشد (n + 1)/2 دور؛ اگر زوج، n/2 + 1 (محور از دو مهره) یا n/2 (محور از دو فاصله).

ورودی

n تعداد مهره‌ها، k تعداد رنگ‌ها، و flips = 1 یعنی برگرداندن هم مجاز است (دستبند).