דוגמה

תוצאות אפשריות של קוביה: $\left\{ 1,2,3,4,5,6 \right\}$
כמה תוצאות יש להטלת קובייה? $|\left\{ 1,2,3,4,5,6 \right\}|=6$
כמה תוצאות יש להטלת קוביה $|\left\{ A,B,C,D,E,F \right\}|=6\quad ?ABC$

דוגמה

כמה תוצאות אפשריות יש להטלה של שלושה מטבעות שונים?

\begin{matrix} 000 & 100 & 010 & 001 & 110 & 011 & 101 & 111 \end{matrix}

דוגמה

כמה תוצאות אפשריות יש להטלה של שלושה מטבעות זהים?
שלוש פעמים 1, פעמיים 1 ופעם 0, פעמיים 0 ופעם 1, שלוש פעמים 0.

עקרונות בסיסיים

משפט (עקרון הסכום)

אם $X,Y$ קבוצות זרות אזי:

|X \cup Y|=|X|+|Y|

דוגמה

כמה תוצאות אפשריות ישנן להטלת קוביה $ABC$ או קוביית מספרים $1-6$ ?

X=\left\{ 1,2,3,4,5,6 \right\} \qquad Y=\left\{ A,B,C,D,E,F \right\}

|X \cup Y|=|X|+|Y|=6+6=12

ניתן להסתכל על זה גם בצורה של תמונות - כמה תמונות שונות יכולות להיות לנו מהטלת שתי הקוביות.

משפט (עקרון ההפרש)

אם $X,Y$ קבוצות סופיות ו- $Y \subseteq X$ אזי

|X \setminus Y|=|X|-|Y|

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

דוגמה

כמה תתי קבוצות יש ל- $\left\{ 1,2,3 \right\}$ המכילות לפחות 2 איברים?
יש $4$ קבוצות המכילות איבר אחד או פחות ולכן לפי עקרון ההפרש:

|X\setminus Y|=|X|-|Y|=8-4=4

משפט (עקרון הכפל)

אם $X,Y$ קבוצות סופיות אזי

|X\times Y|=|X|\cdot |Y|

דוגמה

כמה תוצאות אפשריות ישנן להטלת קוביית $ABC$ בנוסף להטלת קוביית מספרים $1-6$ ?

|X\times Y|=|X|\cdot |Y|=6\cdot6=36

בתיאור גרפי:
קומבי קומבי קומבי הרצאה 1 תמונה 1.png

דוגמה

נתונים שישה סטודנטים( $A-F$ )
בכמה אפשרויות ניתן לבחור מתוכם ועד של שני סטודנטים?

נפתור תחילה בעיה אחרת: כמה אפשרויות יש לנו אם הסדר בוועד חשוב.
תחילה יש לנו 6 אפשרויות לבחור יו"ר ואז 5 אפשרויות לבחור סיו"ר ולכן יש $6\cdot 5=30$ אפשרויות.

כעת, נפתור את הבעיה כאשר הסדר לא חשוב.
לכל אפשרות למקרה בו הסדר אינו חשוב - למשל $\left\{ A,B \right\}$ - מתאימות שתי אפשרויות למקרה בו הסדר חשוב: $(B,A),(A,B)$ ולכן, נקבל $15$ אפשרויות לסידור.
קומבי הרצאה 1 תמונה 2.png

דוגמה

\Theta=\left\{ A,B,\dots,Z \right\} \implies |\Theta|=n=26

\Omega=\left\{ 0,1,\dots,99 \right\} \implies |\Omega|=m=100

מספר האפשרויות בלחור איבר מ- $\Theta$ הוא $26$
מספר האפשרויות לבחור איבר מ- $\Theta$ או מ- $\Omega$ הוא $|\Theta \cup\Omega|=n+m=126$
מספר האפשרויות לבחור איבר מ- $\Theta$ ואיבר שני מ- $\Omega$ הוא ${|\Theta \times\Omega|}=n\cdot m=2600$
מספר האפשרויות לבחור שני איברים שונים מ- $\Theta$ עם חשיבות לסדר $n(n-1)=26\cdot25$ ובלי חשיבות לסדר הבחירה $\frac{n(n-1)}{2}=\frac{26\cdot 25}{2}$ .
מספר האפשרויות לסדר את האיברים של $\Theta$ בשורה יש לנו $n!$ אפשרויות
זאת מכיוון שיש לנו $n$ אפשרויות לשים את האיבר הראשון ואז $n-1$ אפשרויות לאיבר השני וכך הלאה.

