বার্নসাইডের লেমা / পোলিয়ার গণনা উপপাদ্য#

বার্নসাইডের লেমা#

বার্নসাইডের লেমা ১৮৯৭ সালে বার্নসাইড দ্বারা প্রকাশিত ও প্রমাণিত হয়েছিল, কিন্তু ঐতিহাসিকভাবে এটি ১৮৮৭ সালে ফ্রোবেনিয়াস দ্বারা এবং আরো আগে ১৮৪৫ সালে কশি দ্বারা আবিষ্কৃত হয়েছিল। তাই একে কখনো কখনো কশি-ফ্রোবেনিয়াস লেমা-ও বলা হয়।

বার্নসাইডের লেমা আমাদের সেটের অভ্যন্তরীণ প্রতিসাম্যের উপর ভিত্তি করে তুল্যতা শ্রেণীর সংখ্যা গণনা করতে দেয়।

বস্তু ও উপস্থাপনা#

আমাদের বস্তুর সংখ্যা এবং উপস্থাপনার সংখ্যার মধ্যে স্পষ্ট পার্থক্য করতে হবে।

বিভিন্ন উপস্থাপনা একই বস্তুর সাথে সংশ্লিষ্ট হতে পারে, কিন্তু অবশ্যই প্রতিটি উপস্থাপনা ঠিক একটি বস্তুর সাথে সংশ্লিষ্ট। ফলে সব উপস্থাপনার সেট তুল্যতা শ্রেণীতে বিভক্ত হয়। আমাদের কাজ হলো বস্তুর সংখ্যা, অথবা সমতুল্যভাবে, তুল্যতা শ্রেণীর সংখ্যা গণনা করা। নিচের উদাহরণটি বস্তু ও উপস্থাপনার মধ্যে পার্থক্য আরো স্পষ্ট করবে।

উদাহরণ: বাইনারি ট্রি-র রং করা#

ধরুন আমাদের নিম্নলিখিত সমস্যা আছে। আমাদের $n$ শীর্ষবিশিষ্ট একটি মূলযুক্ত বাইনারি ট্রি-কে দুটি রঙে রং করার কতগুলো উপায় আছে তা গুনতে হবে, যেখানে প্রতিটি শীর্ষে আমরা বাম ও ডান সন্তানের মধ্যে পার্থক্য করি না।

এখানে বস্তুর সেট হলো ট্রি-র বিভিন্ন রং করার সেট।

এখন আমরা উপস্থাপনার সেট সংজ্ঞায়িত করি। একটি রং করার উপস্থাপনা হলো একটি ফাংশন $f(v)$, যা প্রতিটি শীর্ষে একটি রং নির্ধারণ করে (এখানে আমরা রং $0$ এবং $1$ ব্যবহার করি)। উপস্থাপনার সেট হলো এই ধরনের সব সম্ভব ফাংশনের সেট, এবং এর আকার স্পষ্টতই $2^n$।

একই সাথে আমরা এই সেটকে তুল্যতা শ্রেণীতে বিভক্ত করি।

উদাহরণস্বরূপ, ধরি $n = 3$, এবং ট্রিটি মূল $1$ ও তার দুই সন্তান $2$ এবং $3$ নিয়ে গঠিত। তাহলে নিচের ফাংশন $f_1$ এবং $f_2$ সমতুল্য বলে বিবেচিত হবে।

$$\begin{array}{ll} f_1(1) = 0 & f_2(1) = 0\\ f_1(2) = 1 & f_2(2) = 0\\ f_1(3) = 0 & f_2(3) = 1 \end{array}$$

অপরিবর্তনীয় বিন্যাস#

কেন এই দুটি ফাংশন $f_1$ এবং $f_2$ একই তুল্যতা শ্রেণীতে পড়ে? স্বজ্ঞাতভাবে এটা বোধগম্য - আমরা শীর্ষ $1$ এর সন্তান, শীর্ষ $2$ এবং $3$, পুনর্বিন্যাস করতে পারি, এবং ফাংশন $f_1$ এর এরকম রূপান্তরের পর এটি $f_2$ এর সাথে মিলে যাবে।

কিন্তু আনুষ্ঠানিকভাবে এর অর্থ হলো একটি অপরিবর্তনীয় পারমুটেশন $\pi$ আছে (অর্থাৎ একটি পারমুটেশন যা বস্তু নিজেকে পরিবর্তন করে না, শুধু এর উপস্থাপনা পরিবর্তন করে), যেন:

