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

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

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

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

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

$${\binom {n}{k}}={\frac {n(n-1)\dotsb (n-k+1)}{k(k-1)\dotsb 1}}={\frac {n!}{k!(n-k)!}}$$

כאשר $k>n$ זה שווה לאפס.

הנוסחה הזאת נובעת מהעובדה שלכל צירוף עם $k$ איברים מהקבוצה $S$ בגודל $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 הקלפים ביד שונים, והסדר שלהם לא משנה. יש $2,598,960$ צירופים כאלה, והסיכוי למשוך כל יד אחת באקראי הוא ${\frac {1}{2,598,960}}$.

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

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

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

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

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

$$\left(\!\!{\binom {n}{k}}\!\!\right)={\binom {n+k-1}{k}}$$

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

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

הערות שוליים

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

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