Stel dat je n soorten items hebt, en je wilt een verzameling van r daarvan selecteren. Misschien willen we deze items in een bepaalde volgorde. We noemen deze verzamelingen items permutaties. Als de volgorde er niet toe doet, noemen we de verzameling verzamelingen combinaties. Voor zowel combinaties als permutaties kun je het geval overwegen waarin je sommige van de n typen meer kiest dan eenmaal, wat 'met herhaling' wordt genoemd, of het geval waarin je elk type maar één keer kiest, dat 'nee' wordt genoemd herhaling'. Het doel is om het aantal mogelijke combinaties of permutaties in een bepaalde situatie te kunnen tellen.
Bestellingen en Factories
De faculteitsfunctie wordt vaak gebruikt bij het berekenen van combinaties en permutaties. n! betekent N×(N–1)×...×2×1. Bijvoorbeeld 5! = 5×4×3×2×1 = 120. Het aantal manieren om een set items te bestellen is een faculteit. Neem de drie letters a, b en c. Je hebt drie keuzes voor de eerste letter, twee voor de tweede en slechts één voor de derde. Met andere woorden, in totaal 3×2×1 = 6 bestellingen. Over het algemeen zijn er n! manieren om n items te bestellen.
Permutaties met herhaling
Stel dat je drie kamers hebt die je gaat schilderen, en elke kamer krijgt een van de vijf kleuren: rood (r), groen (g), blauw (b), geel (y) of oranje (o). U kunt elke kleur zo vaak kiezen als u wilt. Je hebt de keuze uit vijf kleuren voor de eerste kamer, vijf voor de tweede en vijf voor de derde. Dit geeft in totaal 5×5×5 = 125 mogelijkheden. In het algemeen is het aantal manieren om een groep van r items in een bepaalde volgorde te kiezen uit n herhaalbare keuzes n^r.
Permutaties zonder herhaling
Stel nu dat elke kamer een andere kleur krijgt. U kunt kiezen uit vijf kleuren voor de eerste kamer, vier voor de tweede en slechts drie voor de derde. Dit geeft 5×4×3 = 60, wat toevallig 5!/2! is. In het algemeen is het aantal onafhankelijke manieren om r items in een bepaalde volgorde te selecteren uit n niet-herhaalbare keuzes n!/(n–r)!.
Combinaties zonder herhaling
Vergeet vervolgens welke kamer welke kleur heeft. Kies gewoon drie onafhankelijke kleuren voor het kleurenschema. De volgorde maakt hier niet uit, dus (rood, groen, blauw) is hetzelfde als (rood, blauw, groen). Voor elke keuze uit drie kleuren zijn er 3! manieren waarop u ze kunt bestellen. Je vermindert dus het aantal permutaties met 3! om 5!/(2!×3!) = 10 te krijgen. Over het algemeen kun je een groep r items in willekeurige volgorde kiezen uit een selectie van n niet-herhaalbare keuzes op n!/[(n–r)!×r!] manieren.
Combinaties met herhaling
Ten slotte moet u een kleurenschema maken waarin u elke kleur zo vaak kunt gebruiken als u wilt. Een slimme boekhoudcode helpt bij deze teltaak. Gebruik drie X'en om de kamers weer te geven. Uw lijst met kleuren wordt weergegeven door 'rgbyo'. Meng de X'en in je kleurenlijst en associeer elke X met de eerste kleur links ervan. rgXXbyXo betekent bijvoorbeeld dat de eerste kamer groen is, de tweede groen en de derde geel. Een X moet ten minste één kleur aan de linkerkant hebben, dus er zijn vijf beschikbare slots voor de eerste X. Omdat de lijst nu een X bevat, zijn er zes beschikbare slots voor de tweede X en zeven beschikbare slots voor de derde X. In totaal zijn er 5×6×7 = 7!/4! manieren om de code te schrijven. De volgorde van de kamers is echter willekeurig, dus er zijn eigenlijk maar 7!/(4!×3!) unieke arrangementen. Over het algemeen kunt u r items in willekeurige volgorde kiezen uit n herhaalbare keuzes op (n+r–1)!/[(n–1)!×r!] manieren.