עקרון ההכלה וההפרדה, ואז הכללה והפחדה

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

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

קומבינטוריקה אנומרטיבית היא התחום המתמטי שעוסק, פחות או יותר, בבעיה הבאה: “הנה לך קבוצה סופית, כמה איברים יש בה?”, כאשר לרוב הקבוצה הזו תלויה באיזה פרמטר \( n \) ואנו רוצים את התשובה כפונקציה של \( n \). הנה כמה דוגמאות לבעיות שבכולן נטפל בקרוב: קבוצת המספרים הטבעיים בין \( 1 \) ל-\( n \) שאינם מתחלקים ב-2, 3 או 5; קבוצת המספרים בין 1 ל-\( n \) שזרים ל-\( n \) (כלומר, אין להם מחלקים טבעיים משותפים הגדולים מ-1), וקבוצת הפרות הסדר על \( n \) איברים - בלשון ציורית, מספר הדרכים שבהן יכול דוור מבולבל (אם אנחנו שונאים את ניומן מסיינפלד) או מזכירה מבולבלת (אם אנחנו שונאים נשים) לחלק \( n \) מכתבים ל-\( n \) האנשים שאמורים לקבל אותם באופן כזה שאף מכתב לא יגיע ליעדו (למשל, אם האנשים הם 1,2,3 אז אפשרות אחת היא שהמכתב של 3 יגיע ל-1, שהמכתב של 2 יגיע ל-3, ושהמכתב של 1 יגיע ל-2).

בואו נתחיל מגרסה עוד יותר פשוטה של הבעיה הראשונה: כמה מספרים בין 1 ל-100 כן מתחלקים ב-2 או ב-3? ובכן, בדיוק 50 מספרים מתחלקים ב-2 - כל הזוגיים. כמו כן, 33 מתחלקים ב-3; כל המספרים שהם כפולות של 3 עד 99, ו-100 לא עוזר לנו כי אינו מתחלק ב-3. קצת מחשבה מראה לנו את הנוסחה הכללית: מספרים מ-\( 1 \) ועד \( n \) שמתחלקים ב-\( k \) יש בדיוק, אבל בדיוק, \( \left\lfloor \frac{n}{k}\right\rfloor \), כשהקווים מייצגים ערך שלם תחתון: אם התקבלה תוצאה שברית, מעגלים למטה למספר השלם הקרוב.

אם כן, הפיתוי גדול לומר שיש \( 50+33=83 \) מספרים בין 1 ו-100 שמתחלקים ב-2 או ב-3. אבל ספירה מהירה תראה שזה לא נכון. בעצם, עזבו אתכם ממספרים בין 1 ל-100 שקשה לספור; אם ננסה באותה שיטה לספור מספרים בין 1 ל-10 נקבל \( 8 \) מספרים, אבל בבירור יש רק 7: \( \left\{ 2,3,4,6,8,9,10\right\} \). איפה הטעות שלנו? במספר המעצבן 6, שמתחלק בו זמנית גם ב-2 וגם ב-3. ספרנו אותו פעמיים: פעם אחת כחבר בקבוצה \( \left\{ 2,4,6,8,10\right\} \) של מספרים שמתחלקים ב-2, ופעם אחת בקבוצה \( \left\{ 3,6,9\right\} \) של מספרים שמתחלקים ב-3. את הספירה הכפולה הזו צריך לתקן - פשוט נחסיר 1 מהתוצאה.

עבור מספרים בין 1 ל-100 הרעיון דומה; יש 83 מספרים פחות כמות המספרים בין 1 ל-100 שמתחלקים גם ב-2 וגם ב-3. למזלנו קל לדעת מיהם - אלו בדיוק המספרים שמתחלקים 6, כלומר \( \left\lfloor \frac{100}{6}\right\rfloor =16 \). קיבלנו שיש \( 50+33-16=67 \) מספרים בין 1 ל-100 שמתחלקים או ב-2, או ב-3, או בשניהם.

