מבוא לקומבינטוריקה

קומבינטוריקה הוא ענף במתמטיקה העוסק בספירת עצמים המקיימים תכונה מסוימת. לדוגמא, כמה תוצאות אפשריות שונות יש למשחקי הכדורגל (על מנת למלא טופס וינר).

אנו נלמד כיצד לחשב ישירות את מספר האפשרויות או כיצד להציג את הבעייה באופן שקול אותו אנו יודעים לחשב.

דוגמא. 10 אנשים עומדים בתור למכולת, כאשר בעל המכולת החליט להוסיף קופאי. כמה דרכים ישנן לחלק את האנשים בין הקופאים כך שלא יהיה אדם אחד בתור מאחורי אדם אחר שהיה לפניו בתור?

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

דוגמא. בכמה דרכים אפשר לסדר n אנשים בתור?

פתרון. כל אחד יכול להיות ראשון בתור לכן כבר יש n אפשרויות. כעת, נניח ואיציק ראשון בתור, נותר לסדר n-1 אנשים אחריו בתור. נניח באינדוקציה שמספר האפשרויות לסדר n-1 אנשים בתור הוא [math]\displaystyle{ (n-1)! }[/math] ונקבל שמספר האפשרויות שלנו הוא [math]\displaystyle{ n\cdot (n-1)! = n! }[/math].

דוגמא. בכמה דרכים ניתן לבחור קבוצה של k חפצים מתוך קבוצה של n חפצים? (במילים אחרות, כמה תת קבוצות מעוצמת k יש לקבוצה מגודל n).

פתרון. נמיר את הבעייה לבעייה אחרת. נספור את כמות האפשרויות לבחור k חפצים כאשר הסדר בינהם משנה, ולאחר מכן נחלק את הכמות שקיבלנו במספר האפשרויות לסדר את k החפצים (הלא הוא [math]\displaystyle{ k! }[/math]).

אם כך, אנו מעוניינים לדעת כמה אפשרויות יש לנו לבחור k חפצים מתוך n חפצים כאשר הסדר שלהם משנה. נסדר את n החפצים בשורה וניקח את k הראשונים. כמה פעמים נקבל את אותה סדרת k חפצים? בדיוק כמספר הפעמים שאפשר לסדר את n-k החפצים הנותרים.

אם כך, קיבלנו נוסחא [math]\displaystyle{ {n \choose k} = \frac{n!}{k!(n-k)!} }[/math]

נסכם בטבלה את התוצאות הבסיסיות והידועות:

בעייה	מספר האפשרויות
מספר האפשרויות לסדר n אנשים שונים בשורה	[math]\displaystyle{ n! }[/math]
מספר האפשרויות לבחור קבוצה של k תלמידים מתוך כיתה של n תלמידים	[math]\displaystyle{ {n \choose k} = \frac{n!}{k!(n-k)!} }[/math]
מספר האפשרויות לבנות סדרה עם k איברים מתוך קבוצה המכילה מ איברים	[math]\displaystyle{ n^k }[/math]
מספר האפשרויות לבנות סדרה עם k איברים שונים מתוך קבוצה המכילה n איברים	[math]\displaystyle{ \frac{n!}{(n-k)!} }[/math]

תרגיל. כמה פתרונות שלמים אי שליליים יש למשוואה [math]\displaystyle{ x_1+...+x_n=k }[/math]?