מולטי קבוצה

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

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

לדוגמה, המולטי קבוצה $\{a,a,b\}$ היא מולטי קבוצה בת שלושה איברים: האיבר a עם ריבוי 2 והאיבר b עם ריבוי 1. כיוון שיש חשיבות לחזרה, היא אינה זהה למולטי קבוצה $\{a,b\}$, שבה שני איברים והמספר 1 מופיע בה רק פעם אחת. כיוון שאין חשיבות לסדר, מולטי קבוצה זו זהה למולטי קבוצה $\{b,a,a\}$.

הגדרה

מולטי קבוצה מוגדרת על ידי זוג סדור $(A,f)$ כאשר A היא קבוצה רגילה המכילה את האיברים השונים בקבוצה (כל איבר מופיע בה פעם אחת, שכן זו קבוצה רגילה ואין בה חשיבות לחזרה), ו-$f:A\rightarrow \mathbb {N}$ היא פונקציית הריבוי שמקבלת איבר בקבוצה ומחזירה את הריבוי שלו, כלומר מספר הפעמים שהאיבר מופיע במולטי קבוצה.

העוצמה של מולטי קבוצה בעלת מספר סופי של איברים היא סכום הריבויים של איבריה: $\sum _{x\in A}f(x)$.

לדוגמה, המולטי קבוצה $\{a,a,b\}$ מוגדרת על ידי הזוג הסדור $(\{a,b\},f)$ כאשר $f:\{a,b\}\rightarrow \mathbb {N}$ מוגדרת על ידי $f(a)=2,f(b)=1$. עוצמה המולטי קבוצה היא $f(a)+f(b)=2+1=3$.

יחס ההכלה מוגדר על מולטי קבוצות באופן הבא: עבור מולטי קבוצות $M_{1}=(A_{1},f_{1}),M_{2}=(A_{2},f_{2})$, מתקיים $M_{2}\subseteq M_{1}\iff A_{2}\subseteq A_{1}\ and\ \forall a\in A_{2}:f_{2}(a)\leq f_{1}(a)$.

לעיתים כותבים את המולטי קבוצה באופן מקוצר, כך: עבור מולטי קבוצה עם איברים $x_{1},...,x_{n}$ עם ריבויים $a_{1},...,a_{n}$ בהתאמה, כותבים $\{x_{1}^{a_{1}},x_{2}^{a_{2}},x_{n}^{a_{n}}\}$. לדוגמה, את המולטי קבוצה $\{a,a,a,b,c,c\}$ ניתן לכתוב בקיצור $\{a^{3},b,c^{2}\}$.

מספר המולטי קבוצות

מספר המולטי קבוצות בגודל $k$ שניתן לבחור מתוך קבוצה (רגילה) בת $n$ איברים מסומן $\left(\!\!{n \choose k}\!\!\right)$. לדוגמה, בקבוצה $\{a,b,c\}$ יש 3 איברים, וניתן לבחור מתוכה 6 מולטי קבוצות שונות בגודל 2: $\{a,a\},\{b,b\},\{c,c\},\{a,b\},\{a,c\},\{b,c\}$. לכן מתקיים: $\left(\!\!{3 \choose 2}\!\!\right)=6$. באופן כללי, מתקיים השוויון הבא: $\left(\!\!{n \choose k}\!\!\right)={n+k-1 \choose k}$, כאשר ${n \choose k}$ הוא המקדם הבינומי.

יישומים

למולטי קבוצה שימושים בקומבינטוריקה. כך לדוגמה מספר הפתרונות השלמים האי־שליליים למשוואה $x_{1}+x_{2}+...+x_{n}=k$ שווה ל-$\left(\!\!{n \choose k}\!\!\right)$. בתורת הגרפים, משתמשים במולטי קבוצה כדי להגדיר את מושג המולטיגרף. למולטי קבוצה שימושים רבים גם במדעי המחשב.

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

• Richard P. Stanley, Enumerative Combinatorics Chapter 1.2, second edition, 2011
• מולטי קבוצה, באתר MathWorld (באנגלית)