את הרעיון הכללי אפשר לנסח כך: אם \( A,B \) הן קבוצות, אז \( \left|A\cup B\right|=\left|A\right|+\left|B\right|-\left|A\cap B\right| \) - גודל הקבוצה \( A\cup B \) שמכילה את כל האיברים של \( A,B \) הוא כסכום גדלי הקבוצות \( A,B \) פחות הגודל של הקבוצה \( A\cap B \) של איברים ששייכים הן ל-\( A \) והן ל-\( B \). השלב הבא הוא לנסח את המשפט עבור שלוש קבוצות, \( A,B,C \). הניחוש הראשוני הוא לומר ש-

מכאן כבר אפשר לנחש את המקרה הכללי: אם יש לנו קבוצות \( A_{1},\dots,A_{k} \) ואנו רוצים לדעת מה הגודל של \( \bigcup_{i=1}^{k}A_{i} \), קודם כל נסכום את הגדלים של כל הקבוצות, אחר כך נחסיר את הגודל של כל החיתוכים של שתי קבוצות, נחבר את הגודל של חיתוכים של שלוש, נחסיר את הגודל של חיתוכים של ארבע… אני אומר את זה מילולית כי לכתוב את זה בנוסחה - ובכן, איך נאמר זאת בעדינות - זה כואב. הנה הנוסחה:

\( \left|\bigcup_{i=1}^{n}A_{i}\right|=\sum_{i=1}^{n}\left|A_{i}\right|-\sum_{1\le i<j\le n}\left|A_{i}\cap A_{j}\right|+\dots+\left(-1\right)^{n+1}\left|\bigcap_{i=1}^{n}A_{i}\right| \)

לקצרנים שבינינו, אפשר גם עם סכום כפול:

\( \left|\bigcup_{i=1}^{n}A_{i}\right|=\sum_{t=1}^{n}\sum_{1\le i_{1}<i_{2}<\dots<i_{t}\le n}\left(-1\right)^{t+1}\left|\bigcap_{j=1}^{t}A_{i_{j}}\right| \)

לא נעים כל כך, אבל העיקרון עצמו ברור למדי. עם זאת, צריך גם להוכיח שהוא עובד. הרעיון הוא להסתכל על איבר כלשהו \( x\in\bigcup_{i=1}^{n}A_{i} \) ולשאול את עצמנו - מה הוא תורם לאגף ימין, ומה הוא תורם לאגף שמאל? לאגף שמאל הוא תורם בדיוק 1; אגף ימין קצת יותר מסובך. נניח ש-\( x \) נמצא בדיוק ב-\( k \) קבוצות, אז לכל \( t>k \), פשוט לא ייתכן ש-\( x\in\bigcap_{j=1}^{t}A_{i_{j}} \) כי אנחנו חותכים פה יותר קבוצות מאשר יש קבוצות שמכילות את \( x \) ולכן הוא לא בחיתוך. לכן מה שרלוונטי מראש הוא רק \( t\le k \), וגם אז - רק חיתוכים \( \bigcap_{j=1}^{t}A_{i_{j}} \) שבהם כל הקבוצות כוללות את \( x \), כלומר כל הקבוצות נלקחות מתוך \( k \) הקבוצות שכוללות את \( x \) מלכתחילה. המספר שלהן הוא מה שמסמנים כ-\( {k \choose t} \): מספר האפשרויות לבחור \( t \) מתוך \( k \). זה אומר ש-\( x \) תורם לסכום באגף ימין בדיוק את תת-הסכום הבא:

\( \sum_{t=1}^{k}{k \choose t}\left(-1\right)^{t+1} \)

כדי לחשב את הסכום הזה משתמשים בנוסחת הבינום של ניוטון, שקל לראות ממנה שמתקיים \( 0=\left(1-1\right)^{k}=\sum_{t=0}^{k}{k \choose t}\left(-1\right)^{t} \). לכן אנו מקבלים:

