Symmetry দিয়ে গণনা — Burnside-এর lemma আর Pólya

১ · ঘোরালে যা একই — কেন সাধারণ গণনা বেশি গোনে

এই মডিউলে এ পর্যন্ত যা গুনেছেন, তার প্রতিটি বস্তু ছিল আলাদা: একটি bit string, একটি tiling, একটি partition. কিন্তু অনেক প্রশ্নে দুটি বস্তু “আসলে একই”, কারণ একটিকে ঘুরিয়ে বা উল্টে অন্যটি পাওয়া যায়। এই পর্বের প্রশ্ন: এমন অবস্থায় আলাদা বস্তু কয়টি?

গণিতে এই স্ট্যান্ডের নাম necklace (মালা): বৃত্তে সাজানো n-টি পুঁতি, প্রতিটি k-টি রঙের একটিতে রং করা, আর ঘোরালে মিলে যায় এমন দুটি মালা একই। পুঁতিগুলোকে 1, 2, 3, 4 নম্বর দিলে একটি রং-করা হলো দৈর্ঘ্য ৪-এর একটি string, যেমন 0011 (0 = লাল, 1 = নীল)। মোট string 2⁴ = 16. এক ধাপ ঘোরানো মানে string-এর প্রথম অক্ষর শেষে পাঠানো: 0011 → 0110 → 1100 → 1001 → 0011.

মোট ৬টি শ্রেণি, আর তাদের আকার যোগ করলে 1 + 4 + 4 + 2 + 4 + 1 = 16. এখানেই সমস্যার মূল। পর্ব ৩৩ “Permutation আর combination”-এ n জন আলাদা মানুষকে গোল টেবিলে বসানোর উপায় (n − 1)! বের হয়েছিল ভাগের নিয়মে: প্রতিটি গোল বসা ঠিক n-টি সারি থেকে আসে, তাই n!/n. সেখানে সবাই আলাদা, তাই কোনো rotation একটি বসাকে নিজের ওপর ফেরত আনে না, আর প্রতিটি শ্রেণির আকার ঠিক n. রঙের প্রশ্নে তা সত্য নয়: 0000 ঘোরালে বদলায়ই না (শ্রেণির আকার 1), আর 0101 দুই ধাপেই ফিরে আসে (আকার 2), তাই তার শ্রেণি ছোট। তাই 16/4 = 4 একটি ভুল উত্তর, আর সঠিক উত্তর 6.

হাতে তালিকা করা ৪ পুঁতিতে চলে, ১০ পুঁতিতে ১০২৪টি string, আর ৩০ পুঁতিতে প্রায় ১০৭ কোটি। দরকার এমন একটি সূত্র, যা শ্রেণির অসমান আকারকে নিজেই সামলায়। সেই সূত্রই Burnside-এর lemma, আর তার জন্য আগে “symmetry” কথাটিকে নির্ভুল করতে হবে।

২ · Symmetry-র group — rotation, reflection, cyclic আর dihedral

একটি বর্গক্ষেত্রের কোণ চারটিকে ঘড়ির কাঁটার দিকে 1, 2, 3, 4 নাম দিন। বর্গটিকে তুলে আবার একই জায়গায় বসানোর উপায় কয়টি, যাতে আকৃতিটি নিজের ওপর পড়ে? ঘোরানো যায় 0°, 90°, 180°, 270°; আর উল্টানো যায় চারটি অক্ষ বরাবর: দুটি কর্ণ আর দুটি মধ্যরেখা। মোট ৮টি symmetry. প্রতিটি symmetry কোণগুলোর একটি permutation (পর্ব ১৬-এর bijection), যেমন 90° ঘোরানো 1 → 2 → 3 → 4 → 1.

এই ৮টি symmetry-র একটি গুরুত্বপূর্ণ ধর্ম আছে: দুটি পরপর করলে আবার একটি symmetry পাওয়া যায় (90° তারপর 90° = 180°), “কিছু না করা” (0°) একটি symmetry, আর প্রতিটির একটি উল্টো আছে (90°-এর উল্টো 270°, প্রতিটি উল্টানোর উল্টো সে নিজেই)। এই তিনটি ধর্ম (আর composition-এর সংযোজন নিয়ম) মানেই একটি group. Group-এর সাধারণ তত্ত্ব, subgroup আর Lagrange-এর উপপাদ্য পর্ব ৭০ “Group — symmetry, cyclic group আর Lagrange-এর উপপাদ্য”-এ আসবে; এই পর্বে শুধু সংজ্ঞা আর দুটি পরিবার লাগবে।

একটি permutation-কে লেখার সবচেয়ে কাজের উপায় তার cycle decomposition: কোন উপাদান কোথায় যায় তা অনুসরণ করে বৃত্তগুলো লেখা। 90° ঘোরানো (1 2 3 4): 1 যায় 2-এ, 2 যায় 3-এ, …, 4 ফেরে 1-এ, একটি দৈর্ঘ্য-৪ cycle. 180° ঘোরানো (1 3)(2 4): দুটি দৈর্ঘ্য-২ cycle. কর্ণ 1–3 বরাবর উল্টানো (1)(3)(2 4): 1 আর 3 স্থির (দৈর্ঘ্য-১ cycle), 2 আর 4 অদলবদল। কেন cycle এত গুরুত্বপূর্ণ, তা §৪-এ স্পষ্ট হবে: একটি symmetry-তে অপরিবর্তিত রং-করায় প্রতিটি cycle-এর সব পুঁতি একই রঙের।