הגדרה 1 (תמורה)

סידור של קבוצה נקרא תמורה. עוצמת קבוצת כל התמורות של קבוצה $\left\{ 1,2,\dots,n \right\}$ מסומנת $P_{n}$ והיא שווה ל- $n!$ .

משפט

P_{n+1}=(n+1)!=(n+1)P_{n}

P_{n}=\frac{P_{n+1}}{n+1}

עבור $n=0$ מתקיים $P_{0}=\frac{P_{1}}{1}=1$ ולכן $0!=1$ .

דוגמה (המשך הדוגמה הקודמת)

6. מספר האפשרויות לסדר את האיברים של $\Theta$ בשורה ואחריהם את $\Omega$ בשורה הוא $P_{n}\times P_{m}=n!\times m!$ .
7. מספר האפשרויות לסדר את האיברים של $\Theta$ כך ש- $A$ ו- $B$ סמוכים.
פתרון 1: מכיוון ש- $AB$ תמיד ביחד(לא משנה הסדר) נקרא לאיבר חדש $AB$ במקום $A,B$ ואז נסדר ולבסוף נכפיל ב- $2$ שכן יש שתי אפשרויות לסידור $A,B$ ולכן $2(n-1)!$ הוא מספר האפשרויות לסידור.
8. מספר האפשרויות לסדר את האיברים של $\Theta$ בשורה כך ש- $A,B$ אינם סמוכים.
פתרון 1: נשים לב לסעיף הקודם - כבר מצאנו את מספר אפשרויות עבורם $A,B$ סמוכים ולכן נוכל לבצע את עקרון ההפרש כך:

|X\setminus Y|=|X|-|Y|=n!-2(n-1)!= n(n-1)!-2(n-1)!=(n-2)(n-1)!

פתרון 2: נתחיל לסדר את כולם ללא $B$ ולזה יש $(n-1)!$ אפשרויות. לבסוף נרצה להכניס את $B$ ולכך יש לנו $n-2$ אפשרויות שכן יש לנו $n$ אפשרויות להכניס את $B$ אך שתיים מהן הן ליד $A$ ולכן לא טובות.

דוגמה

כמה מספרים שלמים בין $1$ ל- $1000$ מתחלקים ב- $3$ ללא שארית? $\left\{ 3,6,9,\dots,999 \right\}$

\frac{999}{3}=\left\lfloor \frac{1000}{3}\right\rfloor=333

כמה מספרים שלמים בין $1$ ל- $n$ מתחלקים ב- $m$ ללא שארית?

\left\lfloor \frac{n}{m}\right\rfloor

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

ספירת חליפות

הגדרה 2 (מספר חליפויות אפשריות)

מספר האפשרויות לבחור $k$ איברים בלי חזרות מתוך $n$ איברים שונים כשיש חשיבות לסדר מסומן $P_{n}^k$ או $P(n,k)$ .

דוגמה

נניח ויש לנו $100$ סטודנטים ואנו רוצים לקבוע משלחת של $10$ סטודנטים שכל אחד הולך למדינה אחרת.

\begin{array}{|c|c|} \hline 1 & 2 & \dots & k\\ \hline n & n-1 & \dots & n-(k-1) \\ \hline \end{array}

כלומר מספר האפשרויות לבחור $k$ איברים מתוך $n$ איברים כפי שהוצג הוא $P_{n}^k=n(n-1)(n-2)\dots(n-k+1)=\frac{n!}{(n-k)!}$

הערה

ניתן לרשום זאת גם כ- $(n-0)(n-1)\dots$

משפט

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

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

ספירת צירופים

הגדרה 3 (מספר צירופים אפשריים)

מספר האפשרויות לבחור $k$ איברים בלי חזרות מתוך $n$ איברים שונים כשאין חשיבות לסדר מסמון $C_{n}^k$ או $C(n,k)$ או $\binom{n}{k}$ .

דוגמה

יש לנו $n$ איברים שונים. כמה תתי קבוצות בגודל $k$ יש לקבוצה? (ניתן לחשוב על זה כשליחה של 10 סטודנטים למשלחת לאותה מדינה ולכן לא חשוב לנו מי נבחר קודם ומי נבחר אחר כך כי כולם הולכים לאותו המקום)

