146 — Burnside Lemma Intro¶

একদম আলাদা স্বাদের একটা problem — fresh মাথায় বোসো। প্রশ্নটা সরল শোনায়: "ঘোরালে যেগুলো এক, সেগুলো একবার করে গুনলে কতগুলো আলাদা জিনিস?" কিন্তু সরাসরি গুনতে গেলে double-counting-এর জট। Burnside lemma একটা অবাক-করা সহজ উত্তর দেয়: সব symmetry-র fixed point-এর গড়। মনে রাখো, এই level CP-leaning, interview-এর জন্য optional (repo-র plan অনুযায়ী)।

Source¶

Original source: Burnside's lemma (necklace counting under rotation)
Platform: CP-Algorithms — https://cp-algorithms.com/combinatorics/burnside.html
Topic: Math-based programming fundamentals → Level 11: Hard Mixed CP Patterns
Difficulty: Hard
Pattern: average fixed points (group action counting)
Basic idea inherited from: 044 (inclusion-exclusion / counting)

1. Problem in simple words¶

nটা পুঁতির একটা গোল necklace, প্রতিটা পুঁতি k রঙের একটায় রাঙানো যায়। কিন্তু necklace ঘোরানো যায় — তাই দুটো রং-বিন্যাস যদি ঘুরিয়ে একে অন্যের সমান হয়, সেগুলো একই necklace।

জিজ্ঞেস: কতগুলো আলাদা (distinct) necklace বানানো যায়?

ছোট উদাহরণ: n = 3 পুঁতি, k = 2 রঙ (লাল/নীল)। মোট রং-বিন্যাস 2³ = 8, কিন্তু ঘোরানো-সমান ধরলে আলাদা মাত্র 4টা — সব-লাল, সব-নীল, 2-লাল-1-নীল, 1-লাল-2-নীল। Burnside lemma এই 4 বের করে দেবে গড়-হিসাবে।

এটা CP-leaning level। Interview-পথে থাকলে এড়িয়ে মূল DS topic-এ যেতে পারো; এই গোনার জাদুটা পরে fresh মাথায় উপভোগ করবে।

2. What is the math idea?¶

মূল ধারণা Burnside's lemma:

আলাদা object সংখ্যা = (প্রতিটা symmetry-র fixed point সংখ্যার গড়)

= (1 / |G|) · Σ (g-এর অধীনে অপরিবর্তিত থাকা coloring সংখ্যা)
              g ∈ G

এখানে G = symmetry গুলোর সেট (necklace-এ n-টা rotation)।

"Fixed point" মানে — কোনো একটা symmetry g (যেমন "1 ঘর ঘোরাও") প্রয়োগ করলেও যে coloring গুলো অবিকল একই থাকে। অবাক ব্যাপার: আলাদা object গোনার বদলে, প্রতিটা symmetry আলাদা coloring কয়টাকে অপরিবর্তিত রাখে — তার গড় নিলেই উত্তর। double-counting-এর জট গড়-হিসাবে আপনাআপনি ঠিক হয়ে যায়।

3. Which basic idea does this inherit from?¶

দাঁড়িয়ে আছে counting / inclusion-exclusion (problem 044)-এর উপর — সেখানে শিখেছিলে সরাসরি গোনা কঠিন হলে চতুরভাবে (overcount বাদ দিয়ে) গোনা। Burnside সেই পরিবারের: সরাসরি "distinct necklace" গোনা কঠিন (কোনটা কোনটার ঘূর্ণন বোঝা ঝামেলা), তাই আমরা ঘুরপথে — symmetry-র fixed point দিয়ে — গুনি।

নতুন idea: group action আর orbit। ঘোরানোর সব রূপ মিলে একটা "group"; একটা coloring-এর সব ঘূর্ণিত রূপ মিলে তার "orbit" — আর প্রতিটা orbit আসলে একটা distinct necklace। Burnside বলে গড় fixed point = orbit সংখ্যা — এটাই গোনার নতুন চশমা।

4. Real-life analogy¶

ভাবো একটা গোল টেবিলে nটা চেয়ারে বন্ধুরা বসেছে, আর তুমি ওপর থেকে ছবি তুলছ। টেবিলটা ঘোরে — তাই একই বসা-বিন্যাস ঘুরিয়ে নিলে "একই দৃশ্য"। কতগুলো আসলে আলাদা দৃশ্য?

