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

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

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

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

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

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

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

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

$g(q)=\sum p(n)q^n=\prod _{m\ge 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}^{\mathrm{\infty }}p(n)x^n=\prod _{k=1}^{\mathrm{\infty }}(1-x^k{)}^{-1}$, צעד שבמידת מה נחשב לראשיתה של תורת המספרים האנליטית.

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

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

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

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

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

$p(n)=\sum _{k\in \mathbb{\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