נעזיר בחליפות ממקודם - בחירת $k$ איברים בלי חזרות מתוך $n$ איברים שונים כשיש חשיבות לסדר. יש $k!$ אפשרויות לסידור של האיברים אחרי שבחרנו בהם ולכן, לפי עקרון הכפל יש לנו $k!\cdot C_{n}^k$ אפשרויות לסדר כשיש חשיבות לסדר ולפי המשפט הנ"ל מתקיים:

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

\Downarrow

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

דרך נוספת: נזכור כי ניתן לייצג כל תת קבוצה כרצף בינארי שכל 1 אומר שהאיבר נכנס לקבוצה וכל 0 אומר שהוא לא.
כמות הקבוצות שיש לנו היא כמות הוקטורים הבינארים ש-???

משפט

מספר האפשרויות לבחור $k$ איברים מתוך $n$ איברים שונים כשאין חשיבות לסדר ובלי חזרות הוא

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

משפט (תכונות של

C_{n}^k

)

P_{n}^k =\begin{pmatrix} n \\ k \end{pmatrix}k!

\begin{pmatrix} n \\ k \end{pmatrix}=\begin{pmatrix} n \\ n-k \end{pmatrix}=\frac{n(n-1)\dots(n-k+1)}{k!}

\begin{pmatrix} n \\ 0 \end{pmatrix}=\begin{pmatrix} n \\ n \end{pmatrix}=1

אם $m>n$ או $m<0$ אזי $\begin{pmatrix}n\\ m\end{pmatrix}=0$

סופרים את שאר הדברים

בעייה נוספת היא לבחור $k$ איברים עם חזרות מתוך $n$ איברים שונים(נניח $n=100$ ) כשיש חשיבות לסדר.
נסתכל על הטבלה:

\begin{array}{|c|c|} \hline 1 & 2 & 3 & 4 & 5 & \dots & k-3 & k-2 & k-1 & k \\ \hline 100 & 100 & 100 & 100 & 100 & \dots & 100 & 100 & 100 & 100 \\ \hline \end{array}

לבסוף נגלה כי:

משפט

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

n^k

הערה

שבוע הבא נראה איך מוצאים את האופציה האחרונה(בלי חשיבות לסדר ועם חזרות) וזוהי בעיה פחות טרוויאלית.

דוגמה

מילה בינארית היא סדרה סופית של $0$ ו- $1$ .
כמה מילים בינאריות באורך $n$ בהן $1$ מופיע בדיוק $k$ פעמים?

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

011010010111 \longrightarrow \left\{ 2,3,5,8,10,11,12 \right\}

וזה בדיוק $C_{n}^k$ שעשינו ממקודם כי אין חשיבות לסדר האחדים.
פתרון 2: על ידי עקרון הכפל: $1_{1}1_{2}1_{3}1_{4}\dots1_{k}0_{1}0_{2}\dots0_{n-k}$ ואז נסמן ב- $x$ את התשובה שאנחנו רוצים והכפלה של זה ב- $(n-k)!$ היא בדיוק הגרסה של זה כשיש חשיבות לסדר של שאר האיברים ובנוסף הכפלה של כל זה ב- $k!$ היא בדיוק סידור כל השורה ולכן:

x\cdot (n-k)!\cdot k!=n! \implies x= \frac{n!}{k!(n-k)!}=\begin{pmatrix} n \\ k \end{pmatrix}

הגדרה 4 (מילה)

מילה מעל אלפבית $A$ היא סדרה סופית של אותיות מ- $A$ .

דוגמה

כמה מילים באורך $n$ מכילות $k_{1}$ פעמים $1$ ו- $k_{2}$ פעמים 2 בנוסף ל- $k_{3}$ פעמים 3 ו- $k_{4}$ פעמים $4$ כך ש- $n=k_{1}+k_{2}+k_{3}+k_{4}$ ?

נעבוד באותה דרך שעבדנו בפתרון 2 ממקודם. נבחר קודם את המקומות של ה- $1$ -ים ואז יש לנו $\begin{pmatrix}n\\k_{1}\end{pmatrix}$ - אלו בחירות בלי חזרות ועם חשיבות לסדר. לאחר מכן, נדרש לבחור את המקמות של ה- $2$ -ים ויהיו לנו $\begin{pmatrix}n-k_{1}\\k_{2}\end{pmatrix}$ . לאחר מכן, נבחר את המקומות של ה- $3$ -ים, שיהיו לנו $\begin{pmatrix}n-k_{1}-k_{2}\\k_{3}\end{pmatrix}$ . לבסוף, נבחר את המקומות של $4$ שלהם יש $\begin{pmatrix}n-k_{1}-k_{2}-k_{3}\\k_{4}\end{pmatrix}$ .
לכן, לפי עקרון הכפל:

\R{\text{מספר האפשרויות}}=\begin{pmatrix} n \\ k_{1} \end{pmatrix}\begin{pmatrix} n-k_{1} \\ k_{2} \end{pmatrix}\begin{pmatrix} n-k_{1}-k_{2} \\ k_{3} \end{pmatrix}\begin{pmatrix} n-k_{1}-k_{2}-k_{3} \\ k_{4} \end{pmatrix}=\frac{n!}{k_{1}!(n-k_{1})!}\cdot \frac{(n-k_{1})!}{k_{2}!(n-k_{1}-k_{2})!}\cdot

\frac{(n-k_{1}-k_{2})!}{k_{3}!(n-k_{1}-k_{2}-k_{3})!}\cdot \frac{(n-k_{1}-k_{2}-k_{3})!}{k_{4}!}=\frac{n!}{k_{1}!k_{2}!k_{3}!k_{4}!}

כשאין חשיבות לסדר ויש חזרות

אנחנו נסמן זאת כך:

\mathbb{C}^k_{n}=\left( \!\!\! \begin{pmatrix} n \\ k \end{pmatrix} \!\!\! \right)

דוגמה

הטלה של $7$ קוביות שונות תתן לנו מספר תוצאות אפשריות של $6^7$ .
אך כעת, אם נקח קוביות זהות, יכולות להיות לנו מספר אפשרויות שיהיו אותה אפשרות.
נסמן ב- $x_{i}$ את מספר ההופעות של $i$ . הבעיה בעצם שקולה למספר הפתרונות של: $x_{1}+x_{2}+x_{3}+x_{4}+x_{5}+x_{6}=7$ כאשר $x_{i}\geq 0$ שלם.
נתרגם כעת את הבעיה למשהו שאולי קרוב יותר למשהו שאנחנו יודעים לפתור: נסמן את התוצאה של הפלת הקוביה ככדור בתא המתאים.
נעבור תא-תא, כל כדור יסומן כ- $1$ בין כל תא נשים $0$ . נניח עבור $1+3+2+0+0+1=7$ נקבל את הוקטור הבינארי $101110110001$ .
כמות הוקטורים הבינארים שיש לנו עם $7$ אחדים ו- $5$ אפסים הוא $\begin{pmatrix}12\\7\end{pmatrix}$ .

עבור בעיה כללית נבצע את אותו הדבר ונקבל כי מספר הפתרונות: $\begin{pmatrix}n+k-1\\ k\end{pmatrix}$ .

משפט

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

משפט

הערכים הבאים שווים:

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

דוגמה

מספר הפתרונות של $x_{1}+x_{2}+\dots+x_{n}=k$ כאשר $x_{i}\geq1$ מספרים שלמים.
פתרון:

(x_{1}-1)+(x_{2}-1)+\dots+(x_{n}-1)=k-n

נסמן: $y_{i}=x_{i}-0$ ואז $y_{i}=x_{i}-1\geq 0$ ולכן:

y_{1}+y_{2}+\dots+y_{n}=k-n

ואז לפי שני המשפטים שלמעלה:

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

דוגמה

נמצא את מספר הפתרונות של $x_{1}+x_{2}+\dots+x_n\leq k$ כאשר $x_i\geq 0$ מספרים שלמים.
נוכל תחילה לחשוב על זה כל פעם כאותה בעיה עם $k$ משתנה כך:

\sum_{i=0}^k \mathbb{C}_{n}^i=\sum_{i=0}^k \begin{pmatrix} n+i-1 \\ i \end{pmatrix}

דוגמה

נמצא כעת את מספר הפתרונות של $x_{1}+x_{2}+\dots+x_{n}=k$ כאשר $x_{i}\geq i$ מספרים שלמים.
נוכל לתחילה לכתוב זאת ככה:

(x_{1}-1)+(x_{2}-2)+(x_{3}-3)+\dots+(x_{n}-n)=k

ואז נסמן $\forall 1\leq i \leq n:\; y_{i}=x_{1}-i$ ואז $y_{1}+\dots+y_{n}=k$ ואז:

