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

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

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

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

אם בקבוצה $S$ יש $n$ איברים, מספר הצירופים בגודל $k$ מסומן כ-$C_{k}^{n}$, כאשר $k\leq n$ הוא שווה למקדם הבינומי: $${\binom {n}{k}}={\frac {n(n-1)\cdots (n-k+1)}{k(k-1)\cdots 1}}={\frac {n!}{k!(n-k)!}}$$ אם $k>n$ אז ${\binom {n}{k}}=0$.

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

דוגמה

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

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

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

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

אם נשייך אינדקס לכל אחד מאיברי הקבוצה $S$, ונתייחס לכל איבר בקבוצה כ"סוג" של אובייקט, אז נוכל לציין באמצעות$x_{i}$ את מספר איברים מסוג $i$ בצירוף. אזי, מספר התת-קבוצות בגודל $k$ הוא מספר הפתרונות השלם האי-שלילי של המשוואה הדיופנטית: $x_{1}+x_{2}+\cdots +x_{n}=k$.

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

דוגמה

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

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

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

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

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

• צירוף, באתר MathWorld (באנגלית)