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

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

==צירוף ללא חזרות==
אם בקבוצה <math>S</math> יש <math>n</math> איברים, מספר הצירופים בגודל <math>k</math> מסומן כ-<math>C^n_k</math>, כאשר <math>k\le n</math> הוא שווה למקדם הבינומי:
<math display=block>\binom{n}{k}=\frac{n(n-1)\cdots(n-k+1)}{k(k-1)\cdots1}=\frac{n!}{k!(n-k)!}</math>
אם <math>k>n</math> אז <math>\binom{n}{k}=0</math>.

הנוסחה הזאת נובעת מהעובדה שלכל צירוף עם <math>k</math> איברים מקבוצה בגודל <math>n</math>, יש <math>k!</math> תמורות. אזי <math>P^n_k=C^n_k\times k!</math> או באופן שקול: <math>C^n_k = P^n_k / k!</math>. קבוצת כל הצירופים בגודל <math>k</math> של קבוצה <math>S</math> מסומנת לעיתים קרובות <math>\textstyle\binom{S}{k}</math>.

===דוגמה===
בהינתן 3 פירות: תפוח, תפוז ואגס, ועלינו לבחור שניים, יש שלושה צירופים אפשריים: תפוח ואגס; תפוח ותפוז; או אגס ותפוז. בדוגמה זו, הקבוצה קטנה מספיק בכדי להציג את כל הצירופים. אבל זה לא יהיה פרקטי עבור קבוצות גדולות יותר. למשל, ניתן לתאר יד פוקר כצירוף של 5 קלפים (<math>k=5</math>) מחפיסת בת 52 קלפים (<math>n=52</math>). 5 הקלפים ביד שונים, והסדר שלהם לא משנה. יש <math>\tbinom{52}{5}=2598960</math> צירופים כאלה, והסיכוי לכל יד כזו הוא <math>\frac{1}{2598960}</math>.

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

צירוף <math>k</math> איברים עם חזרות, מקבוצה <math>S</math> בגודל <math>n</math>, נתון על ידי קבוצה של <math>k</math> איברים לא בהכרח שונים מהקבוצה <math>S</math>. גם כאן הסדר אינו נלקח בחשבון. לכן, שני צירופים הם זהים, אם ניתן לקבל את האחד מהשני על ידי שינוי הסדר. במילים אחרות, זהו מדגם של <math>k</math> איברים מקבוצה בגודל <math>n</math>, המאפשרים כפילויות (כלומר, עם חזרה) אך תוך התעלמות מסדרים שונים (למשל: <math>\{1,2,3\}=\{3,2,1\}</math>).

אם נשייך אינדקס לכל אחד מאיברי הקבוצה <math>S</math>, ונתייחס לכל איבר בקבוצה כ"סוג" של אובייקט, אז נוכל לציין באמצעות<math>x_i</math> את מספר איברים מסוג <math>i</math> בצירוף. אזי, מספר התת-קבוצות בגודל <math>k</math> הוא מספר הפתרונות השלם האי-שלילי של המשוואה הדיופנטית: <math>x_1+x_2+\cdots+x_n=k</math>.

אם בקבוצה <math>S</math> יש <math>n</math> איברים, מספר הצירופים בגודל <math>k</math> שניתן לבנות מאיבריה עם חזרות מסומן ב-<math>\left(\!\!\tbinom{n}{k}\!\!\right)</math>. סימון זה מקביל למקדם הבינומי שסופר <math>k</math> תת-קבוצות. הוא יכול להיכתב גם במונחים של מקדמים בינומיים:
<math display=block>\left(\!\!\!\binom{n}{k}\!\!\!\right)=\binom{n+k-1}{k}</math>