1e: কিছু না করা2r, r³: 90°, 270°3r²: 180°4কর্ণ বরাবর উল্টানো ×25মধ্যরেখা বরাবর ×26সব মিলিয়ে cycle index7k = 2: (16+16+12+4)/8

৩ · Group action, orbit আর stabilizer

Symmetry-গুলো শুধু কোণ নয়, রং-করাকেও সরায়: 90° ঘোরালে 0011 হয় 1001. সাধারণভাবে বলতে আমরা একটি group G আর একটি সেট X (যেমন সব রং-করা) নিই, আর বলি G-এর প্রতিটি উপাদান X-এর উপাদানগুলোকে সরায়।

উদাহরণ (C₄, ৪ পুঁতি): Orb(0011) = {0011, 0110, 1100, 1001}, আর তার stabilizer শুধু {e}. Orb(0101) = {0101, 1010}, stabilizer {e, r²}, কারণ 180° ঘোরালে 0101 বদলায় না। Fix(r²) = {0000, 0101, 1010, 1111}: যে string-এ পুঁতি 1 = পুঁতি 3 আর পুঁতি 2 = পুঁতি 4. খেয়াল করুন, “ঘোরালে মেলে এমন দুটি মালা একই” কথাটির নির্ভুল রূপ: একই orbit-এ থাকা দুটি রং-করা একই মালা। তাই আলাদা মালার সংখ্যা = orbit-এর সংখ্যা।

1. Reflexive: e·x = x, তাই x ~ x. — action-এর শর্ত (ক)
2. Symmetric: g·x = y হলে g⁻¹·y = g⁻¹·(g·x) = (g⁻¹g)·x = e·x = x, তাই y ~ x. — শর্ত (খ) আর উল্টোর অস্তিত্ব
3. Transitive: g·x = y আর h·y = z হলে (hg)·x = h·(g·x) = z, তাই x ~ z. ∎ — শর্ত (খ)

Equivalence relation আর partition-এর সাধারণ সম্পর্ক পর্ব ৫৫ “Equivalence relation আর partition”-এ বিস্তারিত আসবে; এখানে শুধু এটুকু লাগে যে প্রতিটি রং-করা ঠিক একটি orbit-এ পড়ে।

1. প্রতিটি g ∈ G-কে তার ফল g·x অনুযায়ী দলে ভাগ করুন। ফলগুলো ঠিক Orb(x)-এর উপাদান, তাই দল আছে |Orb(x)|-টি, আর দলগুলো মিলে পুরো G. — orbit-এর সংজ্ঞা
2. y ∈ Orb(x) নিন, আর এমন একটি h বাছুন যাতে h·x = y. দাবি: y-এর দল ঠিক {hs : s ∈ G_x}. — দলের বর্ণনা
3. s ∈ G_x হলে (hs)·x = h·(s·x) = h·x = y, তাই hs দলটিতে আছে। উল্টো দিকে g·x = y হলে s = h⁻¹g-এর জন্য s·x = h⁻¹·y = x, তাই s ∈ G_x আর g = hs. — শর্ত (খ)
4. s ↦ hs একটি bijection, কারণ hs = hs′ হলে বাঁ দিকে h⁻¹ গুণ করে s = s′. তাই প্রতিটি দলের আকার |G_x|. — bijection, পর্ব ১৬
5. |Orb(x)|-টি দল, প্রতিটির আকার |G_x|, তাই |G| = |Orb(x)| · |G_x|. ∎ — গুণের নিয়ম

যাচাই: C₄-এ 0101-এর orbit আকার 2, stabilizer আকার 2, গুণফল 4 = |C₄|. 0000-এর orbit আকার 1, stabilizer পুরো group, গুণফল 4. এ থেকেই একটি কাজের ফল: orbit-এর আকার সবসময় |G|-এর একটি উৎপাদক। কিউবের ২৪টি rotation-এ একটি তলের orbit হলো ৬টি তল, তাই একটি তলের stabilizer-এ 24/6 = 4টি rotation: ওই তলের কেন্দ্র দিয়ে যাওয়া অক্ষে 0°, 90°, 180°, 270°.

৪ · Burnside-এর lemma — double counting-এ এক লাইনের প্রমাণ

এখন মূল উপপাদ্য। §১-এর সমস্যা ছিল orbit-গুলোর আকার অসমান। Orbit–stabilizer বলে, ছোট orbit মানে বড় stabilizer, অর্থাৎ ছোট শ্রেণির বস্তু বেশি symmetry-তে স্থির থাকে। এই দুটি প্রভাব ঠিক একে অন্যকে কাটে।

