Problem link ও উৎস
- **Original source:** Burnside's lemma (necklace counting under rotation)
- **Platform:** CP-Algorithms —
- **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)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#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 মাথায় উপভোগ করবে।
### Input ও output {#6-example-input-and-output}
```text
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)` — এই সূত্রটাই কোডের প্রাণ।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো একটা গোল টেবিলে `n`টা চেয়ারে বন্ধুরা বসেছে, আর তুমি ওপর থেকে ছবি তুলছ। টেবিলটা ঘোরে — তাই একই বসা-বিন্যাস ঘুরিয়ে নিলে "একই দৃশ্য"। কতগুলো **আসলে আলাদা** দৃশ্য?
সরাসরি গুনতে গেলে গুলিয়ে যাবে — কোনটা কোনটার ঘোরানো রূপ? Burnside-এর চালাকি: প্রতিটা সম্ভাব্য ঘোরানোর কোণের (0°, একঘর, দুইঘর...) জন্য জিজ্ঞেস করো — "এই কোণে ঘোরালে কোন কোন দৃশ্য হুবহু একই থাকে?" সেগুলো গুনে নাও, সব কোণের গড় নাও — ব্যস, আলাদা দৃশ্যের সংখ্যা। প্রতিটা আসল দৃশ্য তার সব ঘোরানো-রূপ মিলে গড়ে ঠিক একবার গোনা পড়ে।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#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 সংখ্যা — এটাই গোনার নতুন চশমা।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল ধারণা **Burnside's lemma**:
```text
আলাদা 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-এর জট গড়-হিসাবে আপনাআপনি ঠিক হয়ে যায়।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
Burnside না জানলে — সরাসরি: সব `k^n` coloring তৈরি করো, প্রতিটার **canonical form** (সব ঘূর্ণনের মধ্যে সবচেয়ে ছোটটা) বের করো, আলাদা canonical গুনো:
```python
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`টা ঘূর্ণন:
```text
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-এর সুন্দর সূত্র আছে:
```text
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` দিয়ে নিঃশেষে বিভাজ্য, উত্তর পূর্ণসংখ্যা।
### ছবিতে বোঝা {#5-visual-explanation}
`n = 3`, `k = 2`-এর fixed point হিসাব:
```text
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:
```text
●●● (সব লাল) ○○○ (সব নীল)
●●○ (2 লাল 1 নীল) ●○○ (1 লাল 2 নীল)
```
লক্ষ করো — `identity` rotation **সব** coloring fix করে; তাকে বাদ দিলে উত্তর ভুল হবে।
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
`n = 4`, `k = 2` — `k^gcd(r,n)` সূত্রে:
1. **r = 0 (identity):** `gcd(0, 4) = 4` → `2⁴ = 16`। (সব coloring fix)।
2. **r = 1:** `gcd(1, 4) = 1` → `2¹ = 2`। (এক চক্র, সব এক রঙ)।
3. **r = 2:** `gcd(2, 4) = 2` → `2² = 4`। (দুই চক্র: {0,2}, {1,3})।
4. **r = 3:** `gcd(3, 4) = 1` → `2¹ = 2`।
5. **যোগ ও গড়:** `(16 + 2 + 4 + 2) / 4 = 24 / 4 = 6`। আলাদা necklace = **6**। (brute force-ও 6 বলে ✓)।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
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}
```text
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` দেয়।
```text
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।
```text
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!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে ছাপবে:
```text
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!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#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}
1. **Identity rotation বাদ দেওয়া** — identity সব `k^n` coloring fix করে; `r=0` (gcd=n) বাদ দিলে উত্তর ভুল (concept-notes mistake #7)।
2. **gcd-এর জায়গায় ভুল সূত্র** — `r`-ঘোরায় fixed = `k^gcd(r,n)`; চক্র-সংখ্যা = `gcd(r,n)` — এটা গুলিয়ে ফেলা।
3. **Rotation আর reflection মিশিয়ে ফেলা** — এখানে শুধু rotation (cyclic group); necklace উল্টানোও (reflection) ধরলে আলাদা সূত্র (dihedral group)।
4. **`n` দিয়ে ভাগ করতে ভুলে যাওয়া** — Burnside গড়, তাই যোগফলকে symmetry সংখ্যা `n` দিয়ে ভাগ করা বাধ্যতামূলক।
5. **ভাগশেষ ভাবা** — যোগফল সবসময় `n`-এ নিঃশেষে বিভাজ্য (Burnside-এর গ্যারান্টি); উত্তর পূর্ণসংখ্যা, ভগ্নাংশ এলে হিসাবে ভুল।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **CP-Algorithms — Burnside's lemma & Pólya** (