Variaties Permutaties Combinaties Kans




Tellen zonder herhaling

Aantal elementen in een verzameling

Als een eindige verzameling A juist n elementen bevat dan schrijven we #A = n.

Voorbeeld :
V = de verzameling van de diagonalen van een regelmatige vijfhoek. #V = 5.

Variaties

Neem een verzameling van n verschillende elementen. Kies daaruit p elementen in een bepaalde volgorde.
Dergelijke keuze noemen we een variatie van n elementen p aan p.

Voorbeeld: Uit een klas van 20 leerlingen moet je 5 leerlingen kiezen in een bepaalde volgorde. Zo'n keuze is een variatie van 20 elementen 5 aan 5.
Er zijn 20 mogelijkheden om de eerste leerling te kiezen. Voor de keuze van de tweede zijn er maar 19 mogelijkheden meer. En zo verder

Algemene redenering:

Hoeveel mogelijkheden zijn er om zo'n keuze te maken?
Welnu. We moeten p verschillende elementen kiezen uit n.
Er zijn n mogelijkheden bij het kiezen van het eerste element.
Er zijn n-1 mogelijkheden bij het kiezen van het tweede element.
Er zijn n-2 mogelijkheden bij het kiezen van het derde element.
...
Er zijn n-(p-1) mogelijkheden bij het kiezen van het p-de element.
Dus, het totale aantal mogelijkheden is n.(n-1).(n-2). ... .(n-p+1).
We noteren dit aantal mogelijkheden als V(n,p) = n.(n-1).(n-2). ... .(n-p+1).

In vorig voorbeeld wordt dit aantal V(20,5)=20.19.18.17.16=1860480

Voorbeeld 2

Uit een doos met 7 taartjes moet je er drie kiezen.
De eerste keuze is voor je broer, de tweede voor je zus, de derde is voor jezelf.
Die keuze is een variatie van 7 elementen 3 aan 3. Er zijn V(7,3)=7.6.5 mogelijkheden om zo'n keuze te maken.
Merk nogmaals op dat de volgorde van kiezen hier van belang is.

Permutaties

Neem een verzameling van n verschillende elementen. Plaats die n elementen in een zelf gekozen volgorde. Elke keuze geeft een geordend n-tal elementen en heet een permutatie van de gegeven elementen.

Voorbeeld: Neem een klas van 20 leerlingen. Plaats die leerlingen op een rij. Dit kan op zeer veel manieren gebeuren. Het vormen van zo'n rij is eigenlijk een speciaal geval van een variatie: kies uit 20 leerlingen, niet 5, maar 20 leerlingen in een bepaalde volgorde. Het is dus een variatie van 20 elementen 20 aan 20.

Algemene redenering:

Hoeveel verschillende permutaties kan je vormen met n elementen?
Een permutatie is eigenlijk een variatie van de n elementen n aan n.
Dus, het aantal verschillende permutaties = V(n,n) = n.(n-1).(n-2). ... .2.1
We noteren dit aantal mogelijkheden als P(n) = n.(n-1).(n-2). ... .2.1 = n! .
n! wordt gelezen 'n faculteit'

In ons voorbeeld wordt dit aantal 20!

Voorbeelden:

Je kan 5 verschillende knikkers op 5! = 120 manieren op een rij plaatsen.

Je kan 5 verschillende taartjes op 120 manieren toekennen aan 5 personen die elk 1 taartje krijgen.

Combinaties

Neem een verzameling van n verschillende elementen. Kies daaruit p elementen.
De volgorde van deze p elementen heeft helemaal geen belang. Dergelijke keuze noemen we een combinatie van n elementen p aan p.
Verander je de gekozen elementen van volgorde dan is dit geen nieuwe combinatie van n elementen p aan p. Zo'n keuze van p elementen kan op veel manieren gebeuren. We noteren dit aantal mogelijkheden als C(n,p).

Voorbeeld

Uit een team van 5 renners moet een groepje van 3 gekozen worden. De volgorde van het uitkiezen van die 3 renners heeft geen belang. Zo'n keuze heet een combinatie van 5 elementen 3 aan 3. Het totaal aantal mogelijkheden om dergelijk groepje te kiezen noteren we C(5,3).
We zullen nu, eerst aan de hand van dit voorbeeld, het aantal mogelijkheden bepalen.

