Bewijzen met verhaaltjes

Deze bewijstechniek bestaat er in ‘een verhaaltje te vertellen. 

Stel ik wil volgende formule “bewijzen”:  voor n\geq p\geq 2

    \[p(p-1)\binom{n}{p}=n(n-1)\binom{n-2}{p-2}\]

Je zou natuurlijk, gebruikmakend van de definitie van de binomiaalgetallen, beide leden kunnen uitrekenen, en vaststellen dat beide resultaten hetzelfde zijn. Maar proberen we dit eens anders in te kleden. Je hebt binnen een politieke partij n kaderleden, waaruit je een dagelijks bestuur van p personen moet kiezen, met hierin een voorzitter en een ondervoorzitter. Dit kan je doen op twee manieren :

  • Kies eerst p personen. Dit kan op \binom{n}{p}. Kies hier uit een voorzitter: p mogelijkheden. Kies dan een ondervoorzitter: p – 1 mogelijkheden. Samen geeft dit dus, als aantal mogelijkheden:

        \[p(p-1)\binom{n}{p}\]

  • Maar je kan eerst een voorzitter kiezen uit de n kaderleden. Dit kan je op n mogelijkheden. Kies vervolgens een ondervoorzitter: n – 1 mogelijkheden. Kies tenslotte nog p-2 ander personen om je dagelijks bestuur te vervolledigen. dit kan op \binom{n-2}{p-2} manieren. Zo krijg je in het totaal als mogelijkheden:

        \[n(n-1)\binom{n-2}{p-2}\]

Hiermee is de gevraagde formule bewezen!

Ster van David

Iedereen kent wel de driehoek van Pascal met de binomiaalgetallen. In die driehoek kan je mooie verbanden zien: je vindt er de natuurlijke getallen in , de driehoeksgetallen….Gekend is zeker ook de stelling van Stiefel. Minder bekend is de stelling van de Davidster:

In de tekening hierboven zijn de rijen van de driehoek van Pascal als kolommen weergegeven. De  grootste gemene delers van de getallen op de hoekpunten van de gegeven driehoeken zijn gelijk: De grootste gemene deler van \binom{n-1}{k-1},\binom{n}{k+1},\binom{n+1}{k} is gelijk aan de grootste gemene deler van \binom{n-1}{k-},\binom{n}{k-1},\binom{n+1}{k+1} . Dit verband werd in 1972 ontdekt door de Amerikaanse wiskundige Henry Gould.

Bovendien geldt er dat het product van de getallen op de hoekpunten van de driehoeken gelijk is

Een voorbeeld:

 

Kwadraten in de driehoek van Pascal

In de driehoek van Pascal kan je veel verbanden vinden. Vandaag gaan we op zoek naar kwadraten.

  • Kijk naar de derde kolom van de driehoeksgetallen 1,3,6,10,… en tel daar de elementen twee per twee op en je vindt de rij 4,9,16,25,… Hoe kan je dit verklaren?  De som van de elementen is altijd van de vorm

        \[\binom{n}{2}+\binom{n+1}{2}\]


    Uitrekenen geeft \frac{1}{2}n(n-1)+\frac{1}{2}n(n+1)=n^2.
  • Kijk naar de vierde kolom 1,4,10,20,35,56,…en bereken het verschil van de derde en de eerste, de vierde en de tweede enz. , dan vorm je de rij 9,16,25,… Verklaring?

        \[\binom{n+2}{3}-\binom{n}{3}\]

    Uitrekenen met de formule van Stiffel geeft: \Big(\binom{n+2}{3}-\binom{n+1}{3}\Big)+\Big(\binom{n+1}{3}-\binom{n}{3}\Big)=\binom{n+1}{2}+\binom{n}{2}=n^2.

Formules met binomiaalgetallen

Het binomiaalgetal \binom{n}{p} berekent het aantal p-combinaties van n elementen; dit is het aantal mogelijkheden om p elementen te nemen uit n beschikbare elementen. Hierbij is  herhaling niet toegestaan en speelt de volgorde van de elementen geen rol.

Als 0 \leq p \leq n, dan kennen we de formule

    \[\binom{n}{p}=\dfrac{n!}{p!(n-p)!}\]

Om verbanden tussen de binomiaalgetallen te bewijzen kunnen we gebruik maken van bovenstaande formule. Vaak geeft dit aanleiding tot technisch moeilijk rekenwerk. Vandaar dat we in volgende sectie een andere werkmethode willen geven, steunend op eenvoudige begrippen uit de verzamelingenleer. Lees hierover volgend artikel.

Opgave 3

Bepaal het aantal oneven binomiaalgetallen in (a+b)^n.

Antwoord