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

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

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

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

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

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

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

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

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

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

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

${\displaystyle 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)+\ldots }$

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

ראו גם

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

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

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

הערות שוליים