\mathbb{C}_{n}^{k-\frac{n(n+1)}{2}}

דוגמה

מספר הפתרונות של $x_{1}+x_{2}+\dots+x_{n}=k$ כאשר $0\leq x_{i}\leq m$ מספרים שלמים.
במצב בו $k\leq m$ מתקיים $\mathbb{C}_{n}^k$ הוא מספר האפשרויות.
במצב בו $m+1\leq k\leq{2}m+1$ מתקיים כי אם יותר ממשתנה אחד המשתנים $m+1\leq$ אזי נקבל כי $x_{1}+x_{2}+\dots+x_{n}\geq 2m+2>k$ וזוהי סתירה. לכן, יש רק איבר אחד שמקיים זאת. לכן, הפתרון הוא:

\mathbb{C}_{n}^k-\begin{pmatrix} n \\ 1 \end{pmatrix}\cdot \mathbb{C}_{n}^{k-(m+1)}

דוגמה (לדוגמה)

כאשר $m=1$ לכל איבר נוכל לבחור או $0$ או $1$ ולכן, לכן, מספר האפשרויות הוא מספר המילים הבינאריות באורך $n$ עם $k$ אחדים שזה $\begin{pmatrix}n\\k\end{pmatrix}$ אפשרויות.
כאשר $m=2$ יש לנו

\sum_{i=0}^{\left\lfloor \frac{k}{2} \right\rfloor} \begin{pmatrix} n \\ i \end{pmatrix}\begin{pmatrix} n-i \\ k-2i \end{pmatrix}

אפשרויות.

דוגמה

כמה תוצאות אפשריות יש להטלה של שלושה מטבעות שונים?

\begin{matrix} 000 & 100 & 010 & 001 & 110 & 011 & 101 & 111 \end{matrix}

דוגמה

כמה תוצאות אפשריות יש להטלה של שלושה מטבעות זהים?
שלוש פעמים 1, פעמיים 1 ופעם 0, פעמיים 0 ופעם 1, שלוש פעמים 0.

עקרונות בסיסיים

משפט (עקרון הסכום)

אם $X,Y$ קבוצות זרות אזי:

|X \cup Y|=|X|+|Y|

דוגמה

כמה תוצאות אפשריות ישנן להטלת קוביה $ABC$ או קוביית מספרים $1-6$ ?

X=\left\{ 1,2,3,4,5,6 \right\} \qquad Y=\left\{ A,B,C,D,E,F \right\}

|X \cup Y|=|X|+|Y|=6+6=12

ניתן להסתכל על זה גם בצורה של תמונות - כמה תמונות שונות יכולות להיות לנו מהטלת שתי הקוביות.

משפט (עקרון ההפרש)

אם $X,Y$ קבוצות סופיות ו- $Y \subseteq X$ אזי

|X \setminus Y|=|X|-|Y|

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

דוגמה

|X\setminus Y|=|X|-|Y|=8-4=4

משפט (עקרון הכפל)

אם $X,Y$ קבוצות סופיות אזי

|X\times Y|=|X|\cdot |Y|

דוגמה

כמה תוצאות אפשריות ישנן להטלת קוביית $ABC$ בנוסף להטלת קוביית מספרים $1-6$ ?

|X\times Y|=|X|\cdot |Y|=6\cdot6=36

בתיאור גרפי:
קומבי קומבי קומבי הרצאה 1 תמונה 1.png

דוגמה

נתונים שישה סטודנטים( $A-F$ )
בכמה אפשרויות ניתן לבחור מתוכם ועד של שני סטודנטים?

דוגמה

\Theta=\left\{ A,B,\dots,Z \right\} \implies |\Theta|=n=26

\Omega=\left\{ 0,1,\dots,99 \right\} \implies |\Omega|=m=100

מספר האפשרויות בלחור איבר מ- $\Theta$ הוא $26$
מספר האפשרויות לבחור איבר מ- $\Theta$ או מ- $\Omega$ הוא $|\Theta \cup\Omega|=n+m=126$
מספר האפשרויות לבחור איבר מ- $\Theta$ ואיבר שני מ- $\Omega$ הוא ${|\Theta \times\Omega|}=n\cdot m=2600$
מספר האפשרויות לבחור שני איברים שונים מ- $\Theta$ עם חשיבות לסדר $n(n-1)=26\cdot25$ ובלי חשיבות לסדר הבחירה $\frac{n(n-1)}{2}=\frac{26\cdot 25}{2}$ .
מספר האפשרויות לסדר את האיברים של $\Theta$ בשורה יש לנו $n!$ אפשרויות
זאת מכיוון שיש לנו $n$ אפשרויות לשים את האיבר הראשון ואז $n-1$ אפשרויות לאיבר השני וכך הלאה.

