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

מתוך ויקיפדיה, האנציקלופדיה החופשית

יש לך הודעות חדשות (השווה לגרסה הקודמת).

בקומבינטוריקה ותורת המספרים, חלוקה של מספר טבעי היא הצגה שלו כסכום של חלקים, כמו $\ 5=3+1+1$ . שתי חלוקות שההבדל היחיד ביניהן הוא סדר הרכיבים, נחשבות לאותה החלוקה. החלוקות מופיעות בתחומים שונים בקומבינטוריקה, כגון פולינומים סימטריים ותורת ההצגות של החבורה הסימטרית.

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

מספר החלוקות השונות של n נקרא פונקציית החלוקה של n, ומקובל לסמנו ב- $\ p(n)$ . לדוגמה, החלוקות השונות של 3 הן $\ 3=2+1=1+1+1$ , ושל 4 הן $\ 4=3+1=2+2=2+1+1=1+1+1+1$ . מכיוון של- 4 יש חמש חלוקות, $\ p(4)=5$ . עבור הערכים $\ n=1,2,...,10$ , פונקציית החלוקה מקבלת את הערכים הבאים: $\ p(n)=1,2,3,5,7,11,15,22,30,42$ . ערכי הפונקציה גדלים במהירות: $\ p(100)=190569292$ , ואילו $\ p(1000)\approx 2.4\cdot 10^{31}$ . ג. ה. הארדי וראמאנוג'ן הוכיחו ב- 1918 את הנוסחה האסימפטוטית $p(n) \sim \frac{1}{4n\sqrt{3}} e^{\pi \sqrt{2n/3}}$ .

את פונקציית החלוקה חקר לראשונה לאונרד אוילר, שמצא עבור הפונקציה היוצרת שלה פירוק למכפלה אינסופית $\sum_{n=0}^\infty p(n)x^n = \prod_{k=1}^\infty \left(\frac {1}{1-x^k} \right).$ , צעד שבמידת מה נחשב לראשיתה של תורת המספרים האנליטית.

בין התכונות המפתיעות של פונקציות החלוקה אפשר למנות את הקונגרואנציות שגילה ראמאנוג'ן: לכל n, $\ p(5n+4)$ מתחלק ב- 5. באופן דומה $\ p(7n+6)$ מתחלק תמיד ב- 7, ו- $\ p(11n+6)$ מתחלק ב- 11. תוצאות אלה קשורות במספרים מצולעים. מאוחר יותר התגלה גם שהמספרים $\ p(17303n+237)$ מתחלקים ב- 13, ועדיין לא ידועה תוצאה דומה עבור ראשוניים אחרים.