[wiskunde] Aantal combinaties berekenen

[Beresteyn]

Hoe bereken je ook alweer het aantal combinaties als je aanneemt dat alle combinaties mogelijk zijn en de groepsgrootte kan verschillen.
 
Als simpel voorbeeld nemen we aan dat we vijf ballen hebben. Deze ballen zijn genummerd van 1 t/m 5. Combinaties zijn groepjes van ≥2 ballen. Voorbeelden zijn: 1, 2, 3 en 2, 3, 4, 5 en 3, 4. Hoe vorm je de formule waarbij je gemakkelijk en snel kunt doorrekenen voor n ballen (bijv. als je hetzelfde principe wil berekenen voor 5 miljoen ballen). Let op: de volgorde maakt niet uit. Dus de combinaties 3, 4 en 4, 3 worden als één geteld.
 
Ik ben bekend met permutaties en combinaties, maar alleen met de berekening per individuele groep. Dus voor combinaties van 2 ballen zou het aantal combinaties (n! / (n-k)!) / n! zijn. In dit geval hebben we dus (5! / (5-2)!) / 2! = 10 combinaties. Voor combinaties van 3 ballen geldt dat we (5! / (5-3)!) / 3! = 10 combinaties. In het geval van combinaties van 4 ballen hebben we (5! / (5-4)!) / 4! = 5 combinaties. En in het geval van alle 5 hebben we natuurlijk slechts 1 combinatie. Nou zou je deze combinaties bij elkaar kunnen optellen als een totaal van 10 + 10 + 5 + 1 = 26 combinaties. Maar ik vroeg me af of er een gestandaardiseerde formule is om deze hoeveelheid totaal uit te rekenen voor een (zeer) groot aantal n, zonder dat ik al die individuele combinaties moet uitrekenen per n.

[EvilBro]

Via dit:

\((a + b)^N = \sum_{k = 0}^{N} {N \choose k} a^k b^{N - k}\)

naar:

\((a + b)^N = {N \choose 0} + {N \choose 1} + \sum_{k = 2}^{N} {N \choose k} a^k b^{N - k}\)

\(\sum_{k = 2}^{N} {N \choose k} a^k b^{N - k} = (a + b)^N - {N \choose 1} - {N \choose 0}\)

Stel a = b = 1:

\(\sum_{k = 2}^{N} {N \choose k} = 2^N - {N \choose 1} - {N \choose 0}\)

\(\sum_{k = 2}^{N} {N \choose k} = 2^N - N - 1\)

[EvilBro]

Ik zie dat ik iets niet helemaal goed heb opgeschreven. Het midden had moeten zijn:

\((a + b)^N = {N \choose 0} b^N + {N \choose 1} a b^{N - 1} + \sum_{k = 2}^{N} {N \choose k} a^k b^{N - k}\)

\(\sum_{k = 2}^{N} {N \choose k} a^k b^{N - k} = (a + b)^N - {N \choose 1} a b^{N - 1} - {N \choose 0} b^N\)

[Beresteyn]

Dank voor de formule. Echter, zou je eventueel een kort praktisch voorbeeld kunnen toelichten?

[EvilBro]

Ik snap niet zo goed wat ik moet toelichten...

Bijvoorbeeld N=5 (want die heb je met de hand uitgerekend):

\(2^5 - 5 - 1 = 32 - 6 = 26\)

[EvilBro]

Eigenlijk kan de afleiding veel makkelijker (bedenk ik me nu):
Je hebt N elementen die zich in 1 van 2 toestanden bevinden: In de groep of niet. Dit zijn dan natuurlijk \(2^N\) mogelijkheden. Hiervan moeten de groepen met maar 1 element (dat zijn er N) en de groep met geen elementen (dat is er 1) afgetrokken worden. Resultaat:

\(2^N - N - 1\)

[Beresteyn]

Zo stond het toch ook aan het eind van bericht #2?! 
 
Ik begrijp alleen niet waar a en b voor staan in de formule, maar ik kan 'm toepassen en daar gaat het uiteindelijk om.

[mathfreak]

Ik begrijp alleen niet waar a en b voor staan in de formule

Zoek maar eens op het binomium van Newton. Voor N = 2 krijg je de bekende formule (a+b)² = a²+2·a·b+b². Het binomium van Newton is hier een generalisatie van.