WisFaq!

Herhalingscombinatie

Een herhalingscombinatie is een keuze van r objecten uit n gegeven objecten, waarbij de objecten meermaals gekozen mogen worden. (n mag dus groter zijn dan r)
De formule om het aantal herhalingscombinaties te berekenen = (n+r-1)!/(r!.(n-1)!). Kan iemand mij uitleggen hoe je daar aan komt?

Leen Van Gompel
15-10-2002

Antwoord

Hoi,

Dit is een verrassend moeilijke...

Het probleem:
We hebben n verschillende items die we 1,2,..,n nummeren.
We nemen r (r eventueel > n) items. Hierbij nemen we telkens een willekeurig item en leggen het terug, vóór we het volgende nemen.
De uiteindelijke volgorde van de items speelt geen rol.
We tellen het aantal manieren waarop we tot r items kunnen komen.
Je kan dit opsommen voor bv: n=3 en r=2: 11,12,13,22,23,33

The hard way:
Het aantal mogelijk trekkingen met terugleggen van r items uit n items, zonder volgorde: N(n,r) (dit is het gevraagde)

We zien:
N(1,r)=1 en N(n,1)=n
We zien ook:
N(n,r)=å(i=1..n:N(n-i+1,r-1)) =å(i=1..n:N(i,r-1))
(opsplitsen volgens item met kleinste nummer, als dit i is, dan zijn er N(i,r-1) mogelijke aanvullingen)
Je kan een soort van driehoek van Pascal uittekenen. Hiermee kan je per inductie (eerst naar r en dan naar n) bewijzen dat N(n,r)=C(n+r-1,r) met C(n,m)=n!/[m!.(n-m)!]...

Je kan ook een bijectie zoeken tussen elke combinatie van r uit n+r-1 en elke herhalingscombinatie van r uit n. Bijvoorbeeld: 11, 12, 13, 22, 23, 33 correspondeert één voor één met 12, 13, 14, 23, 24, 34. Een herhalings combinatie {x_i} (x_i in niet-dalende volgorde) correspondeert dus één op één met de niet-herhalingscombinatie {x_i+i-1} (bij het i-de element i-1 bijtellen). Hiermee is de formule ook bewezen...

De eenvoud van het resultaat doet echter (nog altijd) vermoeden dat er een eenvoudiger piste moet zijn...

Zie ook Formule voor herhalingscombinaties

Groetjes,
Johan

andros
16-10-2002