\( \sum_{t=1}^{k}{k \choose t}\left(-1\right)^{t}=\sum_{t=0}^{k}{k \choose t}\left(-1\right)^{t+1}+1=1-\sum_{t=0}^{k}{k \choose t}\left(-1\right)^{t}=1 \)

כפי שרצינו.

ואיך עושים איתו דברים מעניינים

סיימנו את ההוכחה ואפשר לעבור לאקשן - פתרון של דברים אמיתיים. נתחיל עם המספרים בין 1 ל-\( n \) שאינם מתחלקים ב-\( 2 \) או \( 3 \) או \( 5 \): כאן הקבוצות הן של המספרים שכן מתחלקים ב-2, וכן מתחלקים ב-3, וכן מתחלקים ב-5, ואנחנו רוצים לחסר את זה מהקבוצה של כלל המספרים, שהיא מגודל \( n \). לכן נקבל:

\( n-\left(\left\lfloor \frac{n}{2}\right\rfloor +\left\lfloor \frac{n}{3}\right\rfloor +\left\lfloor \frac{n}{5}\right\rfloor \right)+\left(\left\lfloor \frac{n}{6}\right\rfloor +\left\lfloor \frac{n}{10}\right\rfloor +\left\lfloor \frac{n}{15}\right\rfloor \right)-\left\lfloor \frac{n}{30}\right\rfloor \)

חייבים להודות שהנוסחה הזו לא נראית הכי מלהיבה בעולם; אבל חשבו לרגע על הדרך הנאיבית לחשב את המספר הזה - לעבור על כל המספרים מ-\( 1 \) עד \( n \) ולכל אחד לבדוק אם הוא מתחלק ב-2 או 3 או 5. אם \( n \) קטן זה לא נורא, אבל מה אם \( n=10^{100} \)? במקרה הזה האלגוריתם שלנו לעולם לא יסתיים, ואילו בעזרת הנוסחה שלנו צריך יהיה לבצע 7 פעולות חילוק ולחבר/לחסר את התוצאות וזהו, כלומר החישוב יסתיים בחלקיקי שניה גם אם \( n \) מפלצתי בגודלו. זו המחשה ראשונה לכוח שבהכלה והפרדה.

בואו נעבור לדוגמה השניה: עבור טבעי \( n \), \( \varphi\left(n\right) \) (“פונקצית אוילר”) מסמן את מספרם של המספרים הטבעיים בין 1 ל-\( n \) שזרים ל-\( n \), כלומר שהמספר היחיד שמחלק את שניהם הוא \( 1 \) עצמו. למשל, עבור \( 6 \), המספרים היחידים שקטנים ממנו וזרים לו הם 1 ו-5 ולכן \( \varphi\left(6\right)=2 \); עבור \( 8 \) אלו הם \( 1,3,5,7 \) ולכן \( \varphi\left(8\right)=4 \), וכן הלאה. אם תסתכלו בגרף של הפונקציה הזו תראו שהיא מתנהגת בצורה די מטורללת - כל הזמן קופצת בין ערכים קטנים לגדולים. נקודות השיא הן בראשוניים (מספרים שמתחלקים רק ב-1 ובעצמם): לכל מספר ראשוני \( p \) מתקיים \( \varphi\left(p\right)=p-1 \) ולכן הערכים הגדולים ביותר של \( \varphi \) יתקבלו על הראשוניים, שהם עצמם מפוזרים בצורה שנראית כמעט אקראית.

ועם זאת, יש נוסחה ל-\( \varphi\left(n\right) \), שמתבססת על כך שאנו יודעים בדיוק מהם הראשוניים שמחלקים את \( n \). יש לנוסחה הזו מספר הוכחות והאהובה עלי עושה שימוש במשפט חשוב למדי מאלגברה - “משפט השאריות הסיני”. לא נדבר על זה בכלל הפעם, ובמקום זאת נראה איך גישת ההכלה וההפרדה מחסלת גם היא את הבעיה בקלות.