সরাসরি গুনতে গেলে গুলিয়ে যাবে — কোনটা কোনটার ঘোরানো রূপ? Burnside-এর চালাকি: প্রতিটা সম্ভাব্য ঘোরানোর কোণের (0°, একঘর, দুইঘর...) জন্য জিজ্ঞেস করো — "এই কোণে ঘোরালে কোন কোন দৃশ্য হুবহু একই থাকে?" সেগুলো গুনে নাও, সব কোণের গড় নাও — ব্যস, আলাদা দৃশ্যের সংখ্যা। প্রতিটা আসল দৃশ্য তার সব ঘোরানো-রূপ মিলে গড়ে ঠিক একবার গোনা পড়ে।

5. Visual explanation¶

n = 3, k = 2-এর fixed point হিসাব:

3টা rotation: 0-ঘোরা (identity), 1-ঘোরা, 2-ঘোরা

identity (কিছু ঘোরাও না):
   সব 2³ = 8 coloring-ই অপরিবর্তিত  ->  fixed = 8

1-ঘোরা (প্রতিটা পুঁতি এক ঘর সরে):
   অপরিবর্তিত থাকতে হলে পুঁতি 1 = পুঁতি 2 = পুঁতি 3 (সব এক রঙ)
   ->  fixed = 2  (সব-লাল, সব-নীল)

2-ঘোরা (দুই ঘর সরে):
   একই যুক্তি — সব এক রঙ  ->  fixed = 2

গড় = (8 + 2 + 2) / 3 = 12 / 3 = 4

হাতে মিলাও — ঠিক 4টা necklace:

●●●  (সব লাল)        ○○○  (সব নীল)
●●○  (2 লাল 1 নীল)   ●○○  (1 লাল 2 নীল)

লক্ষ করো — identity rotation সব coloring fix করে; তাকে বাদ দিলে উত্তর ভুল হবে।

6. Example input and output¶

n    k    আলাদা necklace   fixed points-এর যোগ / n
----------------------------------------------------------
3    2    4                (8 + 2 + 2) / 3
3    3    11               (27 + 3 + 3) / 3
4    2    6                (16 + 2 + 4 + 2) / 4
1    k    k                একটাই পুঁতি, ঘোরানোয় কিছু বদলায় না
n    1    1                এক রঙ — একটাই necklace

মূল edge case: n = 1 হলে rotation একটাই (identity), উত্তর k; k = 1 হলে সব এক রঙ, উত্তর সবসময় 1। আর r-ঘোরায় fixed coloring = k^gcd(r, n) — এই সূত্রটাই কোডের প্রাণ।

7. Brute force thinking¶

Burnside না জানলে — সরাসরি: সব k^n coloring তৈরি করো, প্রতিটার canonical form (সব ঘূর্ণনের মধ্যে সবচেয়ে ছোটটা) বের করো, আলাদা canonical গুনো:

from itertools import product


def necklaces_brute(n, k):
    seen = set()
    for c in product(range(k), repeat=n):          # সব k^n coloring
        rotations = [c[i:] + c[:i] for i in range(n)]   # n টা ঘূর্ণন
        canonical = min(rotations)                  # প্রতিনিধি = ক্ষুদ্রতম
        seen.add(canonical)
    return len(seen)

এটা সংজ্ঞার হুবহু — ঠিক উত্তর দেয় (n=3, k=2 → 4)। আর Burnside যাচাইয়ের নিখুঁত মাপকাঠি। কিন্তু k^n coloring — দ্রুত অসম্ভব।

8. Why brute force may be slow¶

Coloring-সংখ্যা k^n — exponential, আর প্রতিটার জন্য nটা ঘূর্ণন:

n = 10, k = 3  ->  3^10  ≈ 59000        (ঠিক আছে)
n = 30, k = 3  ->  3^30  ≈ 2×10^14       (অসম্ভব)
n = 20, k = 26 ->  26^20                 (কল্পনাতীত)

Burnside সূত্র: n টা rotation, প্রতিটায় gcd হিসাব  ->  O(n log n)

মূল কথা — সব coloring enumerate না করেও, প্রতি rotation-এর fixed count একটা সূত্রে (k^gcd(r,n)) সরাসরি পাওয়া যায়; exponential থেকে নেমে polynomial।

9. Better thinking¶

মূল insight (Burnside): সব coloring না গুনে, প্রতিটা rotation-এর fixed coloring গুনে গড় নাও। আর প্রতিটা rotation-এর fixed count-এর সুন্দর সূত্র আছে:

r ঘর ঘোরালে — পুঁতিগুলো gcd(r, n) টা cycle-এ ভাগ হয়
অপরিবর্তিত থাকতে প্রতিটা cycle-এর সব পুঁতি এক রঙ হতে হবে
->  সেই rotation-এর fixed coloring = k^gcd(r, n)

