עקרון ההכלה וההפרדה

מתוך ויקיפדיה, האנציקלופדיה החופשית

יש לך הודעות חדשות (השווה לגרסה הקודמת).

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

[עריכה] הגדרה פורמלית

תהא קבוצה של $\!\, N$ איברים שונים, ויהיו $\!\, m$ תכונות שונות שיכולות להיות לאותם איברים. נסמן $\!\, p(i)$ את התכונה ה $\!\, i$ . כעת נסמן $\!\, N_{i_1,i_2,\dots,i_k}$ את מספר האיברים שעבורם מתקיימות (לפחות) התכונות $\!\, p(i_1),\dots,p(i_k)$ .

בהינתן אלו, הרי ש $\!\, N(0)$ , מספר האיברים שלא מקיימים אף אחת מהתכונות, נתון על ידי הנוסחה: $\!\, N(0)=N-\sum N_i+\sum_{i_1<i_2}N_{i_1i_2}+\dots+(-1)^s\sum_{i_1<i_2<\dots<i_s}N_{i_1i_2\dots i_s}+\dots+(-1)^nN_{1 2\dots n}$

דרך קומפקטית יותר לנסח את הנוסחה היא זו: נסמן ב- $\ W(r)$ את הסכום $\ W(r)=\sum_{i_1<i_2<\dots<i_r} N(i_1,i_2,\dots,i_r)$ ואז נוסחת ההכלה וההפרדה נתונה על ידי $\ N(0)=\sum_{r=0}^n (-1)^r W(r)$ .

[עריכה] דוגמה

נראה כאן כיצד ניתן לחשב את מספר הפרות הסדר על $\ n$ איברים. מבחינה לא פורמלית ניתן לתאר הפרות סדר באמצעות הסיפור הבא:

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

מבחינה פורמלית יותר, נניח כי נתונים לנו המספרים $\ 1,2,\dots,n$ . הפרת סדר עליהם היא תמורה שלהם $\ a_1,a_2,\dots,a_n$ כך שמתקיים $\ \forall i:a_i\ne i$ .

כדי להשתמש בעיקרון ההכלה וההפרדה נבחר בתור $\ p(i)$ את התכונה "המספר $\ i$ נמצא במקום $\ i$ ".

אם בחרנו עבור $\ r$ מספרים שהם יהיו במקומם "הנכון", נותרו לנו $\ n-r$ מספרים שניתן לערבב בכל צורה שנרצה. אין צורך לדרוש שהם יהיו במקום "לא נכון" - זה בדיוק הרעיון שמאחורי עיקרון ההכלה וההפרדה. אנו יכולים לספור גם מקרים שבהם חלק מהמספרים הנותרים נמצאים במקום הנכון, מכיוון שנוריד את המקרים המיותרים בהמשך הספירה.

לכן: $\ W(r)={n\choose r}(n-r)!$ (קודם כל בוחרים את המספרים שיהיו בהכרח במקומם הנכון, ואחר מערבבים את היתר).

לכן, על פי עיקרון ההכלה וההפרדה:

$\ N(0)=\sum_{r=0}^n (-1)^r W(r)=\sum_{r=0}^n (-1)^r {n\choose r}(n-r)!=\sum_{r=0}^n (-1)^r \frac{n!}{r!}$ .

כעת, אם נרצה לחשב את ההסתברות שתתקבל הפרת סדר, יש לחלק את מספר הפרות הסדר (שנתון על ידי הנוסחה) במספר התמורות הכולל של איברים, $\ n!$ . נקבל את הנוסחה: $\ \sum_{r=0}^n \frac{(-1)^r}{r!}$ .

על פי הגדרת פונקציית האקספוננט, נקבל:

$\ \lim_{n\to\infty}\sum_{r=0}^n \frac{(-1)^r}{r!}=e^{-1}=\frac{1}{e}$ . כלומר, ההסתברות לקבלת הפרת סדר בערבוב של $\ n$ מספרים שואפת ל- $\ \frac{1}{e}$ .

[עריכה] הוכחה

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

כל איבר שלא מקיים אף תכונה נספר רק פעם אחת, במחובר הראשון בסכום, $\!\, N$ .

יהי כעת איבר שמקיים בדיוק $\!\, r$ תכונות. אז לכל $\!\, s\le r$ , איבר זה נספר במחובר $\!\, \sum_{i_1<i_2<\dots<i_s}N_{i_1i_2\dots i_s}$ בדיוק $\!\, r\choose s$ פעמים. (מספר האפשרויות שלנו לבחור $\!\, s$ תכונות שונות מסך $\!\, r$ התכונות שיש לאיבר שלנו, ולספור אותו בגלל אותן תכונות).

אם כך, עבור איבר זה נקבל את הסכום הבא:

$\!\, {r\choose 0} -{r\choose 1}+\dots+\left(-1\right)^s {r\choose s}+\dots+\left(-1\right)^r {r\choose r}=\sum_{s=0}^r\left(-1\right)^s {r\choose s}$ .

סכום זה הוא בדיוק נוסחת הבינום, $\!\, \left(a+b\right)^r$ כאשר $\!\, a=1,b=-1$ , ולכן הסכום הכולל הוא $\!\, \left(1-1\right)^r=0$ . כך לכל איבר שמקיים לפחות אחת מהתכונות, ולכן מספר האיברים שנספרים הוא בדיוק מספרם של אלו שאינם מקיימים אף אחת מהתכונות.