האבחנה האלגברית שבבסיס העניין היא שאם \( n \) ו-\( m \) לא זרים, אז קיים ראשוני \( p \) כלשהו שמחלק את שניהם. נניח שהמחלקים הראשוניים השונים של \( n \) הם בדיוק \( p_{1},\dots,p_{k} \), אז הקבוצה \( A_{i} \) שלנו הפעם תהיה “קבוצת כל המספרים הטבעיים הקטנים או שווים ל-\( n \) שמתחלקים ב-\( p_{i} \)”. את הגודל המדויק של הקבוצה הזו אנחנו יודעים - הוא בדיוק \( \frac{n}{p_{i}} \), מהנימוקים שנתתי קודם. וכמות המספרים שמתחלקים בשני ראשוניים \( p_{i},p_{j} \) היא \( \frac{n}{p_{i}p_{j}} \) וכן הלאה. אז הכלה והפרדה נותנת את הדבר הבא:

\( \varphi\left(n\right)=n-\sum_{i}\frac{n}{p_{i}}+\sum_{i,j}\frac{n}{p_{i}p_{j}}-\dots+\left(-1\right)^{k}\frac{n}{p_{1}\cdots p_{k}} \)

על פניו, לא ברור מה הנוסחה הזו עזרה לנו, אבל שימו לב לכך ש-\( n \) הוא גורם בכל אחד מהמחוברים, כך שניתן להוציא אותו החוצה ולהיוותר עם סכום מהצורה \( \left(1-\sum\frac{1}{p_{i}}+\sum\frac{1}{p_{i}p_{j}}-\dots+\left(-1\right)^{k}\frac{1}{p_{1}\cdots p_{k}}\right) \). מה שטוב בסכום הזה, שעדיין נראה מפלצתי, הוא שאפשר לכתוב אותו בצורה הרבה יותר פשוטה ומסודרת כמכפלה: \( \prod_{i=1}^{k}\left(1-\frac{1}{p_{i}}\right) \). כדי לראות את זה, שימו לב שאם פותחים את המכפלה הזו, מקבלים סכום של איברים כך שכל איבר הוא בעצמו מכפלה, שכל איבר בה הוא או \( 1 \) או \( -\frac{1}{p_{i}} \) (הדרך הפשוטה ביותר לראות זאת - נסו לעשות זאת עם שני ראשוניים בלבד).

אם כן, קיבלנו את הנוסחה \( \varphi\left(n\right)=n\prod_{p|n}\left(1-\frac{1}{p}\right) \) (\( p|n \) פירושו “מכפלה שנלקחת על כל הראשוניים \( p \) שמחלקים את \( n \)”) שהיא קלה ביותר לחישוב, אם יודעים מיהם ה-\( p \)-ים המתאימים (ולדעת מי הם - זו כבר בעיה לא פשוטה כלל).

בואו נעבור עכשיו להפרות סדר, שגם בהן הכלה והפרדה נותנת נוסחה סגורה, אבל מרשימה אפילו יותר מאשר במקרה הקודם שכן היא לא תכלול שום מכפלה ושום סכום, בזכות תעלול מחדו”א שנשתמש בו. הפרת סדר היא בבסיסה תמורה - סידור בשורה של המספרים מ-\( 1 \) עד \( n \). יש באופן כללי \( n!=1\cdot2\cdots n \) תמורות; מהן אנחנו רוצים לחסר את מספר התמורות שבהן יש לפחות אינדקס אחד \( i \) כך שהמספר במקום ה-\( i \) הוא \( i \) עצמו (למשל, \( 4132 \) היא תמורה כזו עם האינדקס \( i=3 \)).

