פונקציית החלוקה (תורת המספרים)

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

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

מספר החלוקות השונות של n נקרא פונקציית החלוקה של n, ומקובל לסמנו ב- . לדוגמה, החלוקות השונות של 3 הן , ושל 4 הן . מכיוון של- 4 יש חמש חלוקות, . עבור הערכים , פונקציית החלוקה מקבלת את הערכים הבאים: . ערכי הפונקציה גדלים במהירות: , ואילו . ג. ה. הארדי וראמאנוג'ן הוכיחו ב- 1917 [1] את הנוסחה האסימפטוטית . לצורך כך השתמשו הארדי וראמאנוג'ן בתאוריה של תבניות מודולריות, שהם היו ממייסדיה, כשהמציאו את "שיטת המעגל" לצורך הערכת המקדמים של פונקציית תטא המתאימה לפונקציית החלוקה, .

בין התכונות המפתיעות של פונקציות החלוקה אפשר למנות את הקונגרואנציות שגילה ראמאנוג'ן: לכל n, מתחלק ב-5. באופן דומה מתחלק תמיד ב-7, ו- מתחלק ב-11. תוצאות אלה קשורות במספרים מצולעים. מאוחר יותר התגלה גם שהמספרים מתחלקים ב-13. בשנת 2000 הוכיח קן אונו שזהויות כאלו קיימות לכל מספר ראשוני ומספר שנים לאחר מכן תוצאה זו הורחבה לכל מספר שלם שזר ל-6.

פונקציה יוצרת[עריכת קוד מקור | עריכה]

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

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

מספר הפעמים שהאיבר יתקבל בפתיחת המכפלה באגף ימין הוא בדיוק מכיוון ש-i קובע באופן יחיד את מספר הפעמים שהמספר k מופיע בחלוקה נתונה.

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

ממשפט המספרים המחומשים נובעת באמצעות מניפולציה על הפונקציה היוצרת נוסחת הנסיגה:

כאשר הוא המספר המחומש המוכלל ה-n-י. זהו סכום סופי, מכיוון ש- (סכום ריק) ולכל k שלילי .

דיאגרמות יאנג[עריכת קוד מקור | עריכה]

דיאגרמת היאנג התואמת לחלוקה 5+4+1

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

משפט: מספר החלוקות של n בעלות מרכיב מקסימלי לא גדול מm שווה למספר החלוקות בעלות מספר מרכיבים לא גדול מm.

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

דיאגרמת היאנג התואמת לחלוקה 3+2+2+2+1. החלוקה הצמודה לחלוקה 5+4+1.

ראו גם[עריכת קוד מקור | עריכה]

קישורים חיצוניים[עריכת קוד מקור | עריכה]

ויקישיתוף מדיה וקבצים בנושא פונקציית החלוקה בוויקישיתוף

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ Hardy, G. H.; Ramanujan, S., Asymptotic formulae in combinatory analysis., J. Lond. M. S. Proc. (2) 17, 75-115 (1917); הופיע גם ב- Hardy, G. H. and Ramanujan, S. "Asymptotic Formulae in Combinatory Analysis." Proc. London Math. Soc. 17, 75-115, 1918