הלמה של ברנסייד

הלמה של ברנסייד היא משפט בתורת החבורות שעוזר לספור אובייקטים עם סימטריות. היא אומרת שאפשר למצוא את מספר המסלולים (הקבוצות של אובייקטים שניתן להעביר זה לזה בעזרת הסימטריות) על ידי ממוצע של גודל קבוצות ה-Fix.

יהי G חבורה סופית הפועלת על קבוצה X. נגדיר Fix(g) = {x in X : g(x)=x}, כלומר האיברים שפעולה g משאירה ללא שינוי. אזי מספר המסלולים N נתון על ידי הנוסחה
N = (1/|G|) * sum_{g in G} |Fix(g)|
כלומר N שווה לממוצע על כל איברי החבורה של מספר האיברים שכל איבר משאיר במקום.

נבנה חלוקה של X למסלולים תחת הפעולה. עבור איבר x ב-X נסתכל על המייצב שלו stab(x), קבוצת הפעולות שמשאירות את x במקום. אם גודל המייצב הוא m אז x נמצא בדיוק ב-m קבוצות Fix(g).
במסלול של x יש |G|/m איברים. לכל איבר במסלול אותו מספר של פעולות שמשאירות אותו במקום. לכן סכימת כל |Fix(g)| על כל g תיתן בדיוק |G| לכל מסלול. חיבור על כל המסלולים נותן N*|G| = sum_{g in G} |Fix(g)|, וממנו מקבלים את הנוסחה לעיל.

נבחין בתבניות חורים בכרטיס 3×3. יש 2^{9}=512 תבניות כולן. החבורה של סיבובים ושיקופים של הריבוע היא D_4 עם 8 איברים. מחשבים עבור כל פעולה כמה תבניות היא משאירה במקום ואז ממוצעים. חישוב זה נותן N = 102 תבניות שונות תחת כל הסימטריות.

הלמה של ברנסייד עוזרת לספור דברים שיש להם סימטריות.

אם יש קבוצה של פעולות (חבורה) שעושות סיבובים ושיקופים על אובייקטים, אז מספר הדפוסים השונים שווים לממוצע של כמה איברים כל פעולה משאירה במקום. Fix(g) הם האיברים שפעולה g לא משנה.

לוקחים כל קבוצה של פריטים שניתן להמיר ביניהן בעזרת הסימטריות. כל פריט במסלול נשאר במקום על ידי אותה כמות פעולות. לכן כל מסלול תורם את אותו המספר לסכום, וכשהם ממוצעים מקבלים את מספר המסלולים.

יש כרטיס 3×3 שבו כל משבצת יכולה להיות מנוקבת או לא. יש 512 אפשרויות לכלל. אם מחשבים כמה דפוסים נשארים זהים אחרי סיבובים ושיקופים, מקבלים בסוף 102 כרטיסים שונים.