למרבה המזל, את החישובים כאן קל מאוד לבצע. מספר התמורות שבהן \( k \) איברים ספציפיים נמצאים במקום הנכון שלהם הוא כמספר האפשרויות לסדר את כל יתר \( n-k \) האיברים בסדר שרירותי כלשהו, כלומר \( \left(n-k\right)! \). שימו לב לכך שאני מרשה לאיברים נוספים פרט ל-\( k \) האיברים הספציפיים להיות במקום הנכון שלהם; אני פשוט לא דורש זאת במפורש. לכן \( \left(n-k\right)! \) אינו מספר התמורות שבהן בדיוק \( k \) איברים נמצאים במקום הנכון שלהם; צריך להיזהר לא לחשוב כך בטעות.

עקרון ההכלה וההפרדה מניב לנו עכשיו את הנוסחה הבאה ל-\( D\left(n\right) \), מספר הפרות הסדר של \( n \) איברים:

\( D\left(n\right)=n!-{n \choose 1}\left(n-1\right)!+{n \choose 2}\left(n-2\right)!-\dots+\left(-1\right)^{n}{n \choose n}\left(n-n\right)! \). כדי להבין מה פשר המקדם \( {n \choose k} \) שמופיע שם בואו נחשוב שניה איך אמורה להיראות הנוסחה: היא אמורה להתחיל עם \( n! \), ואז אמורים לחסר ממנה, לכל מקום בין 1 ל-\( n \), את מספר התמורות שבהן מקום זה מקובע. לכל מקום נקבל אותו מספר - \( \left(n-1\right)! \), ויש \( {n \choose 1} \) מקומות כאלו, ומכאן הכפל. בדומה, \( {n \choose 2} \) מתאים למספר האפשרויות לבחור זוג מקומות לקבע, וכן הלאה.

בואו נכתוב שוב את הנוסחה שקיבלתי, בצורה יותר קומפקטית: \( D\left(n\right)=\sum_{k=0}^{n}\left(-1\right)^{k}{n \choose k}\left(n-k\right)! \). האם יש דרך לפשט אותה עוד יותר? ובכן, \( {n \choose k}=\frac{n!}{k!\left(n-k\right)!} \) כך שאפשר לעשות כאן צמצום קטן ולקבל \( D\left(n\right)=\sum_{k=0}^{n}\left(-1\right)^{k}\frac{n!}{k!}=n!\left(\sum_{k=0}^{n}\frac{\left(-1\right)^{k}}{k!}\right) \). הקומבינטוריקה מביאה אותנו עד כאן ותו לא, אבל עכשיו החדו”א יכול להיכנס לפעולה.

כל מי שמכיר חדו”א ובוהה בנוסחה \( \sum_{k=0}^{n}\frac{\left(-1\right)^{k}}{k!} \) כנראה ירגיש משהו מצלצל לו - זה נראה כמו פונקציית האקספוננט \( e^{x}=\sum_{k=0}^{\infty}\frac{x^{k}}{k!} \), רק שכאן הטור סופי ולא אינסופי. במילים אחרות, \( \sum_{k=0}^{n}\frac{\left(-1\right)^{k}}{k!}=e^{-1}-\sum_{k=n+1}^{\infty}\frac{\left(-1\right)^{k}}{k!} \). אז קיבלנו שהסכום הוא “כמעט” \( \frac{1}{e} \), רק שיש גם שארית מעצבנת \( \sum_{k=n+1}^{\infty}\frac{\left(-1\right)^{k}}{k!} \) שצריך להבין מה בדיוק, או לפחות בערך, הגודל שלה. במקרה הספציפי שלנו זה קל במיוחד כי הטור הוא מה שנקרא “טור לייבניץ” - טור מהצורה \( \sum\left(-1\right)^{n}a_{n} \) כש-\( a_{n} \) שואפת מונוטונית לאפס, וידוע שסכום של טור שכזה, בערכו המוחלט, הוא קטן או שווה לגודל האיבר הראשון בו. כלומר, \( \left|\sum_{k=n+1}^{\infty}\frac{\left(-1\right)^{k}}{k!}\right|\le\left|\frac{\left(-1\right)^{n+1}}{\left(n+1\right)!}\right|=\frac{1}{\left(n+1\right)!} \).

