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

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

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

מספר החלוקות השונות של $ n $ נקרא פונקציית החלוקה של $ n $, ומקובל לסמנו $ p(n) $. לדוגמה:

$ {\begin{aligned}&p(3)=3,\quad 3=1+2=1+1+1\\&p(4)=5,\quad 4=1+3=2+2=1+1+2=1+1+1+1\end{aligned}} $

עבור הערכים $ n=1,2,\ldots ,10 $ פונקציית החלוקה מקבלת את הערכים $ p(n)=1,2,3,5,7,11,15,22,30,42 $. ערכי הפונקציה גדלים במהירות, לדוגמה:

$ {\begin{aligned}&p(100)=190569292\\&p(1000)\approx 2.4\cdot 10^{31}\end{aligned}} $

ג. ה. הארדי ורמנוג'אן הוכיחו ב-1917 את הנוסחה האסימפטוטית $ p(n)\sim {\frac {e^{\pi {\sqrt {2n/3}}}}{4{\sqrt {3}}n}} $. לצורך כך הם השתמשו בתאוריה של תבניות מודולריות, שהם היו ממייסדיה, כשהמציאו את "שיטת המעגל" לצורך הערכת המקדמים של פונקציית תטא המתאימה לפונקציית החלוקה

$ g(q)=\sum p(n)q^{n}=\prod _{m\geq 1}(1-q^{m})^{-1} $

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

פונקציה יוצרת

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

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

$ \prod _{k=1}^{\infty }(1-x^{k})^{-1}=\prod _{k=1}^{\infty }\sum _{i=0}^{\infty }x^{ki} $

מספר הפעמים שהאיבר $ x^{n} $ יתקבל בפתיחת המכפלה באגף ימין הוא בדיוק $ p(n) $ מכיוון ש-i קובע באופן יחיד את מספר הפעמים שהמספר $ k $ מופיע בחלוקה נתונה.

מאותו הטעם, באופן כללי הפונקציה היוצרת של מספר החלוקות בהן מופיעים רק מספרים מקבוצה $ A\subseteq \mathbb {N} $ הוא $ \prod _{k\in A}(1-x^{k})^{-1} $.

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

$ p(n)=\sum _{k\in \mathbb {Z} \setminus \{0\}}(-1)^{k-1}\cdot p(n-p_{k})=p(n-1)+p(n-2)-p(n-5)-p(n-7)+p(n-12)+\cdots $

כאשר $ p_{n}={\frac {n(3n-1)}{2}} $ הוא המספר המחומש המוכלל ה-$ n $-י. זהו סכום סופי, מכיוון ש-$ p(0)=1 $ (סכום ריק) ולכל $ k<0 $ מתקיים $ p(k)=0 $.

ראו גם

• משפט החלוקה של אוילר
• מספרי בל – ספירת חלוקות בהן זהות האיברים בכל חלק חשובה

קישורים חיצוניים

• פונקציית החלוקה, באתר MathWorld (באנגלית)
• גדי אלכסנדרוביץ', חלוקות וההשערה של רמנוג'אן, באתר "לא מדויק", 29 ביוני 2011

הערות שוליים

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

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