আলাদা necklace = (1/n) · Σ k^gcd(r, n),   r = 0..n-1

কেন gcd? r ঘর করে ঘোরালে একটা পুঁতি n/gcd(r,n) ধাপে নিজের জায়গায় ফেরে — তাই পুঁতিগুলো gcd(r,n)টা স্বাধীন চক্রে ভাগ হয়, প্রতি চক্র এক রঙ। সব r-এর জন্য যোগ করে n দিয়ে ভাগ।

10. Thinking tweak¶

এক লাইনের "আহা": distinct object সরাসরি গোনার বদলে উল্টে গোনো — প্রতিটা symmetry আলাদা কয়টা coloring অপরিবর্তিত রাখে, তার গড়ই উত্তর। কারণ প্রতিটা আসল object তার orbit-এর সব রূপ মিলে গড়ে ঠিক একবার গোনা পড়ে।

দুটো ফাঁদ: (১) identity rotation বাদ দেওয়া — identity-ও একটা group element, আর সে সব k^n coloring fix করে; বাদ দিলে উত্তর ভুল (concept-notes mistake #7)। (২) "গড় fixed point" তো ভগ্নাংশ হতে পারে — কিন্তু Burnside নিশ্চিত করে যোগফল সবসময় n দিয়ে নিঃশেষে বিভাজ্য, উত্তর পূর্ণসংখ্যা।

11. Step-by-step dry run¶

n = 4, k = 2 — k^gcd(r,n) সূত্রে:

r = 0 (identity): gcd(0, 4) = 4 → 2⁴ = 16। (সব coloring fix)।
r = 1: gcd(1, 4) = 1 → 2¹ = 2। (এক চক্র, সব এক রঙ)।
r = 2: gcd(2, 4) = 2 → 2² = 4। (দুই চক্র: {0,2}, {1,3})।
r = 3: gcd(3, 4) = 1 → 2¹ = 2।
যোগ ও গড়: (16 + 2 + 4 + 2) / 4 = 24 / 4 = 6। আলাদা necklace = 6। (brute force-ও 6 বলে ✓)।

12. Python solution¶

from math import gcd


def necklaces_rotation(n, k):
    """n পুঁতি, k রঙ, শুধু rotation symmetry — আলাদা necklace সংখ্যা।"""
    total = sum(k ** gcd(r, n) for r in range(n))   # প্রতি rotation-এর fixed
    return total // n                               # Burnside: গড়


from itertools import product


def necklaces_brute(n, k):
    """সব coloring-এর canonical form — যাচাইয়ের জন্য।"""
    seen = set()
    for c in product(range(k), repeat=n):
        rotations = [c[i:] + c[:i] for i in range(n)]
        seen.add(min(rotations))
    return len(seen)


# --- ছোট test গুলো (সব pass করা উচিত) ---
assert necklaces_rotation(3, 2) == 4            # (8 + 2 + 2) / 3
assert necklaces_rotation(4, 2) == 6            # (16 + 2 + 4 + 2) / 4
assert necklaces_rotation(1, 5) == 5            # একটা পুঁতি -> k
assert necklaces_rotation(6, 1) == 1            # এক রঙ -> 1

# brute force-এর সাথে এলোমেলো ছোট case-এ মিল (Burnside-এর প্রমাণ)
for n in range(1, 8):
    for k in range(1, 4):
        assert necklaces_rotation(n, k) == necklaces_brute(n, k), (n, k)

# n=3, k=2-এর fixed-point ভাঙা দেখাই
parts = [2 ** gcd(r, 3) for r in range(3)]
assert parts == [8, 2, 2]
assert sum(parts) // 3 == 4

print(necklaces_rotation(3, 2))     # 4
print(necklaces_rotation(4, 2))     # 6
print(necklaces_rotation(5, 3))     # 51
print("সব test pass!")

13. Line-by-line explanation¶

    total = sum(k ** gcd(r, n) for r in range(n))
    return total // n

এটাই পুরো Burnside। প্রতিটা rotation r (0 থেকে n−1)-এর জন্য fixed coloring = k^gcd(r,n) যোগ করি, তারপর rotation সংখ্যা n দিয়ে ভাগ — এটাই গড় fixed point = আলাদা necklace। r = 0-তে gcd(0,n) = n, তাই identity ঠিকঠাক k^n দেয়।

        rotations = [c[i:] + c[:i] for i in range(n)]
        seen.add(min(rotations))

brute version — একটা coloring-এর সব ঘূর্ণন বানিয়ে ক্ষুদ্রতমটা (canonical প্রতিনিধি) set-এ রাখি। একই orbit-এর সব coloring একই প্রতিনিধি দেয়, তাই len(seen) = distinct necklace।

parts = [2 ** gcd(r, 3) for r in range(3)]
assert parts == [8, 2, 2]

n=3, k=2-এর প্রতিটা rotation-এর fixed count দেখাই — [8, 2, 2], যোগ 12, ভাগ 3 = 4। concept-notes-এর সেই উদাহরণ।

বাকি assert গুলো যাচাই করে: হাতে-গোনা case, brute force-এর সাথে সব ছোট (n,k)-তে মিল, আর fixed-point ভাঙা। সব মিললে সব test pass!।

14. Output walkthrough¶

চালালে ছাপবে:

4
6
51
সব test pass!

প্রথম লাইন n=3, k=2 → 4 (সেই 4টা necklace)। দ্বিতীয় n=4, k=2 → 6। তৃতীয় n=5, k=3 → 51। তার আগের সব assert চুপচাপ pass — Burnside সূত্র আর brute force সব ছোট case-এ একমত। সবশেষে সব test pass!।

15. Time complexity¶

O(n log n) — nটা rotation, প্রতিটায় একটা gcd (O(log n)) আর একটা power। brute force ছিল O(k^n · n) (exponential) — সূত্র সেটাকে polynomial-এ নামিয়েছে। (k^gcd power-এর খরচ ধরলে সামান্য বাড়বে, কিন্তু exponential-এর তুলনায় নগণ্য।)

16. Space complexity¶

O(1) — সূত্রে শুধু একটা accumulator। brute version অবশ্য O(distinct necklace) set রাখে (canonical গুলো), কিন্তু আসল সমাধান O(1)।

17. Common mistakes¶

Identity rotation বাদ দেওয়া — identity সব k^n coloring fix করে; r=0 (gcd=n) বাদ দিলে উত্তর ভুল (concept-notes mistake #7)।
gcd-এর জায়গায় ভুল সূত্র — r-ঘোরায় fixed = k^gcd(r,n); চক্র-সংখ্যা = gcd(r,n) — এটা গুলিয়ে ফেলা।
Rotation আর reflection মিশিয়ে ফেলা — এখানে শুধু rotation (cyclic group); necklace উল্টানোও (reflection) ধরলে আলাদা সূত্র (dihedral group)।
n দিয়ে ভাগ করতে ভুলে যাওয়া — Burnside গড়, তাই যোগফলকে symmetry সংখ্যা n দিয়ে ভাগ করা বাধ্যতামূলক।
ভাগশেষ ভাবা — যোগফল সবসময় n-এ নিঃশেষে বিভাজ্য (Burnside-এর গ্যারান্টি); উত্তর পূর্ণসংখ্যা, ভগ্নাংশ এলে হিসাবে ভুল।

18. Harder problems that inherit this idea¶

CP-Algorithms — Burnside's lemma & Pólya (https://cp-algorithms.com/combinatorics/burnside.html) — rotation + reflection (Pólya enumeration)।
Codeforces — combinatorics/Burnside tag (https://codeforces.com/problemset?tags=combinatorics) — necklace ও বিন্যাস গোনার নানা রূপ।
Project Euler-ঘরানা necklace counting — বড় n, k-তে modular Burnside প্রয়োগ।

19. Pattern learned¶

Burnside's lemma (average fixed points) — symmetry-র অধীনে distinct object গোনা = প্রতিটা symmetry যত coloring অপরিবর্তিত রাখে তার গড়। necklace rotation-এ fixed = k^gcd(r,n), উত্তর = (1/n)·Σ k^gcd(r,n)। identity ভুলো না।

20. Final summary¶

ভবিষ্যতের আমাকে এক লাইনে: "'ঘোরালে/উল্টালে এক' গুনতে Burnside — distinct = সব symmetry-র fixed point-এর গড়। necklace rotation-এ (1/n)·Σ k^gcd(r,n); identity (সব fix করে) বাদ দিও না। n=3,k=2 → (8+2+2)/3 = 4।"

পরের ধাপ → 147 — Matrix Power on Graphs (level 10-এর matrix exponentiation-এর graph-রূপ)। শিকড় → 044 — Inclusion-Exclusion / counting।

ফিরে দেখা: এই level-এর map → ../README.md · চিন্তার ছাঁচ → ../concept-notes.md · template → ../../../templates/math-problem-note-template.md।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" এমন দাবি করা হয়নি — বরং "CP-style pattern" / "common interview pattern" বলা হয়েছে।