1. সেট P = {(g, x) ∈ G × X : g·x = x} দুইভাবে গুনি। — double counting, পর্ব ৩৭
2. প্রথমে g ধরে: প্রতিটি g-এর সঙ্গে জোড়া x-গুলো ঠিক Fix(g), তাই |P| = ∑_g |Fix(g)|. — Fix-এর সংজ্ঞা
3. এবার x ধরে: প্রতিটি x-এর সঙ্গে জোড়া g-গুলো ঠিক G_x, তাই |P| = ∑_x |G_x| = ∑_x |G|/|Orb(x)|. — উপপাদ্য ৩.৩
4. যোগফলটি orbit অনুযায়ী ভাগ করুন। একটি orbit O-এর প্রতিটি x-এ |Orb(x)| = |O|, আর O-তে |O|-টি x, তাই O-এর অবদান |O| · |G|/|O| = |G|. — উপপাদ্য ৩.২
5. প্রতিটি orbit ঠিক |G| যোগ করে, তাই |P| = |G| · |X/G|. ধাপ ২-এর সঙ্গে মিলিয়ে |G| দিয়ে ভাগ করলে উপপাদ্য। ∎ — দুই গণনা সমান

ধাপ ৪-ই আসল কৌশল: একটি orbit-এর বস্তু যত কম, প্রত্যেকের stabilizer তত বড়, আর গুণফল সবসময় |G|. তাই সরল ভাগে যে অসমতা ভুল ঘটাত, এখানে তা নিজেই শোধ হয়ে যায়। এবার §১-এর ৪ পুঁতির মালায় খাটাই।

1G = C₄ = {e, r, r², r³}2|Fix(e)| = 2⁴ = 163|Fix(r)| = 24|Fix(r²)| = 2² = 45|Fix(r³)| = 26(16+2+4+2)/4 = 6

Stepper-এর ধাপ ৩–৪-এ যে নিয়ম কাজ করেছে, সেটি সাধারণভাবে সত্য, আর এটিই এই পর্বের সব হিসাবের চাবি:

1. g একটি রং-করাকে অপরিবর্তিত রাখে যদি এবং কেবল যদি প্রতিটি পুঁতি i-এর রং = g(i)-এর রং। — g·x = x-এর অর্থ
2. একটি cycle (i, g(i), g²(i), …) বরাবর এই সমতা পরপর খাটালে cycle-এর সব পুঁতি একই রঙের; উল্টো দিকে প্রতিটি cycle এক রঙের হলে শর্তটি মেটে। — cycle বরাবর induction
3. Cycle-গুলো পুঁতিগুলোকে ভাগ করে, আর প্রতিটির রং স্বাধীনভাবে k উপায়ে বাছা যায়, তাই k^c(g). ∎ — গুণের নিয়ম

৫ · Necklace-এর সূত্র — Euler-এর φ কেন আসে

এখন যেকোনো n আর k-এর জন্য necklace গুনি। Lemma ৪.২ অনুযায়ী শুধু জানতে হবে প্রতিটি rotation-এর কয়টি cycle.

1. পুঁতিগুলোকে 0, 1, …, n − 1 ধরুন; r^s পুঁতি i-কে পাঠায় i + s (mod n)-এ। i-এর cycle হলো i, i + s, i + 2s, … (mod n). — পর্ব ২২-এর modular arithmetic
2. cycle-এর দৈর্ঘ্য সবচেয়ে ছোট m ≥ 1, যাতে ms ≡ 0 (mod n), অর্থাৎ n ∣ ms. g = gcd(s, n) হলে এটি (n/g) ∣ m(s/g)-এর সমান, আর gcd(n/g, s/g) = 1 বলে (n/g) ∣ m. তাই m = n/g. — Euclid-এর lemma
3. প্রতিটি cycle-এর দৈর্ঘ্য n/g, মোট পুঁতি n, তাই cycle-এর সংখ্যা n/(n/g) = g. ∎ — ভাগ

1. Burnside আর lemma ৪.২, ৫.১ মিলিয়ে N(n, k) = (1/n) ∑_s=0ⁿ⁻¹ k^{gcd(s, n)}. — উপপাদ্য ৪.১
2. s-গুলোকে g = gcd(s, n) অনুযায়ী দলে ভাগ করুন। gcd(s, n) = g মানে s = gt, যেখানে 0 ≤ t < n/g আর gcd(t, n/g) = 1; এমন t ঠিক φ(n/g)-টি। — φ-এর সংজ্ঞা
3. তাই যোগফল ∑_g∣n φ(n/g) k^g. d = n/g বসালে d-ও n-এর সব উৎপাদকের ওপর চলে, আর যোগফল ∑_d∣n φ(d) k^n/d. ∎ — সূচক বদল

উদাহরণ। n = 6, k = 2: উৎপাদক 1, 2, 3, 6; φ = 1, 1, 2, 2. N = (2⁶ + 2³ + 2 · 2² + 2 · 2¹)/6 = (64 + 8 + 8 + 4)/6 = 84/6 = 14. n যদি মৌলিক p হয়, উৎপাদক শুধু 1 আর p: N(p, k) = (k^p + (p − 1)k)/p. যেমন ৫ পুঁতি, ৩ রঙে (243 + 12)/5 = 51. এই সূত্র পূর্ণসংখ্যা দিতে বাধ্য, আর তা থেকে একটি পুরোনো বন্ধুর নতুন প্রমাণ বেরোয় (অনুশীলন ১)।

