תרגיל

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

פתרון א':
נדרש לדעת עוד כמה דברים לפני שאנו פותרים את התרגיל:

האם חייב לחלק את כל הסוכריות? כן
האם איכפת לי איזה סוכריות מקבל משה ואיזה חיים? לא - בגלל שהסוכריות זהות. ⇐ איכפת לנו רק מהכמות שכל אחד מקבל.

נסמן ב- $m$ את כמות הסוכריות שמשה מקבל וב- $h$ את כמות הסוכריות שחיים מקבל. ונקבל כי $h=10-m$ .
נראה כי:

\begin{matrix} h & \qquad \quad & m \\ n & & 0 \\ n-1 & & 1 \\ \vdots & & \vdots \\ 0 & & n \end{matrix}

לכן, יש לנו $11$ אפשרויות במקרה הזה לחלוקה. (כי יש $\left\{ 0,1,\dots,n \right\}$ אפשרויות)

פתרון ב':
נדרש כעת להגיד בדיוק אילו סוכריות משה קיבל ואילו סוכריות חיים קיבל. נשתמש באותם משתנים ממקודם.
עבור כל מצב בשאלה הקודמת, נניח $m$ ו- $10-m$ , כמה דרכים ניתן לחלק את הסוכריות? (שהרי הן עכשיו שונות)
זוהי בחירה ללא חשיבות לסדר של $m$ סוכריות מתוך $10$ ואז חיים מקבל את כל מה שלא בחרנו. לכן זה $\begin{pmatrix}10 \\ m\end{pmatrix}$ עבור $0\leq m\leq10$ .

הערה (מה עשינו פה?)

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

\sum_{m=0}^{10} \begin{pmatrix} 10 \\ m \end{pmatrix}

זה לא טוב כתשובה סופית("בקורס הזה אנחנו לא אוהבים סכום" - המתרגל) ולכן, נדרש למשהו אחר כדי לייצג את התשובה שלנו.
נשים לב כי לכל סוכריה יש $2$ מצבים: או שהיא אצל חיים או שהיא אצל משה. זה קורה לכל סוכריה ולכל סוכריה אנו יכולים לבחור את שאר האופציות - זהו אינו משהו שאנו עושים בנפרד ולכן זה יהיה כפל.
לכן, הפתרון שלנו יהיה:

\overbracket{2\cdot 2\cdot 2\cdots 2}^{10}=2^{10}

הפתרונות זהים, אך אנו נעדיף את $2^{10}$ .

פתרון ג':
כעת נוספה לנו עוד אפשרות - לא לחלק לאף אחד. לכן, במקום $2^{10}$ נקבל $3^{10}$ .

תרגיל

כמה אפשרויות יש להושיב $n$ אנשים על ספסל כאשר:
א. סם רואה את סימה מימינו (לאו דוקא צמוד)?

פתרון א':
תחילה נבחר שני מושבים עבור סם וסימה: $\begin{pmatrix}n\\ 2\end{pmatrix}$ .
נושיב את סם וסימה בשני המושבים - לזה דרך אחת כי סם חייב להיות משמאל לסימה.
כעת, נבחר את המקמות של כל שאר האנשים הלא חשובים: $(n-2)!$ - נזכור זאת מתמורות.
בסה"כ יש לנו: $\begin{pmatrix}n\\ 2\end{pmatrix}(n-2)!$ .

נסתכל על פתרון נוסף: נקרא לקבוצת ההושבות של סימה מימין לסם $A$ ולקבוצת ההושבות של סם מימין לסימה $B$ . בין הקבוצות הללו מתקיים $A \cap B=\emptyset$ . גודל הקבוצות הללו שווה שכן קיימת פונקציה חח"ע ועל $f:A\to B$ כך שעבור כל סידור מתקיים כי $f$ נותנת סידור זהה בו סם וסימה הפוכים במקומם. (בשיעורי הבית ובמבחן כמובן נדרש להגדיר במדוייק ולהוכיח) ⇐ $|A|=|B|$ .
על פי עקרון החיבור מתקיים: $|A|+|B|=n!$ ולכן $2|A|=n!$ ולכן $|A|=\frac{n!}{2}$ .

משפט

הבעיות הבאות שקולות:

בחירה עם חזרות של $k$ מתוך $n$ סוגים ללא חשיבות לסדר הבחירה
חלוקת $k$ כדורים זהים ל- $n$ תאים שונים.
מספר הפתרונות של המשוואה $x_{1}+x_{2}+\dots+x_{n}=k$ כאשר $x_{i}$ טבעיים(כולל 0)
מילים בינאריות עם $k$ אפסים ו- $n-1$ אחדים.

