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

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

הקומפוזיציה  היא אותה חלוקה כמו , והקומפוזיציות  ו-  הן אותן חלוקות כמו .

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

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

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

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

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

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

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

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

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



קטגוריה:קומבינטוריקה
קטגוריה:תורת המספרים