$$f_2 \pi \equiv f_1$$

সুতরাং বস্তুর সংজ্ঞা থেকে শুরু করে, আমরা সব অপরিবর্তনীয় পারমুটেশন খুঁজে পেতে পারি, অর্থাৎ সব পারমুটেশন যেগুলো উপস্থাপনায় প্রয়োগ করলে বস্তু পরিবর্তন করে না। তারপর আমরা পরীক্ষা করতে পারি দুটি ফাংশন $f_1$ এবং $f_2$ সমতুল্য কিনা (অর্থাৎ তারা একই বস্তুর সাথে সংশ্লিষ্ট কিনা) প্রতিটি অপরিবর্তনীয় পারমুটেশনের জন্য $f_2 \pi \equiv f_1$ শর্ত পরীক্ষা করে (অথবা সমতুল্যভাবে $f_1 \pi \equiv f_2$)। যদি অন্তত একটি পারমুটেশন পাওয়া যায় যার জন্য শর্ত পূরণ হয়, তাহলে $f_1$ এবং $f_2$ সমতুল্য, অন্যথায় তারা সমতুল্য নয়।

বস্তুর সংজ্ঞার সাপেক্ষে এরকম সব অপরিবর্তনীয় পারমুটেশন খোঁজা বার্নসাইডের লেমা এবং পোলিয়ার গণনা উপপাদ্য উভয় প্রয়োগের জন্য একটি মূল ধাপ। এটা স্পষ্ট যে এই অপরিবর্তনীয় পারমুটেশনগুলো নির্দিষ্ট সমস্যার উপর নির্ভর করে, এবং তাদের খোঁজা সম্পূর্ণরূপে অন্তর্জ্ঞানমূলক বিবেচনার উপর ভিত্তি করে একটি হিউরিস্টিক প্রক্রিয়া। তবে বেশিরভাগ ক্ষেত্রে কয়েকটি “মৌলিক” পারমুটেশন হাতে খুঁজে বের করাই যথেষ্ট, যেগুলো দিয়ে বাকি সব পারমুটেশন তৈরি করা যায় (এবং কাজের এই অংশ কম্পিউটারে স্থানান্তরিত করা যায়)।

বুঝতে অসুবিধা নেই যে অপরিবর্তনীয় পারমুটেশনগুলো একটি গ্রুপ গঠন করে, কারণ অপরিবর্তনীয় পারমুটেশনের গুণফল (সংযোজন)-ও একটি অপরিবর্তনীয় পারমুটেশন। আমরা অপরিবর্তনীয় পারমুটেশনের গ্রুপকে $G$ দ্বারা চিহ্নিত করি।

লেমার বিবৃতি#

লেমার সূত্রায়নের জন্য আমাদের বীজগণিত থেকে আরেকটি সংজ্ঞা দরকার। পারমুটেশন $\pi$ এর জন্য একটি স্থির বিন্দু $f$ হলো এমন একটি উপাদান যা এই পারমুটেশনের অধীনে অপরিবর্তিত থাকে: $f \equiv f \pi$। উদাহরণস্বরূপ আমাদের উদাহরণে স্থির বিন্দুগুলো হলো সেই ফাংশন $f$, যেগুলো এমন রং করার সাথে সংশ্লিষ্ট যা পারমুটেশন $\pi$ প্রয়োগ করলে পরিবর্তন হয় না (অর্থাৎ ফাংশনের সমতার আনুষ্ঠানিক অর্থে তারা পরিবর্তন হয় না)। আমরা পারমুটেশন $\pi$ এর জন্য স্থির বিন্দুর সংখ্যা $I(\pi)$ দ্বারা চিহ্নিত করি।

তাহলে বার্নসাইডের লেমা বলে: তুল্যতা শ্রেণীর সংখ্যা গ্রুপ $G$ এর সব পারমুটেশনের সাপেক্ষে স্থির বিন্দুর সংখ্যার যোগফলকে এই গ্রুপের আকার দিয়ে ভাগ করলে পাওয়া যায়:

$$|\text{Classes}| = \frac{1}{|G|} \sum_{\pi \in G} I(\pi)$$

