עֶקְרוֹן הַהֲכָלָה וְהַהַפְרָדָה או עֶקְרוֹן הַהֲכָלָה וְהַהֲדָחָה הוא עיקרון קומבינטורי שלפיו, כדי לספור עצמים בקבוצה, אפשר לכלול ולהוציא את אותו עצם שוב ושוב, כל עוד בסוף ההליך נספר כל עצם פעם אחת. עיקרון זה מתורגם לנוסחה שיש לה שימושים וגרסאות רבות בכל ענפי הקומבינטוריקה.

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

תהיינה ${\displaystyle A_{1},\dots ,A_{n}}$ קבוצות סופיות. אז גודל האיחוד ${\displaystyle |A_{1}\cup \cdots \cup A_{n}|}$ שווה לסכום המתחלף ${\displaystyle \sum _{i}|A_{i}|-\sum _{i<j}|A_{i}\cap A_{j}|+\sum _{i<j<k}|A_{i}\cap A_{j}\cap A_{k}|\mp \cdots }$, כלומר: ${\displaystyle \ |\cup A_{i}|=\sum _{k=1}^{n}(-1)^{k-1}\sum _{1\leq i_{1}<\cdots <i_{k}\leq n}|A_{i_{1}}\cap \cdots \cap A_{i_{k}}|}$. אם מסכימים שחיתוך אפס קבוצות שווה למרחב כולו, אפשר לקבל נוסחה אלגנטית למספר האיברים שמחוץ לאיחוד: ${\displaystyle |\Omega -\cup A_{i}|=\sum _{k=0}^{n}(-1)^{k}\sum _{1\leq i_{1}<\cdots <i_{k}\leq n}|A_{i_{1}}\cap \cdots \cap A_{i_{k}}|}$.

במקרים רבים גודל החיתוך של כל k קבוצות הוא קבוע, ואז מתקבלת נוסחה פשוטה יותר, ${\displaystyle |\Omega -\cup A_{i}|=\sum _{k=0}^{n}(-1)^{k}{\binom {n}{k}}|A_{1}\cap \cdots \cap A_{k}|}$.

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

1. מספר העצמים שהם גדולים או אדומים, שווה למספר העצמים הגדולים ועוד מספר העצמים האדומים.
2. פחות מספר העצמים שהם גם גדולים וגם אדומים.

האיברים בשלב השני נספרו פעמיים בשלב הראשון (פעם ראשונה כאדומים, פעם שנייה כגדולים) לכן יש להחסיר אותם.

באופן פורמלי, אם ${\displaystyle A}$ היא קבוצת העצמים האדומים, ו-${\displaystyle B}$ היא קבוצת העצמים הגדולים, אז הגודל של האיחוד בניהן יְחוּשַּׁב כך: ${\displaystyle |A\cup B|=|A|+|B|-|A\cap B|}$.

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

נוסחת ההכלה וההפרדה לגודל האיחוד של שלוש קבוצות היא ${\displaystyle |A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|}$.

נראה כיצד ניתן לחשב את מספר התמורות על ${\displaystyle \ n}$ איברים שבהן אף איבר אינו נשאר במקומו. כדי להפעיל את עקרון ההכלה וההדחה, נסמן ב-${\displaystyle \ A_{i}}$ את קבוצת התמורות שבהן האיבר ה-i דווקא נשאר במקומו. השאלה היא כמה תמורות נמצאות מחוץ לכל הקבוצות, ומכיוון שמספר התמורות הכללי הוא ${\displaystyle \ n!}$, די לספור כמה תמורות שייכות לקבוצה אחת לפחות; כלומר, לחשב את ${\displaystyle |A_{1}\cup \cdots \cup A_{n}|}$. בחיתוך של k קבוצות נמצאות התמורות שמשאירות את k האיברים המתאימים במקומם, בלי קשר לשאלה מה הן עושות בשאר האיברים. לכן גודל החיתוך הוא ${\displaystyle |A_{i_{1}}\cap \cdots \cap A_{i_{k}}|=(n-k)!}$, וזאת לכל אחת מ- ${\displaystyle {\frac {n!}{k!(n-k)!}}}$ הבחירות של האיברים השונים ${\displaystyle i_{1}<\cdots <i_{k}}$. לפי עקרון ההכלה וההדחה, ${\displaystyle n!-|A_{1}\cup \cdots \cup A_{n}|=\sum _{k=0}^{n}(-1)^{k}{\frac {n!}{k!(n-k)!}}|A_{1}\cap \cdots \cap A_{k}|=\sum _{k=0}^{n}(-1)^{k}{\frac {n!}{k!}}=n!\sum _{k=0}^{n}{\frac {(-1)^{k}}{k!}}}$. הסיכוי שתמורה אקראית תהיה שייכת לקבוצה הזאת הוא ${\displaystyle \sum _{k=0}^{n}{\frac {(-1)^{k}}{k!}}}$, שהוא קירוב טוב מאוד למספר ${\displaystyle e^{-1}}$.

כדי להוכיח את השוויון ${\displaystyle |\Omega -\cup A_{i}|=\sum _{k=0}^{n}(-1)^{k}\sum _{1\leq i_{1}<\cdots <i_{k}\leq n}|A_{i_{1}}\cap \cdots \cap A_{i_{k}}|}$, נבדוק כמה פעמים נספר איבר x בשני האגפים. אם x אינו שייך לאף קבוצה, אז הוא נספר פעם אחת באגף שמאל, ופעם אחת (במסגרת החיתוך הריק, עבור k=0) באגף ימין. אחרת, נניח שהוא שייך בדיוק ל-m קבוצות, ומטעמי סימטריה אפשר להניח שאלו הן הקבוצות ${\displaystyle A_{1},\cdots ,A_{m}}$; בפרט, x אינו שייך לקבוצות ${\displaystyle A_{m+1},\dots ,A_{n}}$. במקרה כזה האיבר נספר באגף ימין בדיוק ${\displaystyle \sum _{k=0}^{n}(-1)^{k}\sum _{1\leq i_{1}<\cdots <i_{k}\leq m}1=\sum _{k=0}^{m}(-1)^{k}{\frac {m!}{k!(m-k)!}}=(1-1)^{m}=0}$ פעמים לפי נוסחת הבינום של ניוטון, בדיוק כמו באגף שמאל.

• עקרון החיבור

מיזמי קרן ויקימדיה
ערך מילוני בוויקימילון: הכלה

• עקרון ההכלה וההפרדה, באתר MathWorld (באנגלית)