אם כן, קיבלנו את הנוסחה \( D\left(n\right)=n!\cdot\left(e^{-1}+\xi\left(n\right)\right)=\frac{n!}{e}+n!\xi\left(n\right) \), כשכתבתי את השגיאה ב-\( \xi \) בדיוק כדי שתיראה מכוערת ונרצה להיפטר ממנה. מה אנחנו יודעים עליה? ש-\( \left|n!\xi\left(n\right)\right|\le\frac{n!}{\left(n+1\right)!}=\frac{1}{n} \). במילים אחרות, עבור \( n\ge3 \), השגיאה קטנה מחצי. זה מאפשר לנו לטעון את הטענה הנועזת הבאה: \( D\left(n\right)=\left[\frac{n!}{e}\right] \), כאשר הסוגריים המרובעים פירושם “ערך שלם” - המספר השלם הקרוב ביותר ל-\( \frac{n!}{e} \). זה עובד מכיוון שלכל מספר ממשי, הערך השלם שלו הוא במרחק לכל היותר \( \frac{1}{2} \) ממנו, בעוד שכל מספר שלם אחר הוא מרחק של לפחות \( \frac{1}{2} \) ממנו, ולכן אם כל ה”תיקון” שנדרש כדי לעבור מ-\( \frac{n!}{e} \) ל-\( D\left(n\right) \) הוא פחות מחצי, הערך השלם יביא אותנו ל-\( D\left(n\right) \) בודאות. את זה ש-\( D\left(n\right)=\left[\frac{n!}{e}\right] \) גם עבור \( n=1,2 \) אפשר לבדוק בצורה ישירה, והנה קיבלנו נוסחה סגורה ופשוטה ל-\( D\left(n\right) \). אפשר גם להסיק מסקנה הסתברותית - ככל ש-\( n \) שואף לאינסוף, כך ההסתברות לקבלת הפרת סדר כשמגרילים תמורה באקראי שואפת ל-\( \frac{1}{e} \); הנה לנו דוגמה נאה למקום שבו \( e \) צץ באופן טבעי לגמרי בבעיה קומבינטורית שבכלל לא מזכירה אותו.

הכללה והפחדה

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

אם כן, תהא \( X \) קבוצה כלשהי בת \( n \) איברים (אפשר לחשוב עליה כעל קבוצה של “תכונות” אם זה עוזר לנו). ניקח מרחב וקטורי \( V \) של כל הפונקציות \( f:\mbox{P}\left(X\right)\to\mathbb{R} \), כאשר \( \mbox{P}\left(X\right) \) פירושו קבוצת החזקה של \( X \) - אוסף כל תת-הקבוצות של \( X \). במילים אחרות, כל פונקציה \( f \) כזו מגדירה ערך כלשהו שמתאים לתת-קבוצה של \( X \). קל לראות ש-\( V \) הוא באמת מרחב וקטורי מעל \( \mathbb{R} \) (למעשה, \( \mathbb{R} \) לא ממש חשוב כאן וכל שדה אחר היה עובד באותה מידה). כעת נגדיר טרנספורמציה לינארית \( T:V\to V \) באופן הבא:

\( \left(Tf\right)\left(A\right)=\sum_{B\supseteq A}f\left(B\right) \)

כלומר, בהינתן \( f \), הפונקציה החדשה ש-\( Tf \) מגדירה היא כזו שערכה על כל תת-קבוצה \( A\subseteq X \) הוא סכום ערכי \( f \) על כל ה-\( B \) שמכילות את \( A \). חשבו על זה כך: \( f\left(A\right) \) אומרת כמה איברים ביקום שלנו מקיימים בדיוק את התכונות שבקבוצה \( A \) ושום דבר אחר; \( Tf\left(A\right) \) אומר כמה איברים ביקום שלנו מקיימים לפחות את התכונות שב-\( A \), ואולי עוד דברים. בדרך כלל את \( f \) קשה לחשב ואילו את \( Tf \) קל, ולכן מה שאנחנו רוצים לעשות הוא “להפוך” את \( T \); לקבל איכשהו מ-\( Tf \) את \( f \) עצמה. לצורך כך צריך שהטרנספורמציה הלינארית שלנו תהיה הפיכה, ועקרון ההכלה וההפרדה אומר שזה בדיוק מה שקורה, וגם נותן לנו את הנוסחה המדוייקת של \( T^{-1} \):

