1 - בעיות ספירה בסיסיות — קומבינטוריקה למדעי המחשב

הגדרה 1 (עקרון הסכום)

אם קיימת קבוצת איברים בגודל $A$ בגודל $n_{A}$ וקבוצה נוספת של איברים $B$ בגודל $n_{B}$ כאשר שתיהן קבוצות זרות.
אזי, לבחירת איבר אחד מתוך שתי הקבוצות $n_{A}+n_{B}$ אופנים.

הגדרה 2 (עקרון המכפלה)

אם אפשר לבחור איבר מסוג $A$ ב- $n_{A}$ אופנים ולאחר כל בחירה שכזו אפשר לבחור איבר מסוג $B$ ב- $n_{B}$ אופנים, אזי לבחירת שניהם בסדר הנ"ל יש $n_{A}n_{B}$ אפשרויות.

נשים לב כי יש סדר בבחירת הקבוצות.

הערה

סדר הוא מושג חשוב בקורס הזה.

הגדרה 3 (מספר תמורות)

מספר האפשרויות לסדר $n$ עצמים שונים: $P_{n}=P(n)$ .

משפט

P_{n}=n!

הוכחה:
בהתחלה אנו בוחרים איבר ראשון ויש לנו $n$ אפשרויות לכך.
לאחר מכן, אנו בוחרים את האיבר השני ויש לנו $n-1$ אפשרויות לכך (שכן אין חזרות).
לאחר מכן, אנו בוחרים את האיבר השלישי ויש לנו $n-1$ אפשרויות לכך.
וכך הלאה.
לכן, לפי עקרון הכפל, $P_{n}=n(n-1)(n-2)\dots1=n!$ .
∎

הגדרה 4 (עקרו החילוק)

מוצאים קבוצה $S$ שמכילה את כל הפתרונות החוקיים לבעיה קומבינטורית, אולם כל פתרון חוקי מופיע בריבוי $r$ .
התשובה לבעיה הקמובינטורית הוא $\frac{|S|}{r}$ .

דוגמה

מספר הדרכים לבחור שני אנשים עם חשיבות לסדר מתוך $n$ אנשים היא $n!$ .
נניח ויש לנו $\left\{ 1,2,3,4 \right\}$ כאשר $n=4$ אזי

\begin{matrix} 1234 & 1324 & 1423 & 1243 & 1342 & 1432 & 2134 & 2314 & 2413 & \dots \end{matrix}

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

\frac{4!}{2}

הוא מספר האפשרויות שיש לנו לבחור 2 אנשים.

הגדרה 5 (מספר חליפות)

מספר האפשרויות לבחור $k$ עצמים מתוך $n$ עצמים שונים עם חשיבות לסדר - $P_{n}^k$ .

משפט

P_{n}^k = \frac{n!}{(n-k)!}

הוכחה בהרצאה.

הגדרה 6 (מספר צירופים)

מספר האפשרויות לבחור $k$ עצמים מתוך $n$ עצמים שונים ללא חשיבות לסדר.

C_{n}^k=\begin{pmatrix} n \\ k \end{pmatrix}

משפט

C_{n}^k=\frac{P_{n}^k}{k!}=\frac{n!}{(n-k)!k!}=\begin{pmatrix} n \\ k \end{pmatrix}

תרגיל (1)

במשפחה אב, אם ו- $k$ ילדים.
א. מה מספר האפשרויות לסדרם סביב שולחן עגול(המושבים אינם ממוספרים)?
ב. אם האב והאם יושבים תמיד אחד ליד השניה?

פתרון א':
כשאנחנו מסדרים $n$ אנשים בשורה יש $n!$ אפשרויות. אך במעגל יכול להיות כמה פתרונות בשורה שהם זהים במעגל. נניח עבור $k=2$ וסידורי השורות $1234$ ו- $4123$ נקבל את אותו המעגל. נרצה לבדוק כמה סידורים בשורה יתנו את אותו המעגל(ואז להשתמש בעקרון החיסור) יש בדיוק $k+2$ אפשרויות לעשות את זה ולכן לפי עקרון החילוק $\frac{(k+2)!}{k+2}$ ולכן מספר האפשרויות הוא $(k+1)!$ .

פתרון ב':
נאחד את האמא והאבא לאדם אחד ואז יהיו לנו $k+1$ אנשים לסדר במעגל.
הסידור במעגל יהיה $k!$ ואז נדרש לקבוע סדר ויש 2 דרכים לעשות זאת לפי מספר התמורות ולכן זה $2k!$ אפשרויות.

תרגיל

בקורס קומבינטוריקה $2n$ סטודנטים. לשם הגשת תרגילי בית עליהם להתחלק לזוגות. מה מספר האפשרויות לעשות זאת?

סדר בין הזוגות? אין
סדר בתוך הזוגות? אין

נתחיל מסדר תמורות שהוא $(2n)!$ . כעת יש לנו את 2 הריבויים שאותם אנחנו לא צריכים. סך הכל יש $2^n$ ריבוי של סדר בתוך הזוגות. בנוסף, יש לנו גם ריבוי בין הזוגות ונרצה גם להתעלם ממנו. הריבוי בין הזוגות הוא $n!$ ולכן:

\frac{(2n)!}{2^n\cdot n!}

וזו התשובה שלנו.

הגדרה 1 (עקרון הסכום)

הגדרה 2 (עקרון המכפלה)

נשים לב כי יש סדר בבחירת הקבוצות.

הערה

סדר הוא מושג חשוב בקורס הזה.

הגדרה 3 (מספר תמורות)

מספר האפשרויות לסדר $n$ עצמים שונים: $P_{n}=P(n)$ .

משפט

P_{n}=n!

הגדרה 4 (עקרו החילוק)

דוגמה

מספר הדרכים לבחור שני אנשים עם חשיבות לסדר מתוך $n$ אנשים היא $n!$ .
נניח ויש לנו $\left\{ 1,2,3,4 \right\}$ כאשר $n=4$ אזי

\begin{matrix} 1234 & 1324 & 1423 & 1243 & 1342 & 1432 & 2134 & 2314 & 2413 & \dots \end{matrix}

\frac{4!}{2}

הוא מספר האפשרויות שיש לנו לבחור 2 אנשים.

הגדרה 5 (מספר חליפות)

מספר האפשרויות לבחור $k$ עצמים מתוך $n$ עצמים שונים עם חשיבות לסדר - $P_{n}^k$ .

משפט

P_{n}^k = \frac{n!}{(n-k)!}

הוכחה בהרצאה.

הגדרה 6 (מספר צירופים)

מספר האפשרויות לבחור $k$ עצמים מתוך $n$ עצמים שונים ללא חשיבות לסדר.

C_{n}^k=\begin{pmatrix} n \\ k \end{pmatrix}

משפט

C_{n}^k=\frac{P_{n}^k}{k!}=\frac{n!}{(n-k)!k!}=\begin{pmatrix} n \\ k \end{pmatrix}

תרגיל (1)

תרגיל

בקורס קומבינטוריקה $2n$ סטודנטים. לשם הגשת תרגילי בית עליהם להתחלק לזוגות. מה מספר האפשרויות לעשות זאת?

סדר בין הזוגות? אין
סדר בתוך הזוגות? אין

\frac{(2n)!}{2^n\cdot n!}

וזו התשובה שלנו.