لم برنساید
در مسائل ترکیبیاتی به وفور مواردی یافت میشوند که علاقهمند به شمارش تعداد حالتهای ممکن باشیم. این در حالتی است که عموماً بعضی حالتهای در نظر گرفته شده با یکدیگر هم ارز هستند و با اعمال تبدیلهای هم ریخت میتوان آنها را یکی در نظر گرفت. در این جا ساختار جبری گروه با ویژگیهای مطلوب بسیار مورد توجه میباشد. از این رو داشتن اطلاعات اولیه راجع به این ساختار جبری توصیه میشود.
تاریخچه
این لم روشی برای شمارش افرازهایی است که در یک مجموعه به وسیله یک گروه از تبدیلات ایجاد میشود. این فرمول را ویلیام برنساید در سال ۱۸۹۷ در کتاب خود در مورد گروههای متناهی بیان کرد و آن را به فردیناند جورج فروبینیوس نسبت داد. اما پیش از آن نیز کوشی در سال ۱۸۴۵ مسائل مشابهی را از این روش حل کرده بود. اما به هر حال ویلیام برنساید برای اولین بار به شکل یک لم و با اثبات آن را مطرح کرد و کمک شایان توجهی در پیشروی نظریه گروهها کرد.
شمارش و همارزی
مجموعهای از اعضا مانند S را در نظر میگیریم. گروه G شامل مجموعهای از توابع با دامنه S و برد S و عمل ترکیب دو تابع را در نظر میگیریم.
در صورت اعمال به دستههای همارزی افراز میشود به نحوی که در هر یک از این دستهها، هر عضو تحت عملی در G به سایر اعضای دسته قابل تبدیل است؛ و در عوض به اعضای سایر دستهها قابل تبدیل نیست.
رابطه R را به نحو زیر تعریف میکنیم:
برای o1≤i,j≤ |S|، Ci,Cj ∈ S داریم Ci R Cj اگر و تنها اگر
Cj = G(Ci)
رابطه R با کیفیت بالا یک رابطه همارزی است. زیرا:
- (ویژگی بازتابی): برای هر Ci ∈ S نتیجه میشود که Ci R Ci زیرا G شامل تابع همانی است. (Ci = I(Ci
- (ویژگی تقارنی):اگر برای Ci,Cj ∈ S داشته باشیم Ci R Cj پس یک f ∈ G وجود دارد به نحوی که (Cj = f(Ci. از آنجا که G گروه است و در نتیجه شامل تابع معکوس f است. f ∈ G پس میتوان گفت (Ci = f(Cj و داریم: Cj R Ci.
- (ویژگی ترایایی):فرض میکنیم Ci,Cj,Ck ∈ S و Ci R Cj و Cj R Ck در این صورت به ازای توابع f و g متعلق به G داریم (Cj = g(Ci)، Ck = g(Cj. با توجه به این که G گروه است و در نتیجه بسته است میتوان گفت که h = fοg ∈ G در نتیجه (Ck = h(Ci پس Ci R Ck که این مؤید خصلت ترایایی میباشد.
پس R یک رابطه همارزی روی S است و آن را به ردههای هم ارز افراز میکند. در نتیجه به راحتی قابل ملاحظه است که:
برای درک بهتر موضوع توجه به مثال فوق ضروری است:
مربعی که هر یک از رئوس آن میتواند یکی از دو رنگ سیاه یا سفید را بپذیرد در نظر میگیریم. هر یک از حالتهای ممکن را یکی از اعضای مجموعه S در نظر میگیریم. به این ترتیب S دارای ۱۶ = 4 عضو میباشد.
حال مجموعه حرکتهای سلب دورانی تقارنی را به عنوان مجموعهای از توابع با دامنه و برد S در نظر میگیریم. این مجموعه با عنوان G در شکل نمایش داده شده است و شامل اعضای زیر است.
- π0: دوران به اندازه ۳۶۰ درجه (1234) = π0 (در هر ردیف، رأس بالا به رأس پایین منتقل میشود. ۱ به ۱ و ۲ به ۲ و …)
- π1: دوران به اندازه ۹۰ درجه (2341) = π1
- π2: دوران به اندازه ۱۸۰ درجه (3412) = π2
- π3: دوران به اندازه ۲۷۰ درجه (4123) = π3
- r1: تقارن نسبت به محور افقی (4321) = r1
- r2: تقارن نسبت به محور عمودی (2143) = r2
- r3: تقارن نسبت به قطر اصلی (3214) = r3
- r4: تقارن نسبت به قطر فرعی (1432) = r4
هر یک از این تبدیلها را میتوان به صورت حاصل ضرب دورهای مجزا نوشت که در هر یک از این دورها عناصر به صورت گردشی جابجا میشوند، برای مثال:
r2 = (2143) = 0(12). (۳۴)
π2 = (3412) = 0(1234)
در حالت کلی مشاهده میشود که این گروه G آبلی نیست.
در صورتی که تبدیل f بر مجموعه S اعمال شود، f را تشکیل میدهد.
در همین چارچوب به صورت حاصل ضرب دورهای مجزا میتوان نوشت:
π1 = (C1)
(C2C3C4C5)
(C6C7C8C9)
(C10C11)
(C12C13C14C15)
(C16)0
r3 = (C1)
(C2)(C3C5)(C4)
(C6C7)(C8C9)
(C10)(C11)
(C12C14)(C13C15)
(C16)0
همانطور که مشاهده میشود، برای این دو نمونه و نیز سایر تبدیلها، دوری وجود ندارد که بین دو دسته همارزی عضو مشترک داشته باشد.
در حالت کلی، S مجموعه پیکر بندیهاست و G تبدیلهایی که روی S عمل میکنند. رابطه R بر S به وسیله xRy تعریف شود، در صورتی که برای πهایی متلق به G باشد، π = y، آن گاه R یک رابطه همارزی است.
لم برنساید
تابع مولد دومتغیره زیر جهت شمارش تعداد پیکر بندیهای نا هم ارز S برای حالت خاص بحث شده است.
f(r,w) = r + rw + 2rw + rw + w
که ضریب هر جمله تعداد پیکر بندی متمایزی که با i رنگ w و n-i رنگ r میتوان درست کرد، میباشد. به این تابع فهرست الگویی میگویند.
در لم (قضیه) ای موسوم به برنساید رابطهای برای شمارش تعداد این پیکر بندیهای نا هم ارز ارائه شده است:
که در آن (π)ψ تعدادی از پیکر بندیهای S است که به وسیله π تثبیت میشوند.
مثال کاربردی
به چند طریق میتوان رئوس مربعی را رنگ آمیزی کرد به نحوی که امکان گردش در فضا وجود داشته باشد؟
برای حل از لم برنساید استفاده میکنیم:
- زیرا تبدیل همانی تمام پیکربندیهای S را ثابت نگه میدارد.
- تنهای پیکربندیهایی را ثابت نگه میدارند که تمام رئوسشان رنگ یکسانی داشته باشند.
- برای دو رأس در انتخاب رنگ آزادی عمل داریم اما رنگ رئوس روبروی آنها باتوجه به رنگ این دو رأس تعیین میشود.
- این بار هم برای دو رأس در انتخاب رنگ آزادی عمل داریم اما رنگ رئوس مجاور آنها با توجه به رنگ این دو رأس تعیین میشود.
- در این تبدیل برای سه رأس آزادی انتخاب داریم. زیرا دو رأس اصلاً تغییر مکان نمیدهند و دو رأس دیگر که روبرو هستند همرنگ خواهند بود.
بنا براین:
قضیه برنساید
بعضاً از لم برنساید با عنوان قضیه برنساید یاد میشود.
در صورتی که قضیهای دیگر در نظریه گروهها وجود دارد که موسوم به قضیه برنساید است.
این قضیه بیان میکند که هر گروه که مرتبه آن به شکل
نخستین نتیجهای که از این قضیه گرفته میشود این است که اگر یک گروه غیر آبلی ساده متناهی داشته باشیم، از مرتبهای تجذیه پذیر به سه عامل اول خواهد بود.
شاخص دور
روش شمارش پولیا
منابع
- رالف گریمالدی (۱۳۸۵)، ریاضیات گسسته و ترکیبیاتی از دیدگاه کاربردی حلد دوم، ترجمهٔ محمد علی عمیدی، تهران: مرکز نشر دانشگاهی، شابک ۹۶۴-۰۱-۰۸۹۰-۱