We zullen het aantal variaties van 5 elementen 3 aan 3 vergelijking met het aantal combinaties van 5 elementen 3 aan 3. We maken 2 kolommen. In de eerst kolom staan alle variaties van 5 elementen 3 aan 3 en in de tweede kolom alle combinaties van 5 elementen 3 aan 3.

 
    variations  combinations
       ABC       ABC
       ACB
       BAC
       BCA
       CAB
       CBA
       ABD       ABD
       ADB
       BDA
       BAD
       DAB
       DBA
       ...      ...
       etc      etc


In de tabel zien we dat met 6 variaties slechts 1 combinatie overeenkomt. Er zijn dus 6 = 3! keer meer variaties dan combinaties. Zo hebben we gevonden : V(5,3) = C(5,3). 3!

Algemeen:

We hebben V(n,p) = C(n,p) . p!
Of anders geschreven C(n,p) = V(n,p) / p!

Daar V(n,p) = n.(n-1).(n-2). ... .(n-p+1) , hebben we

 
                 n.(n-1).(n-2). ... .(n-p+1)
        C(n,p) = ---------------------------
                             p!

                 n.(n-1).(n-2). ... .(n-p+1).(n-p). ... .1
<=>     C(n,p) = ---------------------------------------------------
                             p! . (n-p). ... .1

                     n!
<=>     C(n,p) = ------------
                   p!.(n-p)!
Voorbeeld 2:

Uit een verzameling van 20 boeken, neem je 4 boeken mee naar huis om ze te lezen.
We berekenen het aantal mogelijke keuzes.

n = 20 ; p = 4 De volgorde van de geselecteerde boeken is van geen belang.
Het aantal mogelijkheden is C(20,4) = 4845

Eigenschappen van combinaties

Steunend op de laatste formule bewijst men gemakkelijk dat
a) C(n,p) = C(n,n-p)
b) C(n,p) = C(n-1,p) + C(n-1,p-1) ( regel van Pascal )

Binomiaal coefficient

Het getal C(n,p) heet ook een binomiaalcoefficient en wordt ook genoteerd als
 
    p           n
   C  of als  (   )
    n           p

Binomium van Newton

We zullen aantonen dat
 

(a + b)n = an  + C(n,1)an-1 b + C(n,2)an-2 b2  + C(n,3)an-3 b3  +  ...


            +   C(n,n) bn
Om deze eigenschap te bewijzen gebruiken we volledige inductie. Het is heel eenvoudig na te gaan dat de eigenschap geldt voor n=2.
Onderstel nu dat ze geldt voor n = k. We zullen aantonen dat ze dan ook geldt voor n = k+1.
 
(a + b)k+1   = (a + b).(a + b)k


=(a+b).(ak  + C(k,1)ak-1 b  + C(k,2)ak-2 b2  + C(k,3)ak-3 b3  + ... C(k,k)bk )


= ak+1 + C(k,1)ak b  + C(k,2)ak-1 b2  + C(k,3)ak-2 b3  + ... C(k,k)a bk  +

               ak b + C(k,1)ak-1 b2  + C(k,2)ak-2 b3  + ...+ C(k,k-1)a bk + C(k,k) bk+1

Daar C(k,k)= C(k+1,k+1)= 1 en steunend op de regel van Pascal
C(n,p) = C(n-1,p) + C(n-1,p-1) , vinden we
 
= ak+1   + C(k+1,1)ak b  + C(k+1,2)ak-1 b2  + C(k+1,3)ak-2 b3  +  ...

            +   C(k+1,k+1) bk+1
Zo is de formule bewezen.

Het gebruik van het Binomium van Newton

De vorm (a+b)n

 

(2x + 4)3 = (2x)3 + C(3,1)(2x)2.4 + C(3,2)(2x).42 + 43

           = 8x3 + 48x2 + 96x + 64


(3x - 4y)4= (3x)4 - C(4,1) (3x)3(4y) + C(4,2)(3x)2(4y)2 - C(4,3)(3x)(4y)3 + (4y)4

           = 81x4 - 432 y x3 + 864 x2 y2 - 768 x y3 + 256 y4

(x3 - 1/(2x))5

             = (x3)5 - C(5,1)(x3)4 (1/(2x)) + C(5,2)(x3)3 (1/(2x))2 - C(5,3)(x3)2 (1/(2x))3
                 + C(5,4)(x3)(1/2x)4 - (1/(2x))5

             = x15 - 2.5 x11 + 2.5 x7 -1.25 x3 + 0.3125 x-1 - 0.03125 x-5

Afzonderlijke termen berekenen

Bereken de term in x2 in de ontwikkeling van (2x + 1)4
 
   De eerste term bevat x4

   De tweede term bevat x3

   De derde term bevat x2   We berekenen dus de derde term.

   C(4,2) (2x)2.12 = . . . = 24x2
Bereken de term zonder x in de ontwikkeling van (x - 2/x)4
 
   De eerste term bevat x4.

   De tweede term bevat x3. 1/x =  x2

   De derde term bevat x2.( 1/x)2 = x0.  We berekenen dus de derde term.

   C(4,2) x2 (-2/x)2 = 24
Bereken de term in x4 in de ontwikkeling van (x2 + 1/(3x)5
 
  De eerste term bevat (x2)5 = x10

  De tweede term bevat (x2)4.(1/x) = x7

  De derde term bevat  (x2)3.(1/x)2 = x4.   We berekenen dus de derde term.

  C(5,2) (x2)3 (1/3x)2 =  C(5,2) (1/9) x4 = (10/9) x4

Tellen met herhaling

Variaties met herhaling

Neem een verzameling S van n verschillende elementen. Duid nu achtereenvolgens p elementen aan uit die verzameling. Het is toegelaten eenzelfde element meermaals aan te duiden! De rij gevormd door de aangeduide elementen heet een 'variatie met herhaling van n elementen p aan p'.

Voorbeeld:

 
   S = { a,b,c }
   p = 4

De volgende rijtjes zijn variaties met herhaling van 3 elementen 4 aan 4

   a,c,a,a
   b,a,c,c
   c,a,a,b
   b,c,b,b
   b,b,b,b
   b,c,b,c
   . . . .
    enz

Om zo'n variatie te vormen moet je 4 keer kiezen.
Bij elke keuze zijn er 3 mogelijkheden.
Er zijn dus 34 verschillende variaties met herhaling van 3 elementen 4 aan 4
Algemeen:

Neem een verzameling S van n verschillende elementen.
Duid nu achtereenvolgens p elementen uit S aan.
Elk aanduiden kan op n verschillende wijzen gebeuren.
Er zijn dus np verschillende variaties met herhaling van n elementen p aan p We schrijven :

 
                V'(n,p) = np
Voorbeeld 2

Denk aan een getal van 3 cijfers gevormd met de cijfers 1, 4, 7 en 8.
Dit getal is een variatie met herhaling van 4 elementen drie aan drie. Er kunnen 43 = 64 verschillende dergelijke getallen gevormd worden.

 
     448
     174
     117
     711
     888
     ...
     etc

Permutaties met herhaling

Voorbeeld: Neem 3 rode knikkers, 2 blauwe knikkers en 5 gele. Plaats de knikkers op een rij in een zelf gekozen volgorde.
We noemen dit een permutatie met herhaling van de 10 knikkers.

We onderzoeken hoeveel dergelijke rijtjes er kunnen gevormd worden met de gegeven knikkers.

 
        Het totaal aantal mogelijkheden is

        C(10,3).C(10-3,2)

            10!      7!
        = -------.-------
           3!.7!    2!.5!

               10!
        = --------------
           3! . 2! . 5!
In de teller komt het totaal aantal knikkers voor en in de noemer komt het aantal van elke soort voor. Deze methode kan je gemakkelijk veralgemenen.
Algemeen: Neem a gelijke elementen van een eerste soort, b gelijke elementen van een tweede soort en c gelijke elementen van een derde soort. Het aantal verschillende mogelijkheden om al die elementen op een rij te plaatsen is:
 

             (a+b+c)!
        = --------------
           a! . b! . c!
Analoog voor een ander aantal soorten.

Voorbeeld 2:

Maak een getal, met 4 cijfers, gevormd door een rangschikking van de de 4 cijfers 1,2,2,3.

 
  voorbeelden: 2231 ; 1232; 3122; ....


  Het aantal mogelijkheden is

        4!
     --------  = 12
     1!.2!.1!

Combinaties met herhaling

Neem een rij van n verschillende en geordende elementen.
Duid nu achtereenvolgens p elementen aan uit die rij. Het is toegelaten eenzelfde element meermaals aan te duiden! Orden nu de gekozen elementen in dezelfde volgorde als de gegeven elementen. De gelijke elementen worden na elkaar geplaatst. Het resultaat heet een combinatie met herhaling van n elementen p aan p.

Voorbeeld : combinaties maken met herhaling van 5 elementen 6 aan 6.
A = (a,b,c,d,e) dus n= 5 . Kies p = 6
Dan zijn (a, a, b, d, d, d) ; (b, b, b, c, d, e) ; (c, c, c, c, c, c)
drie voorbeelden van combinaties met herhaling van 5 elementen 6 aan 6.

Het aantal herhalingscombinaties met n elementen p aan p noteren we als C'(n,p).

We hernemen vorig voorbeeld en tonen aan hoe het aantal mogelijkheden kan gevonden worden. Eerst merken we op dat dergelijke herhalingscombinatie ondubbelzinnig kan voorgesteld worden door middel van stippen en strepen. Een streep betekent 'ga naar volgende letter'.

 
(a,a,b,d,d,d)     <=>   .././/.../
(b,b,b,c,d,e)     <=>   /.../././.
(c;c;c;c;c;c)     <=>   //......//
Elk symbool bestaat uit 10 elementen, juist 6 punten en juist 4 strepen. Met elke combinatie correspondeert juist 1 symbool en omgekeerd.
We kunnen zo'n symbool bouwen door het plaatsen van juist 6 punten in 10 vakjes. De overige vakjes worden opgevuld met strepen. Het plaatsen van de 6 punten kan juist op C(10,6) manieren gebeuren.
Dus, C'(5,6) = C(5+6-1,6)

Veralgemenend kan men bewijzen dat C'(n,p) = C(n+p-1,p)

Voorbeeld

Je hebt een doos rode snoepjes, een doos gele snoepjes en een doos zwarte snoepjes. Op hoeveel manieren kan je 5 snoepjes kiezen?

De mogelijke keuzes zijn combinaties met herhaling van 3 elementen 5 aan 5. Het aantal keuzemogelijkheden is C'(3,5) = C(7,5) = 21.

Voorbeeld 2:
Hoeveel oplossingen heeft de ongelijkheid p + q + r < 11 als je weet dat p, q en r natuurlijke gehele getallen zijn?

Neem de letters a, b, c en d. Wijs achtereenvolgens 10 maal zo'n letter aan, en schrijf de aangewezen letters in alfabetische volgorde. Er ontstaat een rijtje van 10 letters bijvoorbeeld aabbbcdddd
Met zo' rijtje correspondeert juist 1 oplossing van p + q + r < 11. Neem p = het aantal maal a in het rijtje, q = het aantal maal b en r = het aantal maal c. In het voorbeeld is p=2, q=3, r=1 en p + q + r <11.

Omgekeerd correspondeert met elke oplossing van p + q + r <11 juist 1 zo'n rijtje. Bijvoorbeeld, met p=3, q=3 ,c=2 correspondeert aaabbbccdd.

Voorbeelden:

 
aabbbcdddd  <=> 2+3+1  < 11
bbbccccddd  <=> 0+3+4  < 11
bbbbbbbbbb  <=> 0+10+0 < 11
dddddddddd  <=> 0+0+0  < 11
aaaabbbccc  <=> 4+3+3  < 11
Het aantal rijtjes die kunnen gemaakt worden is het aantal herhalingscombinaties van 4 elementen 10 aan 10. Dus C'(4,10) = C(13,10) = C(13,3).

Uitgewerkte oefeningen

 
Opgeloste oefeningen over variaties, permutaties en combinaties kan je via deze link vinden.
 

Inleiding op kansrekening

Hier vind je links naar cursussen en onderwerpen over kansrekening.

Hierna nog enkele links naar engelstalige cursussen en onderwerpen over kansrekening.


Engelse tutorials op het net over telproblemen



MATH-abundance - tutorial

Site adres is http://home.scarlet.be/math/nl/

Zend alle vragen, foutmeldingen en opmerkingen naar Johan.Claeys@ping.be
Het onderwerp of subject van de mail moet het woord 'wiskunde' bevatten omdat andere mails weggefilterd worden.