חלוקה (קומבינטוריקה)

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

בתורת המספרים ובקומבינטוריקה, חלוקה של מספר שלם חיובי $n$, היא דרך לכתוב את $n$ כסכום של מספרים שלמים חיוביים. שני סכומים הנבדלים רק בסדר הסכומים שלהם נחשבים לאותה חלוקה. לדוגמה, ניתן לחלק את 4 בחמש דרכים שונות:

$4$

$1+3$

$2+2$

${\textstyle 2+1+1}$

$1+1+1+1$

החלוקה $1+3$ היא אותה חלוקה כמו $3+1$, והחלוקות $1+1+2$ ו- $1+2+1$ הן אותן חלוקות כמו $2+1+1$.

חלוקות מתאימות לאובייקטים חשובים רבים במתמטיקה. בפרט, יש התאמה חד-חד-ערכית ועל בין:

1. חלוקות בגודל $n$,
2. דיאגרמות יאנג בגודל $n$,
3. מחלקות צמידות של החבורה הסימטרית $S_{n}$,
4. הצגות אי-פריקות של $S_{n}$ (עד כדי איזומורפיזם),
5. מטריצות נילפוטנטיות (עד כדי הצמדה).

את החלוקות בגודל $n$ סופרת פונקציית החלוקה.

דיאגרמות יאנג

דיאגרמת היאנג התואמת לחלוקה 5+4+1

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

משפט: מספר החלוקות של n בעלות מרכיב מקסימלי לא גדול מm שווה למספר החלוקות בעלות מספר מרכיבים לא גדול מm.

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

דיאגרמת היאנג התואמת לחלוקה 3+2+2+2+1. החלוקה הצמודה לחלוקה 5+4+1.

חלוקות לא רצופות

מציאת מספר בל

מספר החלוקות האפשריות של קבוצה בגודל n, נקרא מספר בל ה-$n$-י על שם המתמטיקאי האמריקאי אריק טמפל בל, ומסומן $\ B_{n}$ (אין קשר ישיר למספרי ברנולי המסומנים באותו אופן, ושכיחים יותר בספרות המתמטית).

מספרי בל מקיימים את הנוסחה הרקורסיבית: $B_{n+1}=\sum _{k=0}^{n}{n \choose k}B_{k}$, $\ B_{0}=1$.
הפונקציה היוצרת המעריכית של מספרי בל היא:

$\sum _{n=0}^{\infty }{\frac {B_{n}}{n!}}z^{n}=e^{e^{z}-1}$

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

מדיה וקבצים בנושא חלוקה בוויקישיתוף

• חלוקה, באתר MathWorld (באנגלית)