צירוף (קומבינטוריקה)

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

צֵירוּף או קוֹמְבִּינַצְיָה הוא בחירה של פריטים מקבוצת איברים שונים, כך שסדר הבחירה אינו משנה (בניגוד לתמורה). באופן פורמלי, צירוף של איברים מקבוצה , הוא תת-קבוצה בת איברים שונים של . לכן, שני צירופים זהים אם ורק אם לכל צירוף יש אותם איברים. סדר האיברים חסר משמעות.

צירוף ללא חזרות

עריכה

אם בקבוצה   יש   איברים, מספר הצירופים בגודל   מסומן כ- , כאשר   הוא שווה למקדם הבינומי:

 
אם   אז  .

הנוסחה הזאת נובעת מהעובדה שלכל צירוף עם   איברים מקבוצה בגודל  , יש   תמורות. אזי   או באופן שקול:  [1]. קבוצת כל הצירופים בגודל   של קבוצה   מסומנת לעיתים קרובות  .

דוגמה

עריכה

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

צירוף עם חזרות

עריכה

צירוף הוא קבוצה של   דברים שנלקחו בכל פעם ללא חזרה. כדי להתייחס לצירופים שבהם החזרה מותרת, נדרש לציין זאת. אם בדוגמה של שלושת הפירות, אפשר היה לקבל שני פירות מאותו סוג, היו נוספות עוד 3 אפשרויות: שני תפוחים; שני תפוזים; שני אגסים.

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

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

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

 

דוגמה

עריכה

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

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

מספר המולטי-קבוצה שקול לפתרון כוכבים ומחיצות
1 {1,1,1} [3,0,0,0]  
2 {1,1,2} [2,1,0,0]  
3 {1,1,3} [2,0,1,0]  
4 {1,1,4} [2,0,0,1]  
5 {1,2,2} [1,2,0,0]  
6 {1,2,3} [1,1,1,0]  
7 {1,2,4} [1,1,0,1]  
8 {1,3,3} [1,0,2,0]  
9 {1,3,4} [1,0,1,1]  
10 {1,4,4} [1,0,0,2]  
11 {2,2,2} [0,3,0,0]  
12 {2,2,3} [0,2,1,0]  
13 {2,2,4} [0,2,0,1]  
14 {2,3,3} [0,1,2,0]  
15 {2,3,4} [0,1,1,1]  
16 {2,4,4} [0,1,0,2]  
17 {3,3,3} [0,0,3,0]  
18 {3,3,4} [0,0,2,1]  
19 {3,4,4} [0,0,1,2]  
20 {4,4,4} [0,0,0,3]  

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

עריכה
  מדיה וקבצים בנושא צירוף בוויקישיתוף
  • צירוף, באתר MathWorld (באנגלית)

הערות שוליים

עריכה
  1. ^ Reichl, Linda E. (2016). "2.2. Counting Microscopic States". A Modern Course in Statistical Physics. WILEY-VCH. p. 30. ISBN 978-3-527-69048-0.
  2. ^ Benjamin & Quinn 2003, p. 70
  3. ^ Benjamin & Quinn 2003, p. 71
  4. ^ Mazur 2010, p. 10 where the stars and bars are written as binary numbers, with stars=0 and bars = 1.