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

מתוך ויקיפדיה, האנציקלופדיה החופשית
Nuvola apps edu mathematics blue-p.svg

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

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

צירוף ללא חזרות[עריכת קוד מקור | עריכה]

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

כאשר זה שווה לאפס.

הנוסחה הזאת נובעת מהעובדה שלכל צירוף עם איברים מהקבוצה בגודל , יש תמורות. אזי או באופן שקול: [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]

קישורים חיצוניים[עריכת קוד מקור | עריכה]

ויקישיתוף מדיה וקבצים בנושא צירוף בוויקישיתוף

הערות שוליים[עריכת קוד מקור | עריכה]

  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.