מתמטיקה דיסקרטית ח (2023 — מרחב למידה אישי

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

יסודות הספירה – העקרונות הבסיסיים

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

עקרון הכפל: אם פעולה אחת יכולה להתבצע ב-n₁ דרכים, ופעולה שנייה (בלתי תלויה) יכולה להתבצע ב-n₂ דרכים, אז מספר הדרכים לבצע את שתי הפעולות ברצף הוא n₁ * n₂. עקרון זה מתרחב לכל מספר של פעולות.

עקרון החיבור: אם פעולה אחת יכולה להתבצע ב-n₁ דרכים, או פעולה שנייה (שאינה חופפת לפעולה הראשונה) יכולה להתבצע ב-n₂ דרכים, אז מספר הדרכים לבצע אחת מהפעולות הוא n₁ + n₂. עקרון זה דורש שקבוצות הדרכים יהיו זרות.

סידורים ובחירות – פרמוטציות וקומבינציות

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

פרמוטציות (תמורות)

פרמוטציה היא סידור של עצמים שבו הסדר חשוב.

פרמוטציה: סידור של k עצמים מתוך n עצמים. הסדר קובע.

פרמוטציות ללא חזרות: מספר הדרכים לסדר k עצמים מתוך n עצמים שונים (כאשר כל עצם נבחר פעם אחת לכל היותר) הוא P(n, k) = n! / (n-k)!. אם k=n, אז זה n!.
פרמוטציות עם חזרות: מספר הדרכים לסדר k עצמים מתוך n סוגים של עצמים (כאשר ניתן לבחור כל עצם מספר פעמים) הוא n^k.

קומבינציות (צירופים)

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

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

קומבינציות ללא חזרות: מספר הדרכים לבחור k עצמים מתוך n עצמים שונים (ללא חזרות, ללא חשיבות לסדר) הוא C(n, k) = n! / (k! * (n-k)!). זהו המקדם הבינומי $\binom{n}{k}$.
קומבינציות עם חזרות: מספר הדרכים לבחור k עצמים מתוך n סוגים של עצמים (עם חזרות, ללא חשיבות לסדר) הוא $\binom{n+k-1}{k}$. שיטה זו ידועה גם כ"כוכבים ומחיצות".

פרמוטציות ללא חזרות

בחירת k עצמים מתוך n שונים, עם חשיבות לסדר, ללא חזרות. נוסחה: P(n,k) = n!/(n-k)!

פרמוטציות עם חזרות

בחירת k עצמים מתוך n סוגים, עם חשיבות לסדר, עם חזרות. נוסחה: n^k

קומבינציות ללא חזרות

בחירת k עצמים מתוך n שונים, ללא חשיבות לסדר, ללא חזרות. נוסחה: C(n,k) = $\binom{n}{k}$

קומבינציות עם חזרות

בחירת k עצמים מתוך n סוגים, ללא חשיבות לסדר, עם חזרות. נוסחה: $\binom{n+k-1}{k}$ (כוכבים ומחיצות)

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

עקרון ההכלה וההפרדה (Inclusion-Exclusion Principle)

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

עקרון ההכלה וההפרדה: עבור קבוצות A₁, A₂, ..., A_n, מתקיים: $| \bigcup_{i=1}^{n} A_i | = \sum |A_i| - \sum |A_i \cap A_j| + \sum |A_i \cap A_j \cap A_k| - \dots + (-1)^{n-1} | \bigcap_{i=1}^{n} A_i |$.

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

עקרון שובך היונים (Pigeonhole Principle)

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

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

גרסה מורחבת: אם מכניסים n עצמים ל-m תאים, אז לפחות תא אחד מכיל לפחות $\lceil n/m \rceil$ עצמים.

אסטרטגיות לפתרון בעיות קומבינטוריות

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

שאלות לדיון

בכמה דרכים ניתן לחלק 10 כדורים זהים ל-4 תאים שונים, כך שאף תא לא יישאר ריק?
כמה מספרים טבעיים קטנים מ-1000 מתחלקים ב-3 או ב-5 אך לא ב-15?
בכמה דרכים ניתן לסדר את האותיות במילה "TECHNION" כך שכל האותיות T, E, C יופיעו ברצף (בסדר כלשהו)?
הסבירו מתי נכון להשתמש ב"כוכבים ומחיצות" ומתי בפרמוטציות עם חזרות, והדגימו עם דוגמה קצרה לכל אחד.

נקודות לתשובת מודל

לשאלה: "בכמה דרכים ניתן לחלק 10 כדורים זהים ל-4 תאים שונים, כך שאף תא לא יישאר ריק?"

זיהוי הבעיה: זוהי בעיית חלוקת עצמים זהים לתאים שונים, עם אילוץ שכל תא יקבל לפחות עצם אחד. זהו מקרה קלאסי של קומבינציות עם חזרות (כוכבים ומחיצות) עם טיפול מקדים לאילוץ.
טיפול באילוץ: כדי להבטיח שאף תא לא יישאר ריק, נחלק תחילה כדור אחד לכל אחד מ-4 התאים. נותרו לנו 10 - 4 = 6 כדורים.
יישום כוכבים ומחיצות: כעת עלינו לחלק את 6 הכדורים הנותרים ל-4 התאים, ללא אילוצים נוספים (מותר לתא לקבל 0 כדורים נוספים).
- מספר הכדורים הנותרים (k) = 6.
- מספר התאים (n) = 4.
- הנוסחה היא $\binom{n+k-1}{k}$ או $\binom{n+k-1}{n-1}$.
חישוב: $\binom{4+6-1}{6} = \binom{9}{6} = \binom{9}{3} = \frac{9 \times 8 \times 7}{3 \times 2 \times 1} = 3 \times 4 \times 7 = 84$.
מסקנה: ישנן 84 דרכים לחלק 10 כדורים זהים ל-4 תאים שונים כך שאף תא לא יישאר ריק.

מצאתם טעות או שחסר משהו?