§৬-এর শেষে একটি Python ব্লক necklace আর bracelet দুটিরই সূত্র দিয়ে গোনে, আর প্রতিটি string-এর orbit চিহ্নিত করে brute force-এ গুনে মেলায়।

৬ · Bracelet — উল্টানোও যখন চলে

মালাটি যদি হাতে নিয়ে উল্টানোও যায় (যেমন একটি চুড়ি বা bracelet), তখন group হয় D_n: n-টি rotation আর n-টি reflection. Rotation-এর অবদান উপপাদ্য ৫.২-এর যোগফলই, নতুন শুধু reflection-এর cycle গোনা।

• n বিজোড়: প্রতিটি reflection-এর অক্ষ একটি পুঁতি আর তার বিপরীত দুই পুঁতির মাঝখান দিয়ে যায়। একটি পুঁতি স্থির, বাকি n − 1টি জোড়ায় অদলবদল: (n + 1)/2টি cycle. n-টি reflection মিলে n · k^(n+1)/2.
• n জোড়: দুই রকম reflection. n/2টির অক্ষ দুটি বিপরীত পুঁতির মধ্য দিয়ে: ২টি স্থির, বাকি (n − 2)/2 জোড়া, মোট n/2 + 1টি cycle. বাকি n/2টির অক্ষ দুই বাহুর মধ্যবিন্দু দিয়ে: কোনো পুঁতি স্থির নয়, n/2টি জোড়া। মিলে (n/2)(k^n/2+1 + k^n/2).

B(n, k) = [n · N(n, k) + (reflection-এর অবদান)] / (2n)

বর্গে (n = 4) এই দুই রকম reflection-ই §২-এর stepper-এ দেখেছেন: কর্ণ (দুই কোণ স্থির) আর মধ্যরেখা (কোনো কোণ স্থির নয়)। n = 6, k = 2: rotation-এর যোগফল 84, reflection-এর 3 · 2⁴ + 3 · 2³ = 48 + 24 = 72, তাই B = 156/12 = 13. Necklace ১৪টি থেকে একটি কমল: 001011 আর তার আয়না-রূপ 001101 rotation-এ আলাদা, কিন্তু উল্টালে একই।

নিচের ব্লক দুটি সূত্রই brute force-এর সঙ্গে মেলায়। প্রথমবার চালালে ব্রাউজারে Python (Pyodide) নামতে কয়েক সেকেন্ড লাগে; পরের ব্লকগুলো দ্রুত চলে।

from itertools import product
from math import gcd
def phi(n):
    return sum(1 for i in range(1, n + 1) if gcd(i, n) == 1)
