Tag archieven: combinatoriek

Een telprobleem

Geplaatst op door

Op hoeveel manieren kan je een rijtje van 10 symbolen 0,1 of 2 maken zodat er nooit twee enen of twee twee na elkaar voorkomen?

Goed is dus 1200121001 en fout is 0012011202 omdat hier twee enen na elkaar voorkomen. 

Vorm de matrix

    \[A=\begin{pmatrix} 1&1&1\\1&0&1\\1&1&0\end{pmatrix}\]

Nummer de rijen en de kolommen met 0,1en 2

a_{00}=1 betekent: er is een mogelijkheid om na een 0 een tweede nul te plaatsen.
a_{11}=0 betekent : na een 1 kan er geen 1 komen.
a_{12}=1 betekent: na een 1 kan er een 2 komen.

Het is duidelijk dat de som van de elementen van deze matrix A het aantal goede tweetallen is: 00,01,02,10,12,20,21 . Er zijn 7 goede tweetallen.

Net zoals bij een directe wegenmatrix (soort overgangsmatrix) zal de som van de elementen van A^9 dan het aantal goede tientallen geven:

    \[A^9=\begin{pmatrix} 1393&985&985\\985&696&697\\985&697&696\end{pmatrix}\]

Het antwoord op de gestelde vraag is dan 8119.

Stelling van Van der Waerden

Geplaatst op door

In de wiskunde zijn er verschillende  stellingen die elk op hun eigen manier zeggen dat totale wanorde onmogelijk is.  Zo hebben we bijvoorbeeld het vermoeden van Baudet: Als je de hele verzameling \mathbb{N} in twee verzamelingen A en B verdeelt, is het dan noodzakelijk zo dat (ten minste) één van die twee verzamelingen willekeurig lange rekenkundige rijtjes bevat?

De Nederlandse wiskundige Van der Waerden publiceerde in 1927 een bewijs. In het artikel staat een algemenere bewering :  voor elk paar positieve gehele getallen r en k is er een getal N zodanig dat indien men {1, 2, …, N }  in r  klassen verdeelt, er minstens een klasse is die een rekenkundige rij van lengte k bevat. Het kleinste getal N waarvoor dit geldt noemt men het Van der Waerden-getal W(r,k).

Zo is bijvoorbeeld W(2,3) =  9. Een kleinere waarde is er niet want {{1,2,4,5},{3,4,6,8}} is een verdeling van {1,2,3,4,5,6,7,8} in twee delen die geen rekenkundige rij met 3 elementen bevat. In onderstaande tekening kleur je de getallen van 1 tot en met 9 in 2 kleuren; je ziet dat je steeds een rekenkundige rij van drie elementen krijgt in eenzelfde kleur.

Derangement

Geplaatst op door

Een derangement is een permutatie zonder vaste punten, met andere woorden een ordening waar geen enkel element op de juiste plaats staat.  Het aantal derangements van n verschillende elementen wordt aangeduid met !n : subfaculteit. Het probleem van het tellen van het aantal derangementen werd in 1708 voor het eerst beschouwd door Pierre Raymond de Montmort, die het probleem oploste in 1713, ongeveeer tegelijkertijd met Nicolaas Bernoulli.

Voor 3 elementen zijn er 3! = 6 permutaties. De ordeningen  312 en 231 zijn derangements. Het zijn de enige, dus !3=2. Voor 4 elementen is, het al wat moeilijker:

Hierboven zie je de 24 permutaties van de 4 elementen {1,2,3,4}. De blauwe zijn de derangements, dus !4=9. Je kan nagaan dat !5=44, !6= 265 en !7=1854. Er zijn echter ook formules beschikbaar om de subfaculteiten uit te rekenen:

    \[\text{!n}=(n-1)[!(n-1)+!(n-2)]\]

    \[\text{!n}=n!\sum_{i=0}^n\dfrac{(-1)^i}{i!}\]

 

Uit deze laatste formule kan je de verhouding tussen !n en n! afleiden:

    \[\dfrac{!n}{n!}=\dfrac{1}{e} \approx 0,368\]

Opgave 28

Geplaatst op door

Hoeveel niet-congruente driehoeken met gehele zijden en omtrek 2019 kan men construeren?

Antwoord

  • Elke zijde van een driehoek is kleiner dan de som van de twee andere zijden. Bijgevolg is de langste zijde van de gezochte driehoeken \leq 1009.
  • Stel dat de langste zijde gelijk is aan 1009, dan kunnen de andere twee zijden gelijk zijn aan : (1009,1),(1008,2),\cdots,(505,505). Er zijn dus 505 mogelijke driehoeken.
  • Stel dat de langste zijde gelijk is aan 1008, dan kunnen de andere zijden gelijk zijn aan: (1008,3),(1007,4),\cdots,(506,505). Er zijn dus 503 mogelijke driehoeken.
  • Stel dat de langste zijde gelijk is aan 1007, dan kunnen de andere zijden gelijk zijn aan: (1007,5),(1006,6),\cdots,(506,506). Er zijn dus 502 mogelijke driehoeken.
  • Daal verder af…
  • Stel dat de langste zijde gelijk is aan 674, dan kunnen de andere zijden gelijk zijn aan: (674,671),(673,672). Er zijn dus 2 mogelijke driehoeken.
  • Tenslotte blijft er de gelijkzijdige driehoek met zijde 673 over.
  • Het totaal aantal mogelijkheden is S=505+503+502+500+\cdots+4+2+1.
  • Herschikking geeft S=505+(503+1)+(502+2)+(500+504)+\cdots. Dit geeft S=505+504 \times 168 =85177.

Delannoy getallen

Geplaatst op door

Beschouw in het vlak de punten P(x,y) met  natuurlijke getallen als coördinaten .Je kan je verplaatsen in het vlak volgens de vectoren (1,0) , (0,1)  en (1,1). Het aantal manieren waarop men vanuit de oorsprong het punt P(m,n) kan bereiken noemt men het Delannoy getal d(m,n), vernoemd naar de Franse legerofficier en amateur wiskundige Henri-Auguste Delannoy (28 sept 1833 – 5 febr 1915). Bij definitie stellen we d(0,0)=1.

Onderstaande tekening laat zien dat er bijvoorbeeld 13 mogelijke manieren zijn om het punt P(2,2) te bereiken:

Een tabel met enkele waarden van de Delannoy getallen :

We geven enkele eigenschappen:

  • d(m,0) = d(0,n) = 1
  • Er is een recursief verband tussen deze getallen: d(m,n) = d(m – 1,n) + d(m,n – 1) + d(m – 1,n – 1): elk getal in bovenstaande tabel is de som van zijn linkerbuur, zijn bovenbuur en het getal linksboven. Dit wordt beter geïllustreerd als we de tabel geven in de vorm van de driehoek van Pascal. ( teken de diagonalen van bovenstaande tabel). Nu is elk getal de som van de driehoek erboven.
  • We stellen de verplaatsingen over (1,0), (0,1) en (1,1) respectievelijk voor door O,N en D. Wanneer we k keer D gebruiken om P(m,n) te bereiken,  moeten we m – k keer O en n – k keer N gebruiken. Om te berekenen op hoeveel manieren dit kan, maken we gebruik van de formule van de herhalingspermutaties : we moeten
    k + (m – k) + (n – k ) = m + n – k symbolen rangschikken, waarvan er k van het soort D zijn , m – k van het soort O en  n – k van het soort N. We vinden dus voor elke waarde van k kleiner of gelijk aan het minimum van m en n als aantal mogelijkheden:

        \[\dfrac{(m+n-k)!}{k! (m-k)! (n-k)!}\]

    In het totaal heb je dan :

        \[\sum_{k=0}^{ min(m,n)}\dfrac{(m+n-k)!}{k! (m-k)! (n-k)!}\]

  • Op de tweede rij en tweede kolom vinden we alle oneven getallen :
    d(m,1) = 2m+1. Dit is gemakkelijk te bewijzen met bovenstaande formule