যদিও বার্নসাইডের লেমা নিজে ব্যবহারিকভাবে এতটা সুবিধাজনক নয় ($I(\pi)$ এর মান দ্রুত কীভাবে বের করতে হয় তা অস্পষ্ট), এটি সবচেয়ে স্পষ্টভাবে সেই গাণিতিক সারমর্ম প্রকাশ করে যার উপর তুল্যতা শ্রেণী গণনার ধারণা ভিত্তি করে।

বার্নসাইডের লেমার প্রমাণ#

এখানে বর্ণিত বার্নসাইডের লেমার প্রমাণ ব্যবহারিক প্রয়োগের জন্য গুরুত্বপূর্ণ নয়, তাই প্রথম পাঠে এড়িয়ে যাওয়া যায়।

এখানকার প্রমাণটি সবচেয়ে সরল পরিচিত প্রমাণ, এবং এতে গ্রুপ তত্ত্ব ব্যবহৃত হয়নি। প্রমাণটি Kenneth P. Bogart ১৯৯১ সালে প্রকাশ করেছিলেন।

আমাদের নিম্নলিখিত বিবৃতি প্রমাণ করতে হবে:

$$|\text{Classes}| \cdot |G| = \sum_{\pi \in G} I(\pi)$$

ডান পক্ষের মান “অপরিবর্তনীয় জোড়া” $(f, \pi)$ এর সংখ্যা ছাড়া আর কিছুই নয়, অর্থাৎ এমন জোড়া যেন $f \pi \equiv f$। এটা স্পষ্ট যে আমরা যোগফলের ক্রম পরিবর্তন করতে পারি। আমরা যোগফলকে সব উপাদান $f$ এর উপর চালাই এবং $J(f)$ এর মান যোগ করি - যে কতগুলো পারমুটেশনের জন্য $f$ একটি স্থির বিন্দু।

$$|\text{Classes}| \cdot |G| = \sum_{f} J(f)$$

এই সূত্র প্রমাণ করতে আমরা একটি টেবিল তৈরি করবো যার কলামগুলো সব ফাংশন $f_i$ দিয়ে এবং সারিগুলো সব পারমুটেশন $\pi_j$ দিয়ে চিহ্নিত। এবং আমরা ঘরগুলো $f_i \pi_j$ দিয়ে পূরণ করি। যদি আমরা এই টেবিলের কলামগুলোকে সেট হিসেবে দেখি, তাহলে কিছু কলাম মিলে যাবে, এবং এর মানে সংশ্লিষ্ট ফাংশন $f$-ও সমতুল্য। সুতরাং ভিন্ন (সেট হিসেবে) কলামের সংখ্যা শ্রেণীর সংখ্যার সমান। আনুষঙ্গিকভাবে, গ্রুপ তত্ত্বের দৃষ্টিকোণ থেকে, $f_i$ দিয়ে চিহ্নিত কলামটি এই উপাদানের কক্ষপথ। সমতুল্য উপাদানের জন্য কক্ষপথ মিলে যায়, এবং কক্ষপথের সংখ্যাই ঠিক শ্রেণীর সংখ্যা দেয়।

সুতরাং টেবিলের কলামগুলো তুল্যতা শ্রেণীতে বিভক্ত হয়। একটি শ্রেণী ঠিক করি, এবং এর কলামগুলো দেখি। প্রথমত লক্ষ্য করুন, এই কলামগুলোতে শুধুমাত্র তুল্যতা শ্রেণীর উপাদান $f_i$ থাকতে পারে (অন্যথায় কোনো পারমুটেশন $\pi_j$ কোনো একটি ফাংশনকে ভিন্ন তুল্যতা শ্রেণীতে সরিয়ে দিত, যা অসম্ভব কারণ আমরা শুধু অপরিবর্তনীয় পারমুটেশন বিবেচনা করছি)। দ্বিতীয়ত প্রতিটি উপাদান $f_i$ প্রতিটি কলামে সমান সংখ্যকবার উপস্থিত হবে (এটিও এই কারণে যে কলামগুলো সমতুল্য উপাদানের সাথে সংশ্লিষ্ট)। এ থেকে আমরা উপসংহার টানতে পারি যে একই তুল্যতা শ্রেণীর সব কলাম মাল্টিসেট হিসেবে পরস্পরের সাথে মিলে যায়।

