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

בקומבינטוריקה, חלוקה בגודל n היא חלוקה של המספרים $1,\dots ,n$ לחלקים רצופים שגודלם אינו עולה, כגון $\{1,\dots ,7\}=\{1,2,3\}\cup \{4,5\}\cup \{6,7\}$, שאפשר לכתוב בקיצור כ-$7=3+2+2$.

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

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}$

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

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