עקרון ההכלה וההפרדה – הבדלי גרסאות

תוכן שנמחק תוכן שנוסף
Matanyabot (שיחה | תרומות)
מ בוט החלפות: \1איברים
החלפתי לשם הראשי! נא לשנות את הכותרת
שורה 1:
'''עקרון ההכלה וההפרדהוההדחה''' (או '''עקרון ההכלה וההדחהוההפרדה''') הוא עקרון [[קומבינטוריקה|קומבינטורי]] שלפיו, כדי לספור עצמים בקבוצה, אפשר לכלול ולהוציא את אותו עצם שוב ושוב, כל עוד בסוף ההליך נספר כל עצם פעם אחת. עקרון פשוט זה מתורגם לנוסחה מעט מורכבת, שיש לה שימושים וגרסאות רבות בכל ענפי הקומבינטוריקה. המקרה הפשוט ביותר מתייחס לספירת עצמים המקיימים אחת משתי תכונות: מספר העצמים שהם גדולים או אדומים שווה למספר העצמים הגדולים ועוד מספר העצמים האדומים, פחות מספר העצמים שהם גם גדולים וגם אדומים; האחרונים נספרו בשלב הראשון פעמיים, ואז הוצאו מהחשבון על-מנת לאזן אותו כראוי. בכתיב מתמטי, <math>\ |A\cup B| = |A|+|B|-|A\cap B|</math>, כאשר A היא קבוצת העצמים האדומים ו-B היא קבוצת העצמים הגדולים.
 
במקרה הכללי, העקרון קובע שגודל האיחוד של כמה קבוצות שווה לסכום מתחלף: סכום הגדלים של כל הקבוצות, פחות סכום הגדלים של חיתוכים של שתי קבוצות, ועוד סכום הגדלים של חיתוכים של שלוש קבוצות, פחות סכום הגדלים של חיתוכים של ארבע קבוצות, וכן הלאה.