لم برنساید

در مسائل ترکیبیاتی به وفور مواردی یافت می شوند که علاقه مند به شمارش تعداد حالت های ممکن باشیم. این در حالتی است که عموماً بعضی حالت های در نظر گرفته شده با یکدیگر هم ارز هستند و با اعمال تبدیل های هم ریخت می توان آن ها را یکی در نظر گرفت. در این جا ساختار جبری گروه با ویژگی های مطلوب بسیار مورد توجه می باشد. از این رو داشتن اطلاعات اولیه راجع به این ساختار جبری توصیه می شود.
این لم روشی برای شمارش افرازهایی است که در یک مجموعه به وسیله یک گروه از تبدیلات ایجاد می شود. این فرمول را ویلیام برنساید در سال ۱۸۹۷ در کتاب خود در مورد گروه های متناهی بیان کرد و آن را به فردیناند جورج فروبینیوس نسبت داد. اما پیش از آن نیز کوشی در سال ۱۸۴۵ مسائل مشابهی را از این روش حل کرده بود. اما به هر حال ویلیام برنساید برای اولین بار به شکل یک لم و با اثبات آن را مطرح کرد و کمک شایان توجهی در پیشروی نظریه گروه ها کرد.
مجموعه ای از اعضا مانند 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−1 ∈ G پس می توان گفت ( Ci = f−1 ( 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 است و آن را به رده های هم ارز افراز می کند. در نتیجه به راحتی قابل ملاحظه است که: