מולטי קבוצה

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

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

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

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

לדוגמה, המולטי קבוצה  מוגדרת על ידי הזוג הסדור  כאשר  מוגדרת על ידי . עוצמה המולטי קבוצה היא .

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

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

 מספר המולטי קבוצות 
מספר המולטי קבוצות בגודל  שניתן לבחור מתוך קבוצה (רגילה) בת  איברים מסומן . לדוגמה, בקבוצה  יש 3 איברים, וניתן לבחור מתוכה 6 מולטי קבוצות שונות בגודל 2: . לכן מתקיים: . באופן כללי, מתקיים השוויון הבא: , כאשר  הוא המקדם הבינומי.

 יישומים 
למולטי קבוצה שימושים בקומבינטוריקה. כך לדוגמה מספר הפתרונות השלמים האי־שליליים למשוואה  שווה ל-. בתורת הגרפים, משתמשים במולטי קבוצה כדי להגדיר את מושג המולטיגרף.

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

מולטי קבוצה ממומשת כמבנה נתונים מובנה בשפות תכנות כמו C++ ו-C#.

 קישורים חיצוניים 
 Richard P. Stanley, Enumerative Combinatorics Chapter 1.2, second edition, 2011

 Wayne D. Blizard, Multiset theory, Notre Dame Journal of Formal Logic 30 (1), Winter 1989 

 הערות שוליים 

קטגוריה:תורת הקבוצות