לבעיות אלו הפתרון הוא:

CC_{n}^k=\mathbb{C}_{n}^k = \left(\!\!\!\begin{pmatrix} n \\ k \end{pmatrix}\!\!\!\right)=\begin{pmatrix} k+(n-1) \\ k \end{pmatrix}

עוד תרגילים

תרגיל

יש ערימה של כדורים: אדומים, כחולים וסגולים. בכמה דרכים ניתן לבחור $10$ כדורים כך שמתקיים:
א. צריכים להיות לפחות 5 אדומים.
ב. צריכים להיות לכל היותר 4 כדורים אדומים.

פתרון א':
בשלב הראשון נקח $5$ אדומים וכך נדע שאנו עומדים בתנאי. יש לנו דרך אחת לקחת $5$ כדורים אדומים(כאילו, טכנית זה $\infty$ אבל בגלל שכל הכדורים האדומים זהים זה לא משנה)
לאחר מכן, צריך לבחור $5$ כדורים נוספים מתוך $3$ צבעים עם חזרות וכשהסדר לא משנה. לכן, זה יהיה $\mathbb{C}_{3}^5$ .
לכן, התשובה תהיה בסעיף זה: $\left(\!\!\!\begin{pmatrix}3 \\5\end{pmatrix}\!\!\!\right)$ שזה $\begin{pmatrix}7\\5\end{pmatrix}$ .

פתרון ב':
נפתור זאת באמצעות עקרון המשלים:

\R{\text{לפחות 5 אדומים}}+\R{\text{לכל היותר 4 אדומים}}=\R{\text{כל הבחירות}}

כל הבחירות יהיו $\mathbb{C}_{3}^{10}$ .
נזכור מסעיף א' כי $\mathbb{C}_{3}^5$ ולכן, הפתרון של ב' הינו $\mathbb{C}_{3}^{10}-\mathbb{C}_{3}^5$ .

נביט בפתרון נוסף לאותה הבעיה:
נבחר $5$ כדורים מתוך כחול-סגול-אדום - שלזה יש $\mathbb{C}_{3}^4$ ואז נבחר $5$ כדורים מתוך כחול-סגול שזה $\mathbb{C}_{2}^6$ ואז הפתרון שלנו יהיה $\mathbb{C}_{3}^4\cdot\mathbb{C}_{2}^6$ .
יש לנו בעיה בפתרון הזה - יש מצב שנספור את אותו הפתרון פעמיים - כי אנחנו עושים זאת בשלבים במקום במקביל, מה שיותר ריבוי של אותה אפשרות.

עוד תרגילים

תרגיל

פתרון א':
בשלב הראשון נקח

5

אדומים וכך נדע שאנו עומדים בתנאי. יש לנו דרך אחת לקחת

5

כדורים אדומים(כאילו, טכנית זה

\infty

אבל בגלל שכל הכדורים האדומים זהים זה לא משנה)
לאחר מכן, צריך לבחור

5

כדורים נוספים מתוך

3

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

\mathbb{C}_{3}^5

.
לכן, התשובה תהיה בסעיף זה:

\left(\!\!\!\begin{pmatrix}3 \\5\end{pmatrix}\!\!\!\right)

שזה

\begin{pmatrix}7\\5\end{pmatrix}

פתרון ב':
נפתור זאת באמצעות עקרון המשלים:

\R{\text{לפחות 5 אדומים}}+\R{\text{לכל היותר 4 אדומים}}=\R{\text{כל הבחירות}}

כל הבחירות יהיו

\mathbb{C}_{3}^{10}

.
נזכור מסעיף א' כי

\mathbb{C}_{3}^5

ולכן, הפתרון של ב' הינו

\mathbb{C}_{3}^{10}-\mathbb{C}_{3}^5

נביט בפתרון נוסף לאותה הבעיה:
נבחר

5

כדורים מתוך כחול-סגול-אדום - שלזה יש

\mathbb{C}_{3}^4

ואז נבחר

5

כדורים מתוך כחול-סגול שזה

\mathbb{C}_{2}^6

ואז הפתרון שלנו יהיה

\mathbb{C}_{3}^4\cdot\mathbb{C}_{2}^6

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

2 - בעיות מניה והמקדם המולטינומי

קומבינטוריקה למדעי המחשב

בעיות מניה והמקדם המולטינומי

2 - בעיות מניה והמקדם המולטינומי

קומבינטוריקה למדעי המחשב

בעיות מניה והמקדם המולטינומי

עוד תרגילים

עוד תרגילים