===דוגמה===
אם בתפריט יש ארבעה סוגי סופגניות (<math>n=4</math>) ונרצה להזמין שלוש סופגניות (<math>k=3</math>), ניתן לחשב את מספר הדרכים לבחירת הסופגניות עם חזרה באמצעות הנוסחה: <math>\bigl(\!\!\tbinom{4}{3}\!\!\bigr)=\tbinom{4+3-1}{3}=\tbinom{6}{3}=20</math>. 

ניתן לאמת תוצאה זו על ידי רישום כל התת-מולטי-קבוצות בגודל של 3 של הקבוצה <math>S=\{1,2,3,4\}</math>. כפי שמוצג בטבלה (להלן) העמודה השנייה מפרטת את הסופגניות שנבחרו, העמודה השלישית מציגה את הפתרונות המספרים השלמים האי-שליליים <math>[x_1,x_2,x_3,x_4]</math> של המשוואה <math>x_1+x_2+x_3+x_4=3</math>, העמודה האחרונה מציגה את הכוכבים והמחיצות של הפתרונות.

{| class="wikitable mw-collapsible" style="text-align:center; margin-left: auto; margin-right: auto; border; none"
! מספר
! המולטי-קבוצה
! שקול לפתרון
! כוכבים ומחיצות
!
|-
| 1
| {1,1,1}
| [3,0,0,0]
| <math>\bigstar\bigstar\bigstar|||</math>
|rowspan=20|
|-
| 2
| {1,1,2}
| [2,1,0,0]
| <math>\bigstar\bigstar|\bigstar||</math>
|-
| 3
| {1,1,3}
| [2,0,1,0]
| <math>\bigstar\bigstar||\bigstar|</math>
|-
| 4
| {1,1,4}
| [2,0,0,1]
| <math>\bigstar\bigstar|||\bigstar</math>
|-
| 5
| {1,2,2}
| [1,2,0,0]
| <math>\bigstar|\bigstar\bigstar||</math>
|-
| 6
| {1,2,3}
| [1,1,1,0]
| <math>\bigstar|\bigstar|\bigstar|</math>
|-
| 7
| {1,2,4}
| [1,1,0,1]
| <math>\bigstar|\bigstar||\bigstar</math>
|-
| 8
| {1,3,3}
| [1,0,2,0]
| <math>\bigstar||\bigstar\bigstar|</math>
|-
| 9
| {1,3,4}
| [1,0,1,1]
| <math>\bigstar||\bigstar|\bigstar</math>
|-
| 10
| {1,4,4}
| [1,0,0,2]
| <math>\bigstar|||\bigstar\bigstar</math>
|-
| 11
| {2,2,2}
| [0,3,0,0]
| <math>|\bigstar\bigstar\bigstar||</math>
|-
| 12
| {2,2,3}
| [0,2,1,0]
| <math>|\bigstar\bigstar|\bigstar|</math>
|-
| 13
| {2,2,4}
| [0,2,0,1]
| <math>|\bigstar\bigstar||\bigstar</math>
|-
| 14
| {2,3,3}
| [0,1,2,0]
| <math>|\bigstar|\bigstar\bigstar|</math>
|-
| 15
| {2,3,4}
| [0,1,1,1]
| <math>|\bigstar|\bigstar|\bigstar</math>
|-
| 16
| {2,4,4}
| [0,1,0,2]
| <math>|\bigstar||\bigstar\bigstar</math>
|-
| 17
| {3,3,3}
| [0,0,3,0]
| <math>||\bigstar\bigstar\bigstar|</math>
|-
| 18
| {3,3,4}
| [0,0,2,1]
| <math>||\bigstar\bigstar|\bigstar</math>
|-
| 19
| {3,4,4}
| [0,0,1,2]
| <math>||\bigstar|\bigstar\bigstar</math>
|-
| 20
| {4,4,4}
| [0,0,0,3]
| <math>|||\bigstar\bigstar\bigstar</math>
|}

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

*

==הערות שוליים==

קטגוריה:ערכים שבהם תבנית בריטניקה אינה מתאימה
קטגוריה:קומבינטוריקה