הגדרה 1 (תמורה)

סידור של קבוצה נקרא תמורה. עוצמת קבוצת כל התמורות של קבוצה $\left\{ 1,2,\dots,n \right\}$ מסומנת $P_{n}$ והיא שווה ל- $n!$ .

משפט

P_{n+1}=(n+1)!=(n+1)P_{n}

P_{n}=\frac{P_{n+1}}{n+1}

עבור $n=0$ מתקיים $P_{0}=\frac{P_{1}}{1}=1$ ולכן $0!=1$ .

דוגמה (המשך הדוגמה הקודמת)

|X\setminus Y|=|X|-|Y|=n!-2(n-1)!= n(n-1)!-2(n-1)!=(n-2)(n-1)!

דוגמה

כמה מספרים שלמים בין $1$ ל- $1000$ מתחלקים ב- $3$ ללא שארית? $\left\{ 3,6,9,\dots,999 \right\}$

\frac{999}{3}=\left\lfloor \frac{1000}{3}\right\rfloor=333

כמה מספרים שלמים בין $1$ ל- $n$ מתחלקים ב- $m$ ללא שארית?

\left\lfloor \frac{n}{m}\right\rfloor

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

ספירת חליפות

הגדרה 2 (מספר חליפויות אפשריות)

מספר האפשרויות לבחור $k$ איברים בלי חזרות מתוך $n$ איברים שונים כשיש חשיבות לסדר מסומן $P_{n}^k$ או $P(n,k)$ .

דוגמה

נניח ויש לנו $100$ סטודנטים ואנו רוצים לקבוע משלחת של $10$ סטודנטים שכל אחד הולך למדינה אחרת.

\begin{array}{|c|c|} \hline 1 & 2 & \dots & k\\ \hline n & n-1 & \dots & n-(k-1) \\ \hline \end{array}

כלומר מספר האפשרויות לבחור $k$ איברים מתוך $n$ איברים כפי שהוצג הוא $P_{n}^k=n(n-1)(n-2)\dots(n-k+1)=\frac{n!}{(n-k)!}$

הערה

ניתן לרשום זאת גם כ- $(n-0)(n-1)\dots$

משפט

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

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

ספירת צירופים

הגדרה 3 (מספר צירופים אפשריים)

דוגמה

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

\Downarrow

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

משפט

מספר האפשרויות לבחור $k$ איברים מתוך $n$ איברים שונים כשאין חשיבות לסדר ובלי חזרות הוא

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

משפט (תכונות של

C_{n}^k

)

P_{n}^k =\begin{pmatrix} n \\ k \end{pmatrix}k!

\begin{pmatrix} n \\ k \end{pmatrix}=\begin{pmatrix} n \\ n-k \end{pmatrix}=\frac{n(n-1)\dots(n-k+1)}{k!}

\begin{pmatrix} n \\ 0 \end{pmatrix}=\begin{pmatrix} n \\ n \end{pmatrix}=1

אם $m>n$ או $m<0$ אזי $\begin{pmatrix}n\\ m\end{pmatrix}=0$

סופרים את שאר הדברים

בעייה נוספת היא לבחור $k$ איברים עם חזרות מתוך $n$ איברים שונים(נניח $n=100$ ) כשיש חשיבות לסדר.
נסתכל על הטבלה:

\begin{array}{|c|c|} \hline 1 & 2 & 3 & 4 & 5 & \dots & k-3 & k-2 & k-1 & k \\ \hline 100 & 100 & 100 & 100 & 100 & \dots & 100 & 100 & 100 & 100 \\ \hline \end{array}

לבסוף נגלה כי:

משפט

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

n^k

הערה

שבוע הבא נראה איך מוצאים את האופציה האחרונה(בלי חשיבות לסדר ועם חזרות) וזוהי בעיה פחות טרוויאלית.

דוגמה

מילה בינארית היא סדרה סופית של $0$ ו- $1$ .
כמה מילים בינאריות באורך $n$ בהן $1$ מופיע בדיוק $k$ פעמים?

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

