יחידה 1: שיטות ספירה בסיסיות

עקרונות ספירה

עקרון הכפל

אם ניתן לבצע פעולה $A$ ב- $m$ דרכים, ולאחריה פעולה $B$ ב- $n$ דרכים, אז ניתן לבצע את שתי הפעולות ב- $m \cdot n$ דרכים.

עקרון החיבור

אם ניתן לבצע פעולה $A$ ב- $m$ דרכים או פעולה $B$ ב- $n$ דרכים (והפעולות זרות), אז ניתן לבצע אחת מהפעולות ב- $m + n$ דרכים.

תמורות (Permutations)

הגדרה: תמורה

תמורה של $n$ איברים היא סידור של כל האיברים בסדר מסוים.

מספר התמורות של $n$ איברים: $n!$

תמורות עם חזרות

מספר הדרכים לסדר $n$ איברים כאשר יש $k$ סוגים עם $n_1, n_2, \ldots, n_k$ חזרות:

$\frac{n!}{n_1! \cdot n_2! \cdot \ldots \cdot n_k!}$

צירופים (Combinations)

הגדרה: צירוף

צירוף הוא בחירת $k$ איברים מתוך $n$ איברים, כאשר הסדר לא חשוב.

$\binom{n}{k} = \frac{n!}{k!(n-k)!}$

תרגילים (תרגול 1)

תרגיל 1 (מועד א', סמסטר ב', 2023/4)

נגדיר מטריצה-בראש-אחר כמטריצה בינארית (מקבלת ערכים מ- $\{0,1\}$ ) עם $n$ שורות ו- $m$ עמודות שבהן השורה הראשונה אינה זהה לאף שורה אחרת. עבור $n, m$ כלשהם, כמה מטריצות בראש אחר ישנן?

פתרון

נבנה את המטריצה בעזרת חוק הכפל. נבחר את השורה הראשונה — מתוך הכפל, ישנן $2^m$ דרכים לעשות זאת.

ואז לכל שורה אחרת יש $2^m - 1$ אפשרויות (כל שורה בינארית חוץ מהשורה הראשונה).

סה"כ:

$2^m (2^m - 1)^{n-1}$

תרגיל 2 (מועד ב', סמסטר א', 2024/5)

יהא $n$ טבעי ו- $\pi$ תמורה על $[n]$ . אינדקס $k \in [n]$ נקרא משפיע ב- $\pi$ אם מתקיים התנאי הבא: אם $k$ נקודת שבת של $\pi$ אז לכל $j > k$ מתקיים שגם $j$ היא נקודת שבת של $\pi$ . יהי אינדקס $k \in [n]$ כלשהו. כמה תמורות של $[n]$ ישנן בהן $k$ משפיע?

פתרון

כדי ש- $k$ יהי משפיע צריכים להתקיים אחד מהמקרים הזרים הבאים:

$k$ אינו נקודת שבת
$k$ כן נקודת שבת, וכך גם כל $j > k$

מקרה 1: נספור את כל התמורות שבהן $k$ אינו נקודת שבת. ישנן $n!$ תמורות בסך הכל, ומתוכן $(n-1)!$ תמורות שבהן $k$ כן נקודת שבת (כי קיבענו $\pi(k)=k$ ונותר לבחור תמורה על $n-1$ איברים). לכן:

$n! - (n-1)!$

מקרה 2: התמונה של $k, k+1, \ldots, n$ נקבעת ביחידות (כולם נקודות שבת), ונותר לבחור תמורה על $1, \ldots, k-1$ . ישנן $(k-1)!$ אפשרויות.

סה"כ (מעיקרון החיבור, כי המקרים זרים):

$n! - (n-1)! + (k-1)!$

עקרונות ספירה

עקרון הכפל

אם ניתן לבצע פעולה $A$ ב- $m$ דרכים, ולאחריה פעולה $B$ ב- $n$ דרכים, אז ניתן לבצע את שתי הפעולות ב- $m \cdot n$ דרכים.

עקרון החיבור

אם ניתן לבצע פעולה $A$ ב- $m$ דרכים או פעולה $B$ ב- $n$ דרכים (והפעולות זרות), אז ניתן לבצע אחת מהפעולות ב- $m + n$ דרכים.

תמורות (Permutations)

הגדרה: תמורה

תמורה של $n$ איברים היא סידור של כל האיברים בסדר מסוים.

מספר התמורות של $n$ איברים: $n!$

תמורות עם חזרות

מספר הדרכים לסדר

n

איברים כאשר יש

k

סוגים עם

n_1, n_2, \ldots, n_k

חזרות:

\frac{n!}{n_1! \cdot n_2! \cdot \ldots \cdot n_k!}

תרגילים (תרגול 1)

תרגיל 1 (מועד א', סמסטר ב', 2023/4)

נגדיר מטריצה-בראש-אחר כמטריצה בינארית (מקבלת ערכים מ-

\{0,1\}

) עם

n

שורות ו-

m

עמודות שבהן השורה הראשונה אינה זהה לאף שורה אחרת. עבור

n, m

כלשהם, כמה מטריצות בראש אחר ישנן?

פתרון

נבנה את המטריצה בעזרת חוק הכפל. נבחר את השורה הראשונה — מתוך הכפל, ישנן $2^m$ דרכים לעשות זאת.

ואז לכל שורה אחרת יש $2^m - 1$ אפשרויות (כל שורה בינארית חוץ מהשורה הראשונה).

סה"כ:

$2^m (2^m - 1)^{n-1}$

תרגיל 2 (מועד ב', סמסטר א', 2024/5)

יהא

n

טבעי ו-

\pi

תמורה על

[n]

. אינדקס

k \in [n]

נקרא משפיע ב-

\pi

אם מתקיים התנאי הבא: אם

k

נקודת שבת של

\pi

אז לכל

j > k

מתקיים שגם

j

היא נקודת שבת של

\pi

. יהי אינדקס

k \in [n]

כלשהו. כמה תמורות של

[n]

ישנן בהן

k

משפיע?

פתרון

כדי ש- $k$ יהי משפיע צריכים להתקיים אחד מהמקרים הזרים הבאים:

$k$ אינו נקודת שבת
$k$ כן נקודת שבת, וכך גם כל $j > k$

$n! - (n-1)!$

סה"כ (מעיקרון החיבור, כי המקרים זרים):

$n! - (n-1)! + (k-1)!$