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

קובץ:Ferrer partitioning diagrams.svg

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

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

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

<math>\begin{align}&p(3)=3,\quad3=1+2=1+1+1\\&p(4)=5,\quad4=1+3=2+2=1+1+2=1+1+1+1\end{align}</math>

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

<math>\begin{align}&p(100)=190569292\\&p(1000)\approx2.4\cdot10^{31}\end{align}</math>

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

<math>g(q)=\sum p(n)q^n=\prod_{m\ge1}(1-q^m)^{-1}</math>

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

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

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

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

<math>\prod_{k=1}^\infty(1-x^k)^{-1}=\prod_{k=1}^\infty\sum_{i=0}^\infty x^{ki}</math>

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

מאותו הטעם, באופן כללי הפונקציה היוצרת של מספר החלוקות בהן מופיעים רק מספרים מקבוצה <math>A\sube\N</math> הוא <math>\prod_{k\in A}(1-x^k)^{-1}</math>.

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

<math>p(n)=\sum_{k\in\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</math>

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

ראו גם

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

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

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