এখন একটি যেকোনো উপাদান $f$ ঠিক করি। একদিকে, এটি তার কলামে ঠিক $J(f)$ বার উপস্থিত হয় (সংজ্ঞা অনুসারে)। অন্যদিকে, একই তুল্যতা শ্রেণীর সব কলাম মাল্টিসেট হিসেবে একই। তাই একটি প্রদত্ত তুল্যতা শ্রেণীর প্রতিটি কলামে যেকোনো উপাদান $g$ ঠিক $J(g)$ বার উপস্থিত হয়।

সুতরাং যদি আমরা প্রতিটি তুল্যতা শ্রেণী থেকে ইচ্ছামতো একটি কলাম নিই, এবং তাদের উপাদান সংখ্যা যোগ করি, আমরা একদিকে পাবো $|\text{Classes}| \cdot |G|$ (কলাম সংখ্যাকে সারি সংখ্যা দিয়ে গুণ করে), এবং অন্যদিকে সব $f$ এর জন্য $J(f)$ এর যোগফল (এটি পূর্ববর্তী সব যুক্তি থেকে অনুসরণ করে):

$$|\text{Classes}| \cdot |G| = \sum_{f} J(f)$$

পোলিয়ার গণনা উপপাদ্য#

পোলিয়ার গণনা উপপাদ্য বার্নসাইডের লেমার একটি সাধারণীকরণ, এবং এটি তুল্যতা শ্রেণীর সংখ্যা বের করার জন্য আরো সুবিধাজনক হাতিয়ার প্রদান করে। লক্ষণীয় যে এই উপপাদ্যটি পোলিয়ার আগেই ১৯২৭ সালে Redfield আবিষ্কার করেছিলেন, কিন্তু তাঁর প্রকাশনা গণিতবিদদের নজরে আসেনি। পোলিয়া স্বাধীনভাবে ১৯৩৭ সালে একই ফলাফলে পৌঁছেছিলেন, এবং তাঁর প্রকাশনা আরো সফল হয়েছিল।

এখানে আমরা পোলিয়ার গণনা উপপাদ্যের শুধুমাত্র একটি বিশেষ ক্ষেত্র আলোচনা করবো, যা ব্যবহারিকভাবে অত্যন্ত কার্যকর হবে। উপপাদ্যের সাধারণ সূত্র আলোচনা করা হবে না।

আমরা $C(\pi)$ দ্বারা পারমুটেশন $\pi$ তে চক্রের সংখ্যা চিহ্নিত করি। তাহলে নিম্নলিখিত সূত্র (পোলিয়ার গণনা উপপাদ্যের একটি বিশেষ ক্ষেত্র) সত্য:

$$|\text{Classes}| = \frac{1}{|G|} \sum_{\pi \in G} k^{C(\pi)}$$

$k$ হলো প্রতিটি উপস্থাপনা উপাদান কতগুলো মান নিতে পারে তার সংখ্যা, বাইনারি ট্রি রং করার ক্ষেত্রে এটি হবে $k = 2$।

প্রমাণ#

এই সূত্রটি বার্নসাইডের লেমার সরাসরি পরিণতি। এটি পেতে, আমাদের শুধু লেমায় উপস্থিত $I(\pi)$ এর একটি সুস্পষ্ট রাশি বের করতে হবে। মনে করুন, $I(\pi)$ হলো পারমুটেশন $\pi$ তে স্থির বিন্দুর সংখ্যা।

সুতরাং আমরা একটি পারমুটেশন $\pi$ এবং কিছু উপাদান $f$ বিবেচনা করি। $\pi$ প্রয়োগের সময়, $f$ এর উপাদানগুলো পারমুটেশনের চক্র অনুসারে সরে যায়। যেহেতু ফলাফলে $f \equiv f \pi$ পেতে হবে, একটি চক্র দ্বারা স্পর্শিত উপাদানগুলো সবই সমান হতে হবে। একই সাথে বিভিন্ন চক্র স্বাধীন। সুতরাং প্রতিটি পারমুটেশন চক্র $\pi$ এর জন্য আমরা একটি মান ($k$ সম্ভব থেকে) বেছে নিতে পারি এবং এভাবে আমরা স্থির বিন্দুর সংখ্যা পাই:

$$I(\pi) = k^{C(\pi)}$$

প্রয়োগ: নেকলেস রং করা#