def necklace(n, k):                    # Burnside over the n rotations
    return sum(phi(d) * k ** (n // d)
               for d in range(1, n + 1) if n % d == 0) // n

def bracelet(n, k):                    # Burnside over the 2n symmetries
    if n % 2:
        refl = n * k ** ((n + 1) // 2)
    else:
        refl = n // 2 * (k ** (n // 2 + 1) + k ** (n // 2))
    return (n * necklace(n, k) + refl) // (2 * n)

def brute(n, k, flip):                 # walk every string, mark its orbit
    seen, orbits = set(), 0
    for s in product(range(k), repeat=n):
        if s not in seen:
            orbits += 1
            for r in range(n):
                t = s[r:] + s[:r]
                seen.add(t)
                if flip:
                    seen.add(t[::-1])
    return orbits

for k, top in ((2, 10), (3, 7)):
    print("k =", k)
    for n in range(1, top + 1):
        a, b = necklace(n, k), brute(n, k, False)
        c, d = bracelet(n, k), brute(n, k, True)
        print(f"  n={n:2}  necklace {a:4} brute {b:4}"
              f"   bracelet {c:4} brute {d:4}  ok={a == b and c == d}")

k = 2
  n= 1  necklace    2 brute    2   bracelet    2 brute    2  ok=True
  n= 2  necklace    3 brute    3   bracelet    3 brute    3  ok=True
  n= 3  necklace    4 brute    4   bracelet    4 brute    4  ok=True
  n= 4  necklace    6 brute    6   bracelet    6 brute    6  ok=True
  n= 5  necklace    8 brute    8   bracelet    8 brute    8  ok=True
  n= 6  necklace   14 brute   14   bracelet   13 brute   13  ok=True
  n= 7  necklace   20 brute   20   bracelet   18 brute   18  ok=True
  n= 8  necklace   36 brute   36   bracelet   30 brute   30  ok=True
  n= 9  necklace   60 brute   60   bracelet   46 brute   46  ok=True
  n=10  necklace  108 brute  108   bracelet   78 brute   78  ok=True
k = 3
  n= 1  necklace    3 brute    3   bracelet    3 brute    3  ok=True
  n= 2  necklace    6 brute    6   bracelet    6 brute    6  ok=True
  n= 3  necklace   11 brute   11   bracelet   10 brute   10  ok=True
  n= 4  necklace   24 brute   24   bracelet   21 brute   21  ok=True
  n= 5  necklace   51 brute   51   bracelet   39 brute   39  ok=True
  n= 6  necklace  130 brute  130   bracelet   92 brute   92  ok=True
  n= 7  necklace  315 brute  315   bracelet  198 brute  198  ok=True

৭ · কিউবের তল রং করা — ২৪টি rotation

বাজারঘর উপহারের বাক্স বানায় কিউব আকারে, প্রতিটি তল লাল বা নীল কাগজে মোড়া। বাক্সটি হাতে ঘোরানো যায় (কিন্তু আয়নায় উল্টানো যায় না), তাই ঘোরালে মেলে এমন দুটি বাক্স একই। আলাদা বাক্স কয়টি? সেট X = ছয় তলের সব রং-করা (k⁶টি), আর G = কিউবের rotation group.

প্রথমে |G|: উপরের তলটি ৬টি তলের যেকোনোটিতে যেতে পারে, আর তারপর ওই অক্ষে ৪ রকম ঘোরানো যায়, তাই 6 · 4 = 24. (Orbit–stabilizer-এর ভাষায়: একটি তলের orbit ৬, stabilizer ৪।) ২৪টি rotation-কে অক্ষ অনুযায়ী সাজালে:

সংখ্যাগুলো যোগ করলে 1 + 6 + 3 + 8 + 6 = 24, তাই কোনো rotation বাদ পড়েনি। Lemma ৪.২ অনুযায়ী প্রতিটি পদে x_i-এর জায়গায় k বসালেই |Fix|, আর Burnside দেয়

কিউবের তল k রঙে = (k⁶ + 3k⁴ + 12k³ + 8k²) / 24

এখানে 12k³ এসেছে দুই জায়গা থেকে: quarter turn-এর ৬টি (x₁²x₄, তিনটি cycle) আর বাহু-অক্ষের ৬টি (x₂³, তিনটি cycle) থেকে।

1e: 2⁶ = 642তল-অক্ষ 90°/270°: 6 × 2³3তল-অক্ষ 180°: 3 × 2⁴4কোণ-অক্ষ: 8 × 2²5বাহু-অক্ষ: 6 × 2³6240 / 24 = 107লাল তল অনুযায়ী ভাগ

টেবিলটি হাতে বানানো, তাই ভুল হতে পারে। নিচের ব্লক টেবিলটিকে নিজেই আবিষ্কার করে: দুটি quarter turn থেকে শুরু করে তাদের সব composition নিয়ে group-টি তৈরি করে (যতক্ষণ নতুন rotation আসে), প্রতিটির cycle গোনে, তারপর Burnside আর brute force মেলায়।

from itertools import product
from collections import Counter
# faces: 0 Up, 1 Down, 2 Front, 3 Back, 4 Left, 5 Right
a = (0, 1, 5, 4, 2, 3)        # quarter turn about the Up-Down axis
b = (5, 4, 2, 3, 0, 1)        # quarter turn about the Front-Back axis
def compose(p, q):
    return tuple(p[q[i]] for i in range(6))
def cycles(p):                 # cycle lengths of a permutation
    seen, out = set(), []
    for i in range(6):
        n, j = 0, i
        while j not in seen:
            seen.add(j); j = p[j]; n += 1
        if n:
            out.append(n)
    return tuple(sorted(out))
G, todo = {tuple(range(6))}, [tuple(range(6))]
while todo:                    # close {a, b} under composition
    g = todo.pop()
    for h in (a, b):
        x = compose(h, g)
        if x not in G:
            G.add(x); todo.append(x)
print("rotations found:", len(G))
for t, m in sorted(Counter(cycles(g) for g in G).items()):
    print("  cycle type", t, "x", m)

for k in (2, 3):
    burnside = sum(k ** len(cycles(g)) for g in G) // len(G)
    seen, orbits = set(), 0
    for s in product(range(k), repeat=6):
        if s not in seen:
            orbits += 1
            seen.update(tuple(s[g[i]] for i in range(6)) for g in G)
    print(f"k={k}: Burnside {burnside}, brute force {orbits}")

rotations found: 24
  cycle type (1, 1, 1, 1, 1, 1) x 1
  cycle type (1, 1, 2, 2) x 3
  cycle type (1, 1, 4) x 6
  cycle type (2, 2, 2) x 6
  cycle type (3, 3) x 8
k=2: Burnside 10, brute force 10
k=3: Burnside 57, brute force 57

৮ · Pólya-র enumeration উপপাদ্য — রঙের হিসাবসহ গোনা

Burnside মোট সংখ্যা দেয়। কিন্তু বাজারঘরের গুদামে যদি লাল কাগজ মাত্র ৩টি তলের মতো থাকে? তখন প্রশ্ন: ঠিক ৩টি লাল আর ৩টি নীল তলের আলাদা বাক্স কয়টি? Stepper-এর শেষ ধাপে উত্তর ছিল ২, কিন্তু তা তালিকা করে। Pólya-র উপপাদ্য এমন সব প্রশ্নের উত্তর একসঙ্গে একটি generating function-এ দেয় (পর্ব ৪৮ “Generating function — গণনাকে বীজগণিতে রূপান্তর”)।

উদাহরণ: Z(C₄) = (x₁⁴ + x₂² + 2x₄)/4, Z(D₄) §২-এর stepper-এ, আর কিউবের তলে Z = (x₁⁶ + 3x₁²x₂² + 6x₁²x₄ + 6x₂³ + 8x₃²)/24. সব x_i = k বসালে lemma ৪.২ অনুযায়ী Burnside-এর উত্তর। এখন আরও সূক্ষ্ম কিছু বসাব।

1. রঙের সংখ্যা (α, β, …) নির্দিষ্ট এমন রং-করার সেট X_α,β,… নিন। কোনো symmetry রং বদলায় না, শুধু অবস্থান সরায়, তাই G এই সেটের ওপরই কাজ করে, আর Burnside খাটে: উত্তর = (1/|G|)∑_g |Fix(g) ∩ X_α,β,…|. — উপপাদ্য ৪.১
2. Lemma ৪.২ অনুযায়ী g-স্থির রং-করা মানে প্রতিটি cycle এক রঙের। দৈর্ঘ্য i-এর একটি cycle পুরো r হলে তা i-টি r দেয়, যা rⁱ দিয়ে চিহ্নিত; তাই একটি cycle-এর সব পছন্দের generating function rⁱ + bⁱ + ⋯. — generating function-এ ঘাত = সংখ্যা
3. Cycle-গুলোর রং স্বাধীন, তাই g-স্থির সব রং-করার generating function ∏_i(rⁱ + bⁱ + ⋯)^c_i(g), আর তার r^αb^β⋯-এর সহগ = |Fix(g) ∩ X_α,β,…|. — পর্ব ৪৮-এর গুণফলের নিয়ম
4. সব g-এর ওপর যোগ করে |G| দিয়ে ভাগ করলে ঠিক x_i → rⁱ + bⁱ + ⋯ বসানো Z_G, আর ধাপ ১ অনুযায়ী তার প্রতিটি সহগ উত্তর। ∎ — যোগফল অদলবদল

উদাহরণ ১ (৪ পুঁতি, ২ রং)। Z(C₄)-এ বসাই: (r + b)⁴ = r⁴ + 4r³b + 6r²b² + 4rb³ + b⁴; (r² + b²)² = r⁴ + 2r²b² + b⁴; 2(r⁴ + b⁴). যোগ করে 4 দিয়ে ভাগ:

r⁴ + r³b + 2r²b² + rb³ + b⁴

দুই লাল আর দুই নীলের সহগ 2: §১-এর “পাশাপাশি” আর “মুখোমুখি”। সহগের যোগফল 6, মোট মালার সংখ্যা।

উদাহরণ ২ (কিউব, ৩ লাল ৩ নীল)। r³b³-এর সহগ চাই। x₁⁶ → (r + b)⁶ থেকে C(6, 3) = 20. 3x₁²x₂² → (r + b)²(r² + b²)²-এ r³b³ আসে শুধু (rb-এর সহগ 2) × (r²b²-এর সহগ 2) = 4 থেকে, তিনগুণে 12. 6x₁²x₄ আর 6x₂³ থেকে 0 (৩টি r-কে ১ বা ২, আর ৪ বা ২-এর অংশে ভাঙা যায় না: x₁²x₄-এ r-এর ঘাত 0, 1, 2, 4, 5, 6 হতে পারে, 3 নয়; x₂³-এ শুধু জোড়)। 8x₃² → (r³ + b³)²-এ r³b³-এর সহগ 2, আটগুণে 16. মোট (20 + 12 + 16)/24 = 2, stepper-এর তালিকার সঙ্গে মেলে।

উদাহরণ ৩ (৬ পুঁতি, ৩ রং)। বাজারঘরের ৬ তাকের ঘূর্ণায়মান স্ট্যান্ডে ২টি লাল, ২টি নীল আর ২টি সবুজ পণ্য। Rotation r^s-এর gcd(s, 6)-টি cycle (lemma ৫.১), তাই Z(C₆) = (x₁⁶ + x₂³ + 2x₃² + 2x₆)/6. r²b²g²-এর সহগ: x₁⁶ থেকে multinomial 6!/(2!2!2!) = 90 (পর্ব ৩৫); x₂³ = (r² + b² + g²)³ থেকে তিন রং তিন গুণনীয়কে, 3! = 6; x₃² আর x₆ থেকে 0 (প্রতিটি রং ৩ বা ৬-এর গুণিতক বার আসত)। উত্তর (90 + 6)/6 = 16.

নিচের ব্লক polynomial-গুলোকে Python dictionary হিসেবে রাখে (key = ঘাতের tuple, value = সহগ), Z(C₆)-এ বসিয়ে পুরো pattern inventory বানায়, আর ৩⁶ = ৭২৯টি রং-করা থেকে orbit গুনে রঙের সংখ্যা অনুযায়ী মেলায়।

from itertools import product
from collections import Counter
from math import gcd
def pmul(p, q):                # polynomials as {(r, b, g) exponents: coeff}
    out = Counter()
    for e1, c1 in p.items():
        for e2, c2 in q.items():
            out[tuple(x + y for x, y in zip(e1, e2))] += c1 * c2
    return out
def power_sum(i, colours=3):   # x_i -> r^i + b^i + g^i
    return Counter({tuple(i if c == j else 0 for c in range(colours)): 1
                    for j in range(colours)})

n = 6                          # rotation r^s has gcd(s, n) cycles of length n/gcd
total = Counter()
for s in range(n):
    c = gcd(s, n)
    term = Counter({(0, 0, 0): 1})
    for _ in range(c):
        term = pmul(term, power_sum(n // c))
    total.update(term)
inventory = {e: v // n for e, v in total.items()}

seen, brute = set(), Counter()  # brute force: orbits sorted by colour counts
for s in product("rbg", repeat=n):
    if s not in seen:
        brute[(s.count("r"), s.count("b"), s.count("g"))] += 1
        seen.update(s[r:] + s[:r] for r in range(n))

print("Polya == brute force:", inventory == dict(brute))
for e in [(6, 0, 0), (5, 1, 0), (4, 2, 0), (3, 3, 0), (4, 1, 1),
          (3, 2, 1), (2, 2, 2)]:
    print("  r^%d b^%d g^%d :" % e, inventory[e])
print("all 6-bead necklaces:", sum(inventory.values()))

Polya == brute force: True
  r^6 b^0 g^0 : 1
  r^5 b^1 g^0 : 1
  r^4 b^2 g^0 : 3
  r^3 b^3 g^0 : 4
  r^4 b^1 g^1 : 5
  r^3 b^2 g^1 : 10
  r^2 b^2 g^2 : 16
all 6-bead necklaces: 130

৯ · প্রয়োগ, পরীক্ষার অঙ্ক আর একটি ভুল যুক্তি

প্রয়োগ ১: isomorphism পর্যন্ত graph গোনা

৪টি vertex-এ সম্ভাব্য edge C(4, 2) = 6টি, তাই লেবেলযুক্ত graph 2⁶ = 64টি। কিন্তু vertex-এর নাম বদলালে যে graph মেলে, তারা একই আকৃতি: এটিই graph isomorphism (পর্ব ৫৮ “গ্রাফের representation আর isomorphism”-এ বিস্তারিত)। এখানে X = ৬টি edge-এর রং-করা (আছে / নেই), আর G = ৪টি vertex-এর ২৪টি permutation, যা edge-গুলোকে সরায়। Edge-এর ওপর cycle গুনলে: identity x₁⁶; ৬টি transposition আর ৩টি double transposition, প্রতিটি x₁²x₂²; ৮টি 3-cycle, x₃²; ৬টি 4-cycle, x₂x₄. তাই আলাদা graph (64 + 9 · 16 + 8 · 4 + 6 · 4)/24 = 264/24 = 11.

from itertools import permutations, combinations, product
from collections import Counter

V = 4
E = list(combinations(range(V), 2))          # the 6 possible edges
perms = list(permutations(range(V)))         # the 24 relabellings

def relabel(graph, p):                       # graph = frozenset of edges
    return frozenset(tuple(sorted((p[u], p[v]))) for u, v in graph)

seen, classes = set(), Counter()
for bits in product((0, 1), repeat=len(E)):
    g = frozenset(e for e, x in zip(E, bits) if x)
    if g not in seen:
        classes[len(g)] += 1                 # one new class, by edge count
        seen.update(relabel(g, p) for p in perms)
print("brute force classes by edge count:", sorted(classes.items()))
print("total:", sum(classes.values()))

def n_cycles(p):                             # cycles of p acting on edges
    pe = {e: tuple(sorted((p[e[0]], p[e[1]]))) for e in E}
    seen, c = set(), 0
    for e in E:
        if e not in seen:
            c += 1
            while e not in seen:
                seen.add(e); e = pe[e]
    return c

fix = [2 ** n_cycles(p) for p in perms]
print("Burnside:", sum(fix), "/", len(perms), "=", sum(fix) // len(perms))

brute force classes by edge count: [(0, 1), (1, 1), (2, 2), (3, 3), (4, 2), (5, 1), (6, 1)]
total: 11
Burnside: 264 / 24 = 11

প্রয়োগ ২: রসায়নের isomer (সরলীকৃত)

Benzene বলয়ের ছয়টি কার্বনকে একটি সুষম ষড়ভুজ ধরলে, দুটি হাইড্রোজেনের জায়গায় দুটি ক্লোরিন বসানোর আলাদা উপায় D₆-এর orbit গুনে পাওয়া যায়: C(6, 2) = 15টি অবস্থান-জোড়া ৩টি orbit-এ পড়ে (পাশাপাশি, একটি ফাঁক, মুখোমুখি), যা রসায়নে পরিচিত dichlorobenzene-এর তিনটি গঠন-isomer (ortho, meta, para) বলে মেলে। এটি একটি সরলীকৃত মডেল: বাস্তব রসায়নে বন্ধনের ধরন আর ত্রিমাত্রিক গঠন (stereoisomer) হিসাবে আসে, যা শুধু ছবির symmetry গুনে ধরা যায় না। Pólya তাঁর ১৯৩৭ সালের প্রবন্ধে রাসায়নিক যৌগ গোনার উদাহরণ ব্যবহার করেছিলেন বলে জানা যায়।

অঙ্ক ১: Necklace আর bracelet

৫টি পুঁতি, ৩ রঙে কয়টি necklace আর কয়টি bracelet?

1. ৫ মৌলিক: N(5, 3) = (3⁵ + 4 · 3)/5 = (243 + 12)/5 = 51.
2. ৫ বিজোড়, প্রতিটি reflection-এ (5 + 1)/2 = 3টি cycle: ৫টি reflection মিলে 5 · 27 = 135.
3. B(5, 3) = (5 · 51 + 135)/10 = (255 + 135)/10 = 39. উত্তর: ৫১টি necklace, ৩৯টি bracelet (প্রথম Python ব্লকে মেলানো)।

অঙ্ক ২: বর্গের কোণ তিন রঙে

একটি বর্গাকার টেবিলের চার কোণে চারটি চেয়ার, প্রতিটি তিন রঙের একটিতে রং করা হবে; টেবিল ঘোরানো আর উল্টানো দুটিই চলে। আলাদা সাজ কয়টি? Z(D₄)-এ x_i = 3: (81 + 2 · 9 · 3 + 3 · 9 + 2 · 3)/8 = (81 + 54 + 27 + 6)/8 = 168/8 = 21. শুধু ঘোরানো চললে N(4, 3) = (81 + 9 + 2 · 3)/4 = 96/4 = 24.

অঙ্ক ৩: কিউব, তিন রং

তিন রঙে কিউবের তল (শুধু rotation): (3⁶ + 3 · 3⁴ + 12 · 3³ + 8 · 3²)/24 = (729 + 243 + 324 + 72)/24 = 1368/24 = 57. ভাগফল পূর্ণসংখ্যা না এলে নিশ্চিতভাবে কোথাও ভুল হয়েছে: এটি Burnside-এর হিসাবের সবচেয়ে সস্তা পরীক্ষা।

যুক্তির ভুল ধরুন: “orbit সমান আকারের”

একজন লিখলেন: “৬ পুঁতি, ২ রঙের necklace: মোট 2⁶ = 64টি string, আর প্রতিটি necklace ৬টি rotation থেকে আসে। তাই উত্তর 64/6 ≈ 10.67, অর্থাৎ প্রায় ১১টি।”

ভুল কোথায়: “প্রতিটি necklace ঠিক ৬টি string থেকে আসে” দাবিটি মিথ্যা। 000000-এর orbit-এ ১টি string, 010101-এর orbit-এ ২টি, 001001-এর orbit-এ ৩টি। Orbit–stabilizer অনুযায়ী orbit-এর আকার 6-এর যেকোনো উৎপাদক হতে পারে। ভাগফল পূর্ণসংখ্যা না হওয়াই সতর্কসংকেত, আর “কাছের পূর্ণসংখ্যায় গোল করা” কোনো গাণিতিক যুক্তি নয়। সঠিক উত্তর Burnside দিয়ে 84/6 = 14; ভুল ধারণাটি পর্ব ৩৩-এর গোল টেবিলের ভাগের নিয়ম থেকে এসেছে, যেখানে সব মানুষ আলাদা বলে সব orbit-এর আকার সত্যিই n.

১০ · AI-এর যুগে — symmetry গণনার উত্তর যাচাই

Symmetry-র গণনায় AI সহকারী প্রায়ই সূত্রটি ঠিক লেখে, কিন্তু প্রয়োগে ভুল করে, আর সেই ভুল আত্মবিশ্বাসী ভাষায় আসে। কয়েকটি নিয়মিত ভুল:

AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট

• Group-এর ধরনগুলোর সংখ্যা যোগ করে |G| মিলিয়েছি
• প্রতিটি |Fix(g)| = k^{(cycle-এর সংখ্যা)} নিজে গুনে দেখেছি
• শেষ ভাগফল পূর্ণসংখ্যা কি না দেখেছি
• ছোট একটি ক্ষেত্রে (যেমন k = 2, ছোট n) brute force দিয়ে উত্তর মিলিয়েছি
• প্রশ্নে কোন symmetry চলে (rotation, reflection) তা উত্তরের group-এর সঙ্গে মিলিয়েছি
• উদ্ধৃত নাম, সাল আর উৎস বিশ্বস্ত জায়গায় মিলিয়েছি

Burnside-এর হিসাবের সৌন্দর্য হলো এর প্রতিটি ধাপ ছোট আর যাচাইযোগ্য: একটি সারণি, কয়েকটি ঘাত, একটি যোগ আর একটি ভাগ। AI-এর উত্তরকে সেই সারণিতে ভেঙে নিন, আর একটি দশ লাইনের brute force চালিয়ে মিলিয়ে নিন। দুটি স্বাধীন পথ একই সংখ্যা দিলে তবেই উত্তরে ভরসা করুন।