] >
Het principe van inclusie-exclusie is van toepassing op veel telproblemen. We passen het in paragraaf 10.1 toe op het tellen van permutaties die geen element vast laten (lootjes trekken voor surprise). In de volgende paragraaf gebruiken we het voor het afleiden van een formule voor het aantal surjecties tussen eindige verzamelingen. Dit houdt verband met het aantal partities van eindige verzamelingen.
Gegeven zijn:
Het principe van inclusie-exclusie geeft een formule voor het aantal elementen van dat niet in een van de deelverzamelingen ligt. De formule bevat alleen aantallen elementen van doorsneden van deelverzamelingen . We voeren voor het gemak een verkorte notatie voor deze doorsneden in. Voor schrijven we
De -notatie heeft de volgende betekenis:
Dus , , , , etc. Deze notatie is te vergelijken met de -notatie. Ook hier hebben we een verzameling met een associatieve, commutatieve bewerking met een neutraal element: de verzameling met als bewerking, het neutrale element is zelf. Bij de -notatie hoeft de indexverzameling niet eindig te zijn: iedere collectie van verzamelingen heeft een doorsnede. Analoog aan de -notatie is er ook een -notatie voor de vereniging van een collectie verzamelingen. In deze paragraaf gaat het om het tellen en dan zijn alle erbij betrokken verzamelingen eindig.
We gebruiken karakteristieke functies op van deelverzamelingen van , zie de paragrafen 3.9 en 6.2. Het gedrag van karakteristieke functies onder complement en doorsnede nemen is eenvoudig:
Ook voor de karakteristieke functies gebruiken we een verkorte notatie:
Het principe van inclusie-exclusie geeft een formule voor . Uit volgt
We passen Stelling 9.12 toe:
Sommeren over geeft:
We voeren nog een paar standaardnotaties in:
In plaats van bijvoorbeeld zullen we vaak schrijven. We hebben: . Het principe van inclusie-exclusie is nu als volgt te formuleren:
9.39 Stelling (Principe van inclusie-exclusie). Met de notaties van deze paragraaf: het aantal elementen van dat niet in een van de deelverzamelingen zit, is gelijk aan
9.40 Voorbeeld. We bepalen het aantal getallen in die niet door , , of deelbaar zijn. We gebruiken de indexverzameling . Laten , , en de deelverzamelingen van zijn van respectievelijk de -vouden, de -vouden, de -vouden en de -vouden. We hebben en verder
en dus . Omdat de vier getallen , , en paarsgewijs relatief priem zijn, hebben we
en dus . We bepalen :
Dus . Uit volgt dat . Het aantal getallen in dat geen veelvoud is van , , of is dus . Dit aantal is dus berekend zonder de getallen afzonderlijk te bekijken. Je kunt ze natuurlijk vinden door van de getallen van tot en met achtereenvolgens de -, -, - en -vouden weg te laten (weg te strepen). Je houdt in dit geval het getal over en de priemgetallen groter dan .