“নেকলেস” সমস্যাটি ক্লাসিক সমাবেশ বিদ্যার সমস্যাগুলোর একটি। কাজটি হলো $n$ টি পুঁতি দিয়ে কতগুলো ভিন্ন নেকলেস তৈরি করা যায় তা গণনা করা, যেখানে প্রতিটি পুঁতি $k$ টি রঙের যেকোনো একটিতে রং করা যায়। দুটি নেকলেস তুলনা করার সময়, তাদের ঘোরানো যায়, কিন্তু উল্টানো যায় না (অর্থাৎ চক্রাকার স্থানান্তর অনুমোদিত)।

এই সমস্যায় আমরা তৎক্ষণাৎ অপরিবর্তনীয় পারমুটেশনের গ্রুপ পেতে পারি:

$$\begin{align} \pi_0 &= 1 2 3 \dots n\\ \pi_1 &= 2 3 \dots n 1\\ \pi_2 &= 3 \dots n 12\\ &\dots\\ \pi_{n-1} &= n 1 2 3\dots\end{align}$$

$C(\pi_i)$ গণনার একটি সুস্পষ্ট সূত্র বের করা যাক। প্রথমে লক্ষ্য করি, পারমুটেশন $\pi_i$ এর $j$-তম অবস্থানে মান $i + j$ (মডুলো $n$ নেওয়া) আছে। $\pi_i$ এর চক্র কাঠামো পরীক্ষা করলে দেখি যে $1$ যায় $1 + i$ তে, $1 + i$ যায় $1 + 2i$ তে, যা যায় $1 + 3i$ তে, ইত্যাদি, যতক্ষণ না আমরা $1 + k n$ আকারের একটি সংখ্যায় পৌঁছাই। বাকি উপাদানগুলোর জন্যও একই কথা বলা যায়। ফলে আমরা দেখি সব চক্রের দৈর্ঘ্য একই, যথা $\frac{\text{lcm}(i, n)}{i} = \frac{n}{\gcd(i, n)}$। সুতরাং $\pi_i$ তে চক্রের সংখ্যা হবে $\gcd(i, n)$।

পোলিয়ার গণনা উপপাদ্যে এই মানগুলো বসিয়ে আমরা সমাধান পাই:

$$\frac{1}{n} \sum_{i=1}^n k^{\gcd(i, n)}$$

আপনি এই সূত্রটি এই আকারে রাখতে পারেন, অথবা আরো সরলীকরণ করতে পারেন। যোগফলটি এমনভাবে রূপান্তর করি যাতে এটি $n$ এর সব ভাজকের উপর চলে। মূল যোগফলে অনেক সমতুল্য পদ থাকবে: যদি $i$ $n$ এর ভাজক না হয়, তাহলে $\gcd(i, n)$ গণনা করার পর এমন একটি ভাজক পাওয়া যাবে। তাই প্রতিটি ভাজক $d ~|~ n$ এর জন্য এর পদ $k^{\gcd(d, n)} = k^d$ যোগফলে একাধিকবার আসবে, অর্থাৎ সমস্যার উত্তর এভাবে লেখা যায়

$$\frac{1}{n} \sum_{d ~|~ n} C_d k^d,$$

যেখানে $C_d$ হলো $\gcd(i, n) = d$ এমন $i$ এর সংখ্যা। আমরা এই মানের একটি সুস্পষ্ট রাশি বের করতে পারি। এরকম যেকোনো $i$ এর আকার $i = d j$ যেখানে $\gcd(j, n / d) = 1$ (অন্যথায় $\gcd(i, n) > d$)। সুতরাং এই আচরণের $j$ এর সংখ্যা গুনতে পারি। অয়লারের ফি ফাংশন আমাদের ফলাফল দেয় $C_d = \phi(n / d)$, এবং তাই আমরা উত্তর পাই:

$$\frac{1}{n} \sum_{d ~|~ n} \phi\left(\frac{n}{d}\right) k^d$$

প্রয়োগ: টোরাস রং করা#

প্রায়ই আমরা তুল্যতা শ্রেণীর সংখ্যার জন্য সুস্পষ্ট সূত্র পাই না। অনেক সমস্যায় একটি গ্রুপে পারমুটেশনের সংখ্যা হাতে গণনার জন্য অনেক বেশি হতে পারে এবং তাদের মধ্যে চক্রের সংখ্যা বিশ্লেষণমূলকভাবে গণনা করা সম্ভব হয় না।