\( \left(T^{-1}f\right)\left(A\right)=\sum_{B\supseteq A}\left(-1\right)^{\left|B-A\right|}f\left(B\right) \)

תכף נראה איך זה מתקשר לדברים שראינו עד כה, אבל לפני כן בואו נוכיח. מה שאנחנו בעצם רוצים להראות הוא שאם נגדיר טרנספורמציה לינארית \( S:V\to V \) על ידי \( \left(Sf\right)\left(A\right)=\sum_{B\supseteq A}\left(-1\right)^{\left|B-A\right|}f\left(B\right) \) אז יתקיים ש-\( ST=TS=I \). עכשיו, כמו שבדרך כלל קורה באלגברה לינארית, כל מה שצריך לעשות הוא להציב והכל כבר מסתדר מעצמו. הבה ונראה מהו \( \left(TSf\right) \):

\( \left(TSf\right)\left(A\right)=T\left(\sum_{B\supseteq A}\left(-1\right)^{\left|B-A\right|}f\left(B\right)\right)=\sum_{B\supseteq A}\left(-1\right)^{\left|B-A\right|}Tf\left(B\right) \)

\( =\sum_{B\supseteq A}\left(-1\right)^{\left|B-A\right|}\left(\sum_{C\supseteq B}f\left(C\right)\right) \)

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

\( \sum_{C\supseteq A}\left(\sum_{A\subseteq B\subseteq C}\left(-1\right)^{\left|B-A\right|}\right)f\left(C\right) \)

האינדקס בסכום האמצעי הוא \( B \). אז למה \( \left|B-A\right| \) יכול להיות שווה? ברור שערכיו נעים בין 0 ובין \( m=\left|C-A\right| \). כמה קבוצות \( B \) מקיימות ש-\( \left|B-A\right|=i \) עבור \( 0\le i\le m \)? ובכן, בדיוק כמספר האיברים לבחור \( i \) מתוך \( m \) האיברים של \( C \) שאינם ב-\( A \), כלומר \( {m \choose i} \). לכן את הסכום האמצעי אפשר לכתוב גם כ-\( \sum_{i=0}^{m}\left(-1\right)^{i}{m \choose i}=\left(1-1\right)^{m} \) (כאן השתמשתי בבינום של ניוטון), ולכן אם \( m>0 \) אז הסכום האמצעי שווה לאפס, ואם \( m=0 \) אז הסכום האמצעי שווה ל-1 (אני משתמש כאן בקונוונציה לפיה \( 0^{0}=1 \), אבל מי שלא מאמין לי יכול לבדוק ולהיווכח בכך ש-\( \sum_{A\subseteq B\subseteq C}\left(-1\right)^{\left|B-A\right|} \) אכן שווה 1 כאשר \( A=C \), מה שמצדיק את השימוש בקונוונציה \( 0^{0}=1 \) כאן).

לסיכום, קיבלנו ש-\( \left(TSf\right)\left(A\right)=f\left(A\right) \), וזאת לכל \( A \), ולכן \( TS=I \) כנדרש. זה מסיים את הוכחת עקרון ההכלה וההפרדה הכללי ביותר שאני מכיר, אבל - מה בעצם עשינו כאן, לעזאזל?