011010010111 \longrightarrow \left\{ 2,3,5,8,10,11,12 \right\}

x\cdot (n-k)!\cdot k!=n! \implies x= \frac{n!}{k!(n-k)!}=\begin{pmatrix} n \\ k \end{pmatrix}

הגדרה 4 (מילה)

מילה מעל אלפבית $A$ היא סדרה סופית של אותיות מ- $A$ .

דוגמה

כמה מילים באורך $n$ מכילות $k_{1}$ פעמים $1$ ו- $k_{2}$ פעמים 2 בנוסף ל- $k_{3}$ פעמים 3 ו- $k_{4}$ פעמים $4$ כך ש- $n=k_{1}+k_{2}+k_{3}+k_{4}$ ?

\R{\text{מספר האפשרויות}}=\begin{pmatrix} n \\ k_{1} \end{pmatrix}\begin{pmatrix} n-k_{1} \\ k_{2} \end{pmatrix}\begin{pmatrix} n-k_{1}-k_{2} \\ k_{3} \end{pmatrix}\begin{pmatrix} n-k_{1}-k_{2}-k_{3} \\ k_{4} \end{pmatrix}=\frac{n!}{k_{1}!(n-k_{1})!}\cdot \frac{(n-k_{1})!}{k_{2}!(n-k_{1}-k_{2})!}\cdot

\frac{(n-k_{1}-k_{2})!}{k_{3}!(n-k_{1}-k_{2}-k_{3})!}\cdot \frac{(n-k_{1}-k_{2}-k_{3})!}{k_{4}!}=\frac{n!}{k_{1}!k_{2}!k_{3}!k_{4}!}

כשאין חשיבות לסדר ויש חזרות

אנחנו נסמן זאת כך:

\mathbb{C}^k_{n}=\left( \!\!\! \begin{pmatrix} n \\ k \end{pmatrix} \!\!\! \right)

דוגמה

עבור בעיה כללית נבצע את אותו הדבר ונקבל כי מספר הפתרונות: $\begin{pmatrix}n+k-1\\ k\end{pmatrix}$ .

משפט

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

משפט

הערכים הבאים שווים:

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

דוגמה

מספר הפתרונות של $x_{1}+x_{2}+\dots+x_{n}=k$ כאשר $x_{i}\geq1$ מספרים שלמים.
פתרון:

(x_{1}-1)+(x_{2}-1)+\dots+(x_{n}-1)=k-n

נסמן: $y_{i}=x_{i}-0$ ואז $y_{i}=x_{i}-1\geq 0$ ולכן:

y_{1}+y_{2}+\dots+y_{n}=k-n

ואז לפי שני המשפטים שלמעלה:

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

דוגמה

\sum_{i=0}^k \mathbb{C}_{n}^i=\sum_{i=0}^k \begin{pmatrix} n+i-1 \\ i \end{pmatrix}

דוגמה

נמצא כעת את מספר הפתרונות של $x_{1}+x_{2}+\dots+x_{n}=k$ כאשר $x_{i}\geq i$ מספרים שלמים.
נוכל לתחילה לכתוב זאת ככה:

(x_{1}-1)+(x_{2}-2)+(x_{3}-3)+\dots+(x_{n}-n)=k

ואז נסמן $\forall 1\leq i \leq n:\; y_{i}=x_{1}-i$ ואז $y_{1}+\dots+y_{n}=k$ ואז:

\mathbb{C}_{n}^{k-\frac{n(n+1)}{2}}

דוגמה

\mathbb{C}_{n}^k-\begin{pmatrix} n \\ 1 \end{pmatrix}\cdot \mathbb{C}_{n}^{k-(m+1)}

דוגמה (לדוגמה)

\sum_{i=0}^{\left\lfloor \frac{k}{2} \right\rfloor} \begin{pmatrix} n \\ i \end{pmatrix}\begin{pmatrix} n-i \\ k-2i \end{pmatrix}

אפשרויות.

1 - בעיות ספריה בסיסיות

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

בעיות ספריה בסיסיות

1 - בעיות ספריה בסיסיות

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

בעיות ספריה בסיסיות

עקרונות בסיסיים

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

ספירת חליפות

ספירת צירופים

סופרים את שאר הדברים

כשאין חשיבות לסדר ויש חזרות

עקרונות בסיסיים

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

ספירת חליפות

ספירת צירופים

סופרים את שאר הדברים

כשאין חשיבות לסדר ויש חזרות