সেক্ষেত্রে আমাদের হাতে কয়েকটি “মৌলিক” পারমুটেশন খুঁজতে হবে, যাতে তারা সম্পূর্ণ গ্রুপ $G$ তৈরি করতে পারে। এরপর আমরা একটি প্রোগ্রাম লিখতে পারি যা গ্রুপ $G$ এর সব পারমুটেশন তৈরি করবে, তাদের চক্র সংখ্যা গুনবে, এবং সূত্র দিয়ে উত্তর গণনা করবে।

টোরাস রং করার সমস্যার উদাহরণ বিবেচনা করি। একটি $n \times m$ ($n < m$) চেকওয়ালা কাগজের পাতা আছে, কিছু ঘর কালো। তারপর $m$ দৈর্ঘ্যের দুটি পাশ জোড়া লাগিয়ে এই পাতা থেকে একটি সিলিন্ডার পাওয়া যায়। তারপর দুটি বৃত্ত (উপর ও নিচ) মোচড় না দিয়ে জোড়া লাগিয়ে সিলিন্ডার থেকে একটি টোরাস পাওয়া যায়। কাজটি হলো ভিন্ন রঙিত টোরাসের সংখ্যা গণনা করা, ধরে নিয়ে যে আমরা জোড়া লাগানো রেখাগুলো দেখতে পাচ্ছি না, এবং টোরাসটি ঘোরানো ও পালটানো যায়।

আবার আমরা $n \times m$ কাগজের টুকরো দিয়ে শুরু করি। নিম্নলিখিত ধরনের রূপান্তরগুলো তুল্যতা শ্রেণী সংরক্ষণ করে তা দেখা সহজ: সারিগুলোর চক্রাকার স্থানান্তর, কলামগুলোর চক্রাকার স্থানান্তর, এবং পাতাটিকে ১৮০ ডিগ্রি ঘোরানো। এটাও দেখা সহজ যে এই রূপান্তরগুলো অপরিবর্তনীয় রূপান্তরের সম্পূর্ণ গ্রুপ তৈরি করতে পারে। আমরা যদি কোনোভাবে কাগজের ঘরগুলো সংখ্যা দিই, তাহলে এই ধরনের রূপান্তরের সাথে সংশ্লিষ্ট তিনটি পারমুটেশন $p_1$, $p_2$, $p_3$ লেখা যায়।

এরপর শুধু গুণফল হিসেবে প্রাপ্ত সব পারমুটেশন তৈরি করা বাকি। এটা স্পষ্ট যে এরকম সব পারমুটেশন $p_1^{i_1} p_2^{i_2} p_3^{i_3}$ আকারের যেখানে $i_1 = 0 \dots m-1$, $i_2 = 0 \dots n-1$, $i_3 = 0 \dots 1$।

সুতরাং আমরা এই সমস্যার ইমপ্লিমেন্টেশন লিখতে পারি।

using Permutation = vector<int>;

void operator*=(Permutation& p, Permutation const& q) {
    Permutation copy = p;
    for (int i = 0; i < p.size(); i++)
        p[i] = copy[q[i]];
}

int count_cycles(Permutation p) {
    int cnt = 0;
    for (int i = 0; i < p.size(); i++) {
        if (p[i] != -1) {
            cnt++;
            for (int j = i; p[j] != -1;) {
                int next = p[j];
                p[j] = -1;
                j = next;
            }
        }
    }
    return cnt;
}

int solve(int n, int m) {
    Permutation p(n*m), p1(n*m), p2(n*m), p3(n*m);
    for (int i = 0; i < n*m; i++) {
        p[i] = i;
        p1[i] = (i % n + 1) % n + i / n * n;
        p2[i] = (i / n + 1) % m * n + i % n;
        p3[i] = (m - 1 - i / n) * n + (n - 1 - i % n);
    }

    set<Permutation> s;
    for (int i1 = 0; i1 < n; i1++) {
        for (int i2 = 0; i2 < m; i2++) {
            for (int i3 = 0; i3 < 2; i3++) {
                s.insert(p);
                p *= p3;
            }
            p *= p2;
        }
        p *= p1;
    }

    int sum = 0;
    for (Permutation const& p : s) {
        sum += 1 << count_cycles(p);
    }
    return sum / s.size();
}

বার্নসাইডের লেমা / পোলিয়ার গণনা উপপাদ্য#