התחלתי את הפוסט עם הנוסחה \( \left|\bigcup_{i=1}^{n}A_{i}\right|=\sum_{i=1}^{n}\left|A_{i}\right|-\sum_{1\le i<j\le n}\left|A_{i}\cap A_{j}\right|+\dots+\left(-1\right)^{n+1}\left|\bigcap_{i=1}^{n}A_{i}\right| \). כאן חשבנו על \( A_{i} \) בתור “קבוצת כל האיברים שמקיימים את התכונה ה-\( i \) לפחות” (לא בדיוק!), ולכן על \( A_{i}\cap A_{j} \) בתור כל האיברים שמקיימים לפחות את התכונות \( i,j \) וכן הלאה. בלשון הקבוצות של המשפט שלמעלה, \( S=\left\{ 1,2,\dots,n\right\} \) ו-\( f\left(A\right)=\left|\bigcap_{i\in A}A_{i}\right| \) (כן, יש לי כאן שימוש כפול מוזר ב-\( A \) וב-\( A_{i} \) במשמעויות שונות לגמרי. אל תגידו לי שזה מה שיחסל אתכם עכשיו).

הנוסחה שלעיל מתארת את \( \bigcup_{i=1}^{n}A_{i} \), שהוא מספר האיברים שמקיימים לפחות אחת מהתכונות, אבל בדרך כלל התעניינו דווקא במספר האיברים שלא מקיימים אף אחת מהתכונות, מה שגרם לנו לחסר את הגודל של \( \bigcup_{i=1}^{n}A_{i} \) ממספר האיברים הכולל ב”עולם” שלנו, שזו דרך אחרת להגיד “מספר האיברים שמקיימים לפחות אפס תכונות” (מעין “חיתוך ריק” שלא ממש ברור איך לכתוב אותו).

בואו נחדד את העניין, אם כן. נגדיר פונקציה\( f_{=}\left(A\right) \) ששווה למספר האיברים שמקיימים בדיוק את התכונות שב-\( A \). אנחנו מעוניינים לרוב למצוא את \( f_{=}\left(\emptyset\right) \), אבל לפעמים גם עבור קבוצות מחוכמות יותר. כעת, נגדיר גם \( f_{\ge}\left(A\right) \) בתור מספר האיברים שמקיימים לפחות את התכונות ב-\( A \), כלומר בדיוק \( f_{\ge}\left(A\right)=\left|\bigcap_{i\in A}A_{i}\right| \). כעת קל לראות שמתקיים הקשר

\( f_{\ge}\left(A\right)=\sum_{B\supseteq A}f_{=}\left(B\right) \) (הסבירו לעצמכם למה!) כלומר \( f_{\ge}=Tf_{=} \), ולכן \( f_{=}=T^{-1}f_{\ge} \), כלומר

\( f_{=}\left(A\right)=\sum_{B\supseteq A}\left(-1\right)^{\left|B-A\right|}f_{\ge}\left(B\right) \)

ובפרט עבור \( A=\emptyset \) נקבל

\( f_{=}\left(\emptyset\right)=\sum_{A}\left(-1\right)^{\left|A\right|}f_{\ge}\left(A\right) \)

וזוהי בדיוק נוסחת ההכלה וההפרדה המוכרת והאהובה שלנו, רק בניסוח יותר קומפקטי ויותר קל להבנה (כן! יותר קל! אחרי שבוהים בה הרבה, כנראה…).

אם כן, ראינו שעקרון ההכלה וההפרדה ניתן להצגה בתור מעין “היפוך” - מתחילים מפונקציה א’ שמוגדרת באמצעות סכום על ערכים של פונקציה ב’, “הופכים” ומקבלים את פונקציה ב’ מוצגת בתור סכום משוקלל מסויים על ערכים של פונקציה א’. זה, על רגל אחת, גם התוכן של נוסחת ההיפוך של מביוס; מיהי, מהי ואיך היא מתקשרת למה שראינו פה - בפעם הבאה.

נהניתם? התעניינתם? אם תרצו, אתם מוזמנים לתת טיפ: