De digitale vraagbaak voor het wiskundeonderwijs

home |  vandaag |  gisteren |  bijzonder |  prikbord |  gastenboek |  wie is wie? |  contact

HOME

samengevat
vragen bekijken
een vraag stellen
hulpjes
zoeken
FAQ's
links
twitter
boeken
help

inloggen

colofon

  \require{AMSmath} Printen

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 V
Student universiteit Belgi - dinsdag 15 oktober 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, vr 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 {xi} (xi in niet-dalende volgorde) correspondeert dus n op n met de niet-herhalingscombinatie {xi+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
Vragen naar aanleiding van dit antwoord? Klik rechts..!
woensdag 16 oktober 2002
  Re: Herhalingscombinatie  



klein |  normaal |  groot

home |  vandaag |  bijzonder |  twitter |  gastenboek |  statistieken |  wie is wie? |  colofon

©2001-2021 WisFaq - versie 3