קומבינטוריקה – סיכום צירופים/חזרות/תמורות עם וללא החזרה

צירופים בלי חזרות

בחירת k איברים שונים מתוך n ללא חשיבות לסדר הבחירה,כך שאיבר יכול להיבחר פעם אחת בלבד.
פיזור k כדורים זהים בתוך n תאים שונים כך שבכל תא יש מקום לכדור אחד בלבד.
במשולש פסקל, זהו המקדם של האיבר ה-k-י בפיתוח הבינום   a+b)n)
לוטו (אין חשיבות לסדר הגרלת הכדורים).
מספר תתי הקבוצות בגודל k של קבוצה  A| = n| .

צירופים עם חזרות
בחירת k איברים לא בהכרח שונים מתוך n סוגים של איברים ללא חשיבות לסדר הבחירה,כך שאיבר יכול להיבחר יותר מפעם אחת.
בחירה של k עצמים מתוך n סוגי עצמים כאשר כל העצמים השייכים לאותו סוג -זהים.
פיזור k כדורים זהים בתוך n תאים שונים,כאשר אין הגבלה על מספר הכדורים בתא.
מספר הפתרונות בטבעיים (כולל אפס) של המשוואה     X1+X2+…+Xn = k.
בחירת k אותיות מתוך א"ב של n אותיות ללא חשיבות לסדר ועם החזרות.
מספר האפשרויות לצבוע k חדרים זהים ב-n צבעים שונים.

 

 

חליפות בלי חזרות

בחירת k איברים שונים מתוך n עם חשיבות לסדר הבחירה,כך שאיבר יכול להיבחר פעם אחת בלבד.
פיזור k כדורים שונים בתוך n תאים שונים כך שבכל תא יש מקום לכדור אחד בלבד.
מספר המחרוזות השונות באורך k שניתן לבנות מ-n תווים שונים מבלי להשתמש באותו תו יותר מפעם אחת.
מספר הפונקציות החד-חד-ערכיות של קבוצה  A| = k|  ל- B| = n|

 

 

 

 

 

 

 

 

חליפות עם חזרות

בחירת k איברים לא בהכרח שונים מתוך n סוגים של איברים עם חשיבות לסדר הבחירה,כך שאיבר יכוללהיבחר יותר מפעם אחת.
פיזור k כדורים שונים בתוך n תאים שונים, כאשר אין הגבלה על מספר הכדורים בתא.
מספר המחרוזות השונות באורך k שניתן לבנות מ-n תווים שונים כאשר אין הגבלה על  מספר הפעמיםבו משתמשים באותו תו.
מספר האופנים  לחלוקת 3 פרסים שונים בין 15 תלמידים כאשר תלמיד מסויים יכול לקבל  יותר מפרס אחד        (אנלוגיה ל"טוטו").
מטילים קוביה 5 פעמים. כמה חמישיות סדורות יכולות להתקבל?  פתרון : 65
מספר הפונקציות של  A| = k|  ל- B| = n|
 
הערה
 :   מספר הפונקציות מ- A| = k|  ל- B| = n|  הוא  n+1)k)

 

 

 

 

 

 

תמורות בלי חזרות

מספר האפשרויות לסדר n איברים בשורה.
מספר הפונקציות של  A| = n|  על עצמה.
מספר יחסי הסדר המלא מעל  A| = n| .

 

 

 

תמורות עם חזרות ועם חשיבות לסדר

מספר האפשרויות לסדר n עצמים שונים שביניהם k1 עצמים זהים, k2 עצמים אחרים זהים וכו' כך שמתקיים k1+k2+…+km = n
מספר האופנים לחלק n שחקני כדורסל  (שונים זה מזה,כמובן) ל-k קבוצות כך שבל קבוצה  n/k שחקנים ולכל קבוצה תלבושת בצבע אחר. כאן ,מעבר לחלוקה לקבוצות, יש חשיבות לתת שמות לקבוצות :  קבוצה א', קבוצה ב', וכן הלאה.
מספר האפשרויות לפזר n כדורים שונים בתוך k תאים שונים כך שבכל תא יהיו n/k כדורים.
מספר המילים השונות (מחרוזות שאינן בהכרח בעלות משמעות מילולית) שאפשר לבנות מהמחרוזת  "קומבינטוריקה". (מקרה אנלוגי לכדורסל,אך כאן קבוצות האותיות הזהות אינן שוות זו לזו).

 

 

 

 

 

פיזור/חלוקת K כדורים ל-N תאים – מקרים שונים

 

 

 

 

עקרון ההכלה-הדחה

 

מספר הפונקציות של  A| = n|  על  B| = k|
מספר האפשרויות לפזר n כדורים שונים ב-k תאים שונים כך שלפחות תא אחד ישאר ריק.
מטילים n>=6 קוביות שונות, מהו מספר התוצאות האפשריות בהן מופיע כל אחד מהמספרים 1 עד 6 (k=6) לפחות פעם אחת?

 

הערות:
א. חייב להתקיים n>=k. בפרט, כאשר n=k התוצאה היא  ! n.
ב. הנוסחה נכונה עבור k<=10, אם כי ניתן להמשיך וליישמה עבור k כרצוננו,                      באמצעות הוספת מחוברים מתאימים לפי הדוגמה.   אין הגבלה על n .
ג. הפרדת המחוברים, היוצרת סרבול מסוים,נובעת מכך ש-EXCEL מחשיבה את
(combin(x,y עבור x>y  כשגיאת מערכת , ואז הנוסחה כולה חסרת משמעות. התנאי
שנכתב "מאלץ" ביטוי זה להתאפס ,ובכך נפתרת הבעיה.

 

 

 

 

 

 

 

 

970x90