پرش به محتویات

لم برنساید / قضیه شمارش پولیا

لم برنساید

لم برنساید در سال ۱۸۹۷ توسط برنساید فرمول‌بندی و اثبات شد، اما از نظر تاریخی، پیش از او در سال ۱۸۸۷ توسط فروبنیوس و حتی قبل‌تر در سال ۱۸۴۵ توسط کوشی کشف شده بود. به همین دلیل، گاهی اوقات لم کوشی-فروبنیوس نیز نامیده می‌شود.

لم برنساید به ما امکان می‌دهد تا تعداد کلاس‌های هم‌ارزی را در مجموعه‌ها، بر اساس تقارن داخلی بشماریم.

اشیاء و نمایش‌ها

ما باید به وضوح بین تعداد اشیاء و تعداد نمایش‌ها تمایز قائل شویم.

نمایش‌های مختلف می‌توانند متناظر با اشیاء یکسانی باشند، اما البته هر نمایش دقیقاً به یک شیء متناظر است. در نتیجه، مجموعه‌ی تمام نمایش‌ها به کلاس‌های هم‌ارزی تقسیم می‌شود. وظیفه ما محاسبه تعداد اشیاء یا به طور معادل، تعداد کلاس‌های هم‌ارزی است. مثال زیر تفاوت بین شیء و نمایش را واضح‌تر می‌کند.

مثال: رنگ‌آمیزی درختان دودویی

فرض کنید مسئله زیر را داریم. باید تعداد راه‌های رنگ‌آمیزی یک درخت دودویی ریشه‌دار با $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$ نشان می‌دهیم.

بیان لم

برای فرمول‌بندی لم، به یک تعریف دیگر از جبر نیاز داریم. یک نقطه ثابت $f$ برای یک جایگشت $\pi$، عنصری است که تحت این جایگشت ناوردا است: $f \equiv f \pi$. برای مثال در مثال ما، نقاط ثابت آن توابع $f$ هستند که متناظر با رنگ‌آمیزی‌هایی هستند که با اعمال جایگشت $\pi$ بر آن‌ها تغییر نمی‌کنند (یعنی از نظر رسمی تساوی توابع، تغییری نمی‌کنند). ما $I(\pi)$ را به عنوان تعداد نقاط ثابت برای جایگشت $\pi$ نشان می‌دهیم.

سپس لم برنساید به شرح زیر است: تعداد کلاس‌های هم‌ارزی برابر است با مجموع تعداد نقاط ثابت نسبت به تمام جایگشت‌های گروه $G$، تقسیم بر اندازه این گروه:

$$|\text{کلاس‌ها}| = \frac{1}{|G|} \sum_{\pi \in G} I(\pi)$$

اگرچه استفاده از لم برنساید به خودی خود در عمل چندان راحت نیست (مشخص نیست که چگونه به سرعت مقدار $I(\pi)$ را پیدا کنیم)، اما به وضوح جوهره ریاضی را که ایده محاسبه کلاس‌های هم‌ارزی بر آن بنا شده است، آشکار می‌کند.

اثبات لم برنساید

اثبات لم برنساید که در اینجا شرح داده شده است، برای کاربردهای عملی مهم نیست، بنابراین می‌توان در اولین مطالعه از آن صرف نظر کرد.

اثبات ارائه شده در اینجا ساده‌ترین اثبات شناخته‌شده است و از نظریه گروه‌ها استفاده نمی‌کند. این اثبات توسط Kenneth P. Bogart در سال ۱۹۹۱ منتشر شد.

ما باید گزاره زیر را اثبات کنیم:

$$|\text{کلاس‌ها}| \cdot |G| = \sum_{\pi \in G} I(\pi)$$

مقدار سمت راست چیزی جز تعداد «جفت‌های ناوردا» $(f, \pi)$ نیست، یعنی جفت‌هایی که $f \pi \equiv f$ باشد. واضح است که می‌توانیم ترتیب جمع را تغییر دهیم. ما اجازه می‌دهیم که جمع روی تمام عناصر $f$ پیمایش کند و مقادیر $J(f)$ را جمع بزنیم - یعنی تعداد جایگشت‌هایی که $f$ برای آن‌ها یک نقطه ثابت است.

$$|\text{کلاس‌ها}| \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{کلاس‌ها}| \cdot |G|$ را به دست می‌آوریم (صرفاً با ضرب تعداد ستون‌ها در تعداد سطرها)، و از طرف دیگر، مجموع مقادیر $J(f)$ را برای تمام $f$ به دست می‌آوریم (این از تمام استدلال‌های قبلی نتیجه می‌شود):

$$|\text{کلاس‌ها}| \cdot |G| = \sum_{f} J(f)$$

قضیه شمارش پولیا

قضیه شمارش پولیا تعمیمی از لم برنساید است و همچنین ابزار راحت‌تری برای یافتن تعداد کلاس‌های هم‌ارزی فراهم می‌کند. لازم به ذکر است که این قضیه پیش از پولیا توسط Redfield در سال ۱۹۲۷ کشف شده بود، اما مقاله او مورد توجه ریاضی‌دانان قرار نگرفت. پولیا به طور مستقل در سال ۱۹۳۷ به نتایج مشابهی رسید و مقاله او موفقیت بیشتری کسب کرد.

در اینجا ما فقط یک حالت خاص از قضیه شمارش پولیا را مورد بحث قرار می‌دهیم که در عمل بسیار مفید خواهد بود. فرمول کلی قضیه مورد بحث قرار نخواهد گرفت.

ما $C(\pi)$ را به عنوان تعداد چرخه‌ها در جایگشت $\pi$ نشان می‌دهیم. سپس فرمول زیر (یک حالت خاص از قضیه شمارش پولیا) برقرار است:

$$|\text{کلاس‌ها}| = \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{ک.م.م}(i, n)}{i} = \frac{n}{\text{ب.م.م}(i, n)}$. بنابراین، تعداد چرخه‌ها در $\pi_i$ برابر با $\text{ب.م.م}(i, n)$ خواهد بود.

با جایگزینی این مقادیر در قضیه شمارش پولیا، به جواب می‌رسیم:

$$\frac{1}{n} \sum_{i=1}^n k^{\text{ب.م.م}(i, n)}$$

می‌توانید این فرمول را به همین شکل رها کنید، یا می‌توانید آن را حتی ساده‌تر کنید. جمع را به گونه‌ای تغییر می‌دهیم که روی تمام مقسوم‌علیه‌های $n$ پیمایش کند. در جمع اصلی، جملات معادل زیادی وجود خواهد داشت: اگر $i$ مقسوم‌علیه $n$ نباشد، پس از محاسبه $\text{ب.م.م}(i, n)$ چنین مقسوم‌علیهی یافت می‌شود. بنابراین، برای هر مقسوم‌علیه $d ~|~ n$ جمله $k^{\text{ب.م.م}(d, n)} = k^d$ چندین بار در جمع ظاهر می‌شود، یعنی پاسخ مسئله را می‌توان به صورت زیر بازنویسی کرد:

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

که در آن $C_d$ تعداد آن دسته از اعداد $i$ است که $\text{ب.م.م}(i, n) = d$ است. می‌توانیم یک عبارت صریح برای این مقدار پیدا کنیم. هر عدد $i$ از این نوع به شکل $i = d j$ با شرط $\text{ب.م.م}(j, n / d) = 1$ است (در غیر این صورت $\text{ب.م.م}(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();
}

مسائل تمرینی