] >
Laten en eindige verzamelingen zijn met . Het beeld van een injectieve afbeelding is een deelverzameling van met elementen. We leiden formules af voor het aantal injectieve afbeeldingen van eindige verzamelingen en voor het aantal deelverzamelingen met een gegeven aantal elementen van een eindige verzameling.
9.1 Notatie. Zijn en verzamelingen, dan noteren we de verzameling van injectieve afbeeldingen van naar met .
Dit is geen algemeen aanvaarde notatie. We gebruiken hem alleen in deze paragraaf.
Bewijs. In: ”Getallen”, Epsilon deel 65, uitgegeven door Epsilon-Uitgaven. □
Hetzelfde bewijs, maar wat losser geformuleerd: een injectieve afbeelding van naar maak je door achtereenvolgens beelden van elementen van te kiezen; voor het eerste element heb je mogelijkheden, dan voor het tweede , etc. Dus in totaal .
Een speciaal geval:
9.3 Gevolg. Laten en eindige verzamelingen zijn met . Dan zijn er bijectieve afbeeldingen van naar .
Bewijs. Injectieve afbeeldingen van naar zijn bijectief. □
9.4 De verjaardagsparadox. Wat is de kans dat in een gezelschap van personen er twee zijn die op de zelfde dag jarig zijn? Laten we 29 februari buiten beschouwing dan is de kans dat er niet twee personen zijn die op dezelfde dag jarig zijn gelijk aan
Deze kans is dus . Voor toenemende neemt deze kans af: voor is hij (uiteraard) , voor is hij . Vanaf welke is hij kleiner dan ? Deze vraag staat bekend als het verjaardagsprobleem. De oplossing is , hetgeen voor velen een verrassend klein aantal is. Daarom spreekt men wel van de verjaardagsparadox. (In het algemeen, als het gaat om injectieve afbeeldingen naar , is in de orde van grootte van .)
De code voor het berekenen van faculteiten is uiteraard eenvoudig, zie combinatorics.py
9.5 Notatie. Laat een eindige verzameling zijn met elementen en zij een natuurlijk getal met . We geven met de verzameling aan die bestaat uit de deelverzamelingen van met elementen, dus:
We definiëren:
9.6 Definitie. Laten en natuurlijke getallen zijn met . Dan
Dit getal heet een binomiaalcoëfficiënt. (Verderop wordt duidelijk waarom we hem zo noemen).
We hebben in de definitie genomen. Omdat, als , het eenvoudig in te zien is dat , maakt het niet uit welke verzameling met elementen we nemen.
Laat een eindige verzameling zijn met . Laat een natuurlijk getal zijn zo dat . (Dus .) We nemen een vast element van . Dan kunnen we twee soorten deelverzamelingen van met elementen onderscheiden:
Deelverzamelingen van de eerste soort corresponderen met deelverzamelingen van met elementen. Daarvan zijn er . Deelverzamelingen van de tweede soort zijn deelverzamelingen van met elementen en daarvan zijn er . We hebben dus afgeleid:
Andere eigenschappen zijn:
Bewijs. In: ”Getallen”, Epsilon deel 65, uitgegeven door Epsilon-Uitgaven. □
We kunnen de getallen overzichtelijk weergeven in een driehoekig diagram, de driehoek van Pascal, zie Figuur 9.1.
Je kunt de aantallen in Figuur 9.1 opvatten als het aantal wegen in de gerichte graaf van Figuur 9.3 van boven naar beneden die in het hoekpunt beginnen. Het aantal wegen naar een hoekpunt is immers gelijk aan de som van de aantallen wegen naar de hoekpunten die er onmiddellijk boven liggen.
Een weg ontstaat door herhaald voor links of rechts te kiezen: ga je een hoekpunt naar beneden, dan heb je steeds de keuze tussen een linker en een rechter hoekpunt. In welke rij je zo terecht komt hangt af van het aantal keuzes dat is gemaakt. Na keuzes kom je in rij nummer . Heb je op een totaal van keuzes keer voor rechts gekozen, dan kom je in het hoekpunt . De wegen naar dit hoekpunt corresponderen dus met deelverzamelingen van met elementen.
In de driehoek van Pascal zijn veel regelmatigheden te ontdekken. Zo kun je bijvoorbeeld voor deze eerste rijen constateren dat de som in elke rij gelijk is aan , waarbij het rijnummer is. Dit is het totale aantal deelverzamelingen van een verzameling met elementen. In de rij staan deze aantallen verder uitgesplitst naar het aantal elementen van de deelverzamelingen.
De eigenschappen in de Proposities 9.7 en 9.8 leggen de binomiaalcoëfficiënten vast en kunnen gebruikt worden om ze uit te rekenen. Zo is de driehoek van Pascal in Figuur 9.2 gemaakt. Bij het ontwerpen van een algoritme voor het berekenen van een binomiaalcoëfficiënt is het van belang dat er niet teveel bij moet worden onthouden en ook dat niet veel getallen alsmaar opnieuw berekend moeten worden. Bij het berekenen van een binomiaalcoëfficiënt zijn alleen de binomiaalcoëfficiënten van belang die in de driehoek van Pascal er (schuin) boven liggen. In deze driehoek is er dus een ‘parallellogram’ van getallen die berekend moeten worden. De lijst met getallen die langs de zijde linksboven staan bestaat uit louter enen. De lijst van getallen die daar direct rechtsonder staan, begint bovenin met een en kan verder worden ingevuld met behulp van de eerste lijst. Zo kun je iedere volgende lijst van getallen berekenen en tenslotte is de te berekenen binomiaalcoëfficiënt het laatste getal in de laatst te berekenen lijst onder in het parallellogram. Zie Figuur 9.4 voor de berekening van .
Pythoncode voor het hierboven beschreven algoritme:
Hiermee kunnen grote binomiaalgetallen snel worden berekend.
We hebben binomiaalcoëfficiënten berekend met behulp van de Driehoek van Pascal. Een directe formule is er ook:
Bewijs. Laten en eindige verzamelingen zijn met en . De surjectieve afbeelding
induceert een partitie van . Bij iedere met is er een klasse
Deze klasse heeft even veel elementen als er bijecties van naar zijn. Dit aantal is volgens Gevolg 9.3 gelijk aan . Dus
Hieruit volgt:
De juistheid van deze formule is (achteraf) ook in te zien door voor deze getallen de betrekkingen te verifiëren die de binomiaalcoëfficiënten vastleggen.