משפט החלוקה של אוילר

משפט החלוקה של אוילר הוא משפט הקובע שמספר החלוקות של מספר לחלקים שונים זה מזה שווה למספר החלוקות של המספר לחלקים אי-זוגיים (לא בהכרח שונים).

את המשפט הוכיח לאונרד אוילר ב-1748 באמצעות פונקציות יוצרות, שיטה חדשנית בזמנו.

רקע

חלוקה של מספר טבעי היא הצגה שלו כסכום של מספרים טבעיים. למשל 1+2+2, 2+3, 5 הם דוגמאות לחלוקות של 5. שתי חלוקות הנבדלות רק בסדר המחוברים נחשבות לאותה החלוקה. חלוקה נבדלת היא חלוקה שבה כל החלקים שונים זה מזה. למשל 1+2+4 היא חלוקה נבדלת של 7, ואילו 1+3+3 אינה כזו כי 3 מופיע פעמיים. חלוקה אי-זוגית היא חלוקה שכל חלקיה הם מספרים אי-זוגיים, למשל 1+3+3 היא חלוקה אי-זוגית בעוד ש-1+2+4 אינה כזו.

את מספר החלוקות הנבדלות השונות של מספר $n$ נסמן $D(n)$. את מספר החלוקות האי-זוגיות של מספר $n$ נסמן $O(n)$. משפט החלוקה של אוילר קובע ש-$D(n)=O(n)$ לכל n טבעי.

הפונקציה היוצרת של $D(n)$ היא טור החזקות $\sum _{n=0}^{\infty }D(n)x^{n}$. אנו מתעניינים בפונקציה היוצרת רק כאובייקט אלגברי המאגד את המידע על $D(n)$ בצורה הנוחה לנו, ואין לנו עניין בשאלת ההתכנסות של הטור. באופן דומה $\sum _{n=0}^{\infty }O(n)x^{n}$ היא הפונקציה היוצרת של $O(n)$.

ההוכחה של אוילר

ההוכחה של אוילר עושה שימוש במניפולציות אלגבריות כדי להראות שהפונקציות היוצרות של $D(n)$ ושל $O(n)$ זהות זו לזו, ולכן מספר החלוקות הנבדלות ומספר החלוקות האי-זוגיות שווים זה לזה. ייחודה של ההוכחה בכך שהיא מוכיחה תוצאה בקומבינטוריקה ובתורת המספרים ללא שימוש בכלים האלמנטריים מתורות אלו.

תכונה של הפונקציה היוצרת של $D(n)$, היא שניתן להציג אותה כמכפלה אינסופית, כך שאם נפתח סוגריים במכפלה נקבל את הפונקציה היוצרת:

$\sum _{n=0}^{\infty }D(n)x^{n}=\prod _{n=1}^{\infty }(1+x^{n})=(1+x)(1+x^{2})(1+x^{3})(1+x^{4})(1+x^{5})\cdots$

בפתיחת הסוגרים נקבל פעם אחת בדיוק כל מכפלה מהצורה $x^{k_{1}}x^{k_{2}}\cdots x^{k_{r}}$, אותה ניתן לבטא לפי חוקי החזקות כך: $x^{k_{1}}x^{k_{2}}\cdots x^{k_{r}}=x^{k_{1}+k_{2}+\ldots +k_{r}}$.

ניתן לשים לב, שלפני חיבור איברי המעריך התוצאה שתתקבל היא של מעריכים שכולם שונים זה מזה, ולאחר חיבור איברי המעריך נקבל כל מעריך מספר פעמים זהה לערכה של החלוקה הנבדלת שלו. למשל $x^{5}$ יתקבל 3 פעמים מפתיחת הסוגריים: $x^{5},xx^{4},x^{2}x^{3}$, פעם אחת לכל חלוקה נבדלת, ולכן המקדם שלו בסכום שיתקבל הוא $D(5)=3$.

באופן דומה גם את הפונקציה היוצרת של $O(n)$ ניתן להציג כמכפלה אינסופית (שכל גורם בה הוא סכום אינסופי):

$\sum _{n=0}^{\infty }O(n)x^{n}=\prod _{n=0}^{\infty }\sum _{k=0}^{\infty }x^{(2n+1)k}=(1+x+x^{1+1}+x^{1+1+1}+\ldots )(1+x^{3}+x^{3+3}+x^{3+3+3}+\ldots )(1+x^{5}+x^{5+5}+x^{5+5+5}+\ldots )\cdots$

במקרה הזה כאשר נפתח סוגריים נקבל פעם אחת בדיוק כל מחובר מהצורה $x^{k_{1}+k_{2}+\ldots +k_{r}}$, כאשר המעריכים כולם אי-זוגיים (ולא בהכרח שונים). למשל $x^{5}$ יתקבל 3 פעמים: $x^{5},x^{1+1}x^{3},x^{1+1+1+1+1}$, פעם אחת לכל חלוקה אי-זוגית, ולכן המקדם שלו הוא $O(5)=3$.

נשים לב כי הסכום $1+x^{m}+x^{m+m}+x^{m+m+m}+\ldots$ הוא למעשה סכום של סדרה הנדסית (עם מנה $x^{m}$) ולכן לפי הנוסחה לסכום סדרה הנדסית הוא שווה ל-${\frac {1}{1-x^{m}}}$. לכן ניתן לכתוב:

$\sum _{n=0}^{\infty }O(n)x^{n}=\prod _{n=0}^{\infty }{\frac {1}{1-x^{2n+1}}}={\frac {1}{1-x}}\cdot {\frac {1}{1-x^{3}}}\cdot {\frac {1}{1-x^{5}}}\cdots$.

ביטאנו כל אחת מן הפונקציה היוצרות כמכפלות אינסופיות, וכעת נותר להראות שהמכפלות שוות. הדבר נעשה במניפולציה אלגברית פשוטה. מהזהות הידועה של הפרש ריבועים $x^{2n}-1=(x^{n}-1)(x^{n}+1)$ מקבלים $x^{n}+1={\tfrac {x^{2n}-1}{x^{n}-1}}$, ולכן:

$\sum _{n=0}^{\infty }D(n)x^{n}=(1+x)(1+x^{2})(1+x^{3})(1+x^{4})(1+x^{5})\cdots ={\frac {x^{2}-1}{x-1}}\cdot {\frac {x^{4}-1}{x^{2}-1}}\cdot {\frac {x^{6}-1}{x^{3}-1}}\cdot {\frac {x^{8}-1}{x^{4}-1}}\cdot {\frac {x^{10}-1}{x^{5}-1}}\cdots =$

כל אחד מהמונים מצטמצם עם אחד מהמכנים שאחריו ונשארים רק המכנים האי-זוגיים:

$={\frac {1}{x-1}}\cdot {\frac {1}{x^{3}-1}}\cdot {\frac {1}{x^{5}-1}}\cdots =\sum _{n=0}^{\infty }O(n)x^{n}$

קיבלנו $\sum _{n=0}^{\infty }D(n)x^{n}=\sum _{n=0}^{\infty }O(n)x^{n}$, ולכן $D(n)=O(n)$ כפי שרצינו להוכיח.

הוכחה אלמנטרית

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

נניח $n=\sum _{i=0}^{r}a_{i}\cdot (2i+1)=a_{0}+a_{1}\cdot 3+a_{2}\cdot 5+\ldots +a_{r}\cdot (2r+1)$ היא חלוקה אי-זוגית של המספר n ($a_{i}$ הוא מספר שלם אי-שלילי ששווה למספר העותקים בסכום של המחובר $2i+1$). נציג כל $a_{i}$ בבסיס בינארי, כלומר כסכום של חזקות שונות של 2: $a_{i}=\sum _{j=0}^{l}2^{b_{ij}}$. נקבל חלוקה נבדלת של n:

$n=\sum _{i=0}^{r}a_{i}\cdot (2i+1)=\sum _{i=0}^{r}\sum _{j=0}^{l}2^{b_{ij}}(2i+1)$

זוהי חלוקה נבדלת כי כל שני איברים בה נבדלים בחזקה המקסימלית של 2 המחלקת אותם או במספר האי-זוגי המקסימלי שמחלק אותם.

גם הכיוון ההפוך מוגדר היטב. לכל חלוקה נבדלת נקבץ יחדיו את המחוברים שיש להם אותו מחלק אי-זוגי מקסימלי. בגלל שהחלוקה נבדלת הם יבדלו בחזקה המקסימלית של 2 המחלקת אותם. לכן סכום החזקות של 2 קובעות הצגה בינארית של מקדם $a_{i}$ באופן יחיד.

הכללה

המשפט הוא מקרה פרטי של משפט גליישר , שקובע כי עבור שלם d, מספר החלוקות לחלקים שאינם מתחלקים ב-d, שווה למספר החלוקות המקיימות ששום חלק לא חוזר d פעמים או יותר (במילים אחרות, כל חלק חוזר לכל היותר d-1 פעמים). משפט החלוקה של אוילר הוא משפט גליישר עבור d=2.

ראו גם

• משפט המספרים המחומשים

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

• A theorem by Euler on partitions