הצגת המקור של הדף "הלמה של ברנסייד"

ב[[תורת החבורות]], ה'''למה של ברנסייד''' (הידועה גם כ'''למת הספירה''' או כ'''משפט קושי-פרובניוס''') היא תוצאה המתקבלת מ[[פעולת חבורה|פעולה]] של [[חבורה (מבנה אלגברי)|חבורה]] על [[קבוצה (מתמטיקה)|קבוצה]]. ה[[למה (מתמטיקה)|למה]] שימושית ביותר כאשר סופרים אובייקטים מתמטיים בעלי [[סימטריה]].

הלמה נקראת על שם ה[[מתמטיקאי]] האנגלי [[ויליאם ברנסייד]], אף כי לא הוא גילה אותה לראשונה. ברנסייד פרסם את הלמה עם הוכחה בשנת [[1897]], אף כי ידוע כי הלמה הייתה מוכרת ל[[אוגוסטן לואי קושי|קושי]] עוד ב-[[1845]]. למעשה, מקובל להניח כי הלמה הייתה ידועה כל כך, עד כי ברנסייד לא טרח לציין כי קושי הוכיח אותה לפניו.

תוצאה של הלמה (שנובעת מיידית מניסוחה) היא כי לתמורות על מספר סופי של איברים יש בממוצע [[נקודת שבת]] אחת.

==ניסוח הלמה==
תהי <math>G</math> חבורה סופית הפועלת על קבוצה <math>X</math>. נסמן <math>\text{Fix}(g)=\{x\in X:g(x)=x\}</math>, כלומר קבוצת האיברים ש-<math>g</math> משאיר במקום. אזי מספר ה[[פעולת חבורה#מסלולים ומייצבים|מסלולים]] של הפעולה הוא
<math display=block>N=\frac{1}{|G|}\sum_{g\,\in\,G}|\text{Fix}(g)|</math>
כלומר מספר המסלולים הוא [[ממוצע]] גודלי ה-<math>\text{Fix}</math>.

==הוכחה==
כאמור, נסתכל על חבורה <math>G</math> הפועלת על קבוצה <math>X</math>. נרצה לחלק את <math>X</math> למסלולים (זוהי [[חלוקה (תורת הקבוצות)|חלוקה]] לקבוצות זרות), ולבדוק כמה תורם כל מסלול לסכימה <math>\sum_{g\,\in\,G}|\text{Fix}(g)|</math>.

נסתכל על <math>x\in X</math> כלשהו. נסמן את גודל המייצב שלו <math>m=|\text{stab}(x)|</math>, ונסתכל על כל הקבוצות <math>\text{Fix}(g)</math>. לפי הגדרה, <math>x</math> מופיע בדיוק ב-<math>m</math> קבוצות כאלה. נשים לב גם כי לכל
<math>y</math> במסלול של <math>x</math> מתקיים <math>|\text{stab}(x)|=|\text{stab}(y)|</math>. כיוון שגודל המסלול נתון על ידי <math>|\text{Orb}(x)|=[G:\text{stab}(x)]=\frac{|G|}{m}</math>, ישנם בדיוק <math>\frac{|G|}{m}</math> איברים במסלול של <math>x</math>, שכל אחד מהם נמצא ב-<math>m</math> קבוצות <math>\text{Fix}(g)</math>. לכן, בסכימה <math>\sum_{g\,\in\,G}|\text{Fix}(g)|</math> כל מסלול תורם בדיוק <math>|G|</math>. לכן מתקבל <math>N\cdot|G|=\sum_{g\,\in\,G}|\text{Fix}(g)|</math>, כלומר <math>N=\frac{1}{|G|}\sum_{g\,\in\,G}|\text{Fix}(g)|</math>.

==דוגמה==
[[קובץ:Samp id.png|שמאל|ממוזער|200 פיקסלים|כרטיס לדוגמה. כרטיס זה לא ישתנה אם [[שיקוף (מתמטיקה)|נשקף]] אותו סביב הציר האנכי, אך כן ישתנה אם נסובב אותו, או אם נשקף אותו דרך כל ציר אחר.]]
נניח כי אנו רוצים ליצור תעודות זהות מכרטיסי פלסטיק בני תשע משבצות, שבכל אחת מהן ניתן לנקב (או לא לנקב) חור. אנו רוצים לדעת כמה כרטיסים שונים ניתן ליצור, כאשר תבניות שאפשר להגיע אליהן באמצעות סיבובים או [[שיקוף (מתמטיקה)|שיקופים]] יוצרות למעשה את אותו כרטיס.

הסיבובים והשיקופים יוצרים את [[חבורה דיהדרלית|החבורה הדיהדרלית]] <math>D_4</math>, ולכן בוחנים את פעולת החבורה הזו על קבוצת כל תבניות-החורים האפשריות. יש <math>2^{3\cdot3}=512</math> תבניות כאלה, ושתי תבניות יוצרות כרטיסים שונים רק אם הן לא שייכות לאותו מסלול. המטרה היא, אם כך, לספור את המסלולים בקבוצת התבניות תחת פעולת החבורה.

החבורה <math>D_4</math> מורכבת מ-8 איברים:
*2 שיקופים סביב אלכסונים – נבדוק מה מספר האפשרויות לבניית כרטיס שלא ישתנה תחת שיקוף סביב האלכסון. לכל משבצת מחוץ לאלכסון יש משבצת מתאימה מן העבר השני של האלכסון, והחורים בשתיהן צריכים להתאים זה לזה. כלומר, אף על פי שישנם 6 משבצות מחוץ לציר השיקוף, יש רק 3 בחירות בלתי תלויות, שהן <math>2^3</math> אפשרויות. בנוסף, על ציר השיקוף עצמו ניתן לבחור חורים כרצוננו, ואלו עוד <math>2^3</math> אפשרויות. בסך הכל, קיימות <math>2^3\cdot2^3=2^6=64</math> תבניות שאינן משתנות תחת שיקוף סביב אלכסון מסוים.
*2 שיקופים דרך אמצעי צלעות – מאותה סיבה, יש <math>2^6=64</math> תבניות שאינן משתנות תחת שיקוף דרך אמצע צלע.
*2 סיבובים של 90° – כאן יש רק 3 בחירות בלתי תלויות, ולכן <math>2^3=8</math> תבניות שאינן משתנות תחת סיבוב של 90°.
*סיבוב של 180° – כאן יש <math>2^5=32</math> תבניות שאינן משתנות תחת סיבוב של 180°.
*הזהות – תחת הזהות, כל הכרטיסים נשארים אותו דבר, כלומר - <math>\ 2^9=512</math> כרטיסים.
סך הכול קיבלנו: <math>N=\frac{1}{8}(\underbrace{2\cdot64}_{\rm diagonal}+\underbrace{2\cdot64}_{\rm middle}+\underbrace{2\cdot8}_{90^\circ}+\underbrace{1\cdot32}_{180^\circ}+\underbrace{1\cdot512}_{\rm Id})=102</math>, כלומר 102 כרטיסים שונים.

==קישורים חיצוניים==
*[http://planetmath.org/encyclopedia/CountingTheorem.html הלמה של ברנסייד ב planetmath]
* {{MathWorld}}

[[קטגוריה:משפטים בתורת החבורות|ברנסייד]]
[[קטגוריה:למות|ברנסייד]]