Stapel permutaties

Een stapel register kan eenvoudig voorgeteld worden als een systeem met een  ingang(I) en een uitgang (U) met daartussen een wachtplaats( stapel of stack):

Neem de rij 123  en voer de volgende instructies uit: 3 in de stapel, 2 in de stapel, 2 uit de stapel, 1 in de stapel, 1 uit de stapel, 3 uit de stapel . De rij cijfers die aan de uitgang verschijnt is dan 213.

We zeggen dat 213 een stapelpermutatie is, omdat ze met een eindig aantal in en uit bewegingen kan bekomen worden  van de oorspronkelijke  rij 123. Van de zes ‘gewone’ permutaties van 123 is enkel 231 geen stapelpermutatie. Er zijn dus 5 stapelpermutaties van de rij 123.

Zijn er n elementen gegeven, dan is het aantal stapelpermutaties gegeven door

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

Dit getal noemen we het n-de Catalangetal. We spreken ook af dat cat(0)=1. De eerste Catalaanse getallen zijn: cat(1)=1,cat(2)=2,cat(3)=5,cat(4)=14,cat(5)=42.

De naamgeving verwijst naar de Belgische wiskundige Eugene Catalan (Brugge 1814-Luik 1894). Catalaanse getallen vormen een fascinerende rij in de wiskunde, bekend om hun talrijke verschijningen in verschillende combinatorische problemen. Catalaanse getallen zijn een voorbeeld van hoe wiskundige structuren en patronen op onverwachte manieren kunnen opduiken. Een paar voorbeelden:

Een Dyck-pad van lengte 2n is een pad in een rooster dat niet onder de diagonaal komt en van naar loopt. Het aantal van dergelijke paden wordt gegeven door cat(n).

Het aantal manieren om een convexe -hoek op te splitsen in driehoeken met niet-overlappende diagonalen is gelijk aan cat(n).

Het aantal manieren om 2n punten op een cirkelomtrek te verbinden met koorden die elkaar niet snijden is cat(n).

 

 

Nootje 48

Bepaal alle drietallen natuurlijke getallen a,b,c waarvoor a.b.c=1989 en a+b+c=89

Antwoord

  • De oplossing is symmetrisch in a,b en c.
  • Redeneren we eventjes op c, dan moet c moet een deler zijn van 1989=3^2.13.17.
  • De delers van 1989 zijn: 1,3,9,13,17,39,51,117,153,221,663,1989.
  • Bij een keuze van c moeten we nog het stelsel oplossen:

        \[\begin{cases}a+b=89-c \\ a.b=\frac{1989}{c}\end{cases}\]

  • Noteer S=a+b en P=a.b, dan zijn a en b oplossingen van de vergelijking

        \[x^2-Sx+P=0\]

  • S=89+c; Omdat c oneven is , zal S dus even zijn en moet de discriminant S^2-4P een kwadraat zijn van een even getal ( anders zijn a en b geen natuurlijke getallen).
  • Voor c=1 is S=90 en P=1989. In dat geval is de discriminant gelijk aan 144 en vinden we dat a=39 en b=51.
  • Voor c=1 krijgen we dus als oplossingen de drietallen (39,51,1) en (51,39,1)
  • Door de symmetrie zijn de andere oplossingen dan (1,39,51),(1,51,39),(39,1,51),(51,1,39).

Spiraal van Ulam

Je kan volgend rooster van natuurlijke getallen maken in de vorm van een spiraal:

De wiskundige Stanislaw Ulam kreeg in 1963 het idee om e priemgetallen hierbij aan te duiden 

Hij zag, tot zijn verbazing, dat de priemgetallen de neiging hebben om zich op diagonalen van de spiraal te bevinden. De diagonalen zijn ook zichtbaar wanneer er heel veel getallen in een spiraal worden geplaatst. Het opvallende is, dat priemgetallen zich meer op bepaalde diagonalen bevinden dan op andere. De reden hiervoor is alsnog onduidelijk.

Een regendruppel…

Een regendruppel met massa m valt onder invloed van de zwaartekracht en ondervindt een wrijving die recht evenredig mag genomen worden met de snelheid v. Bereken de snelheid in functie van t.

  • Volgens de wetten van Newton is de kracht waaraan de regendruppel onderhevig is: F=m.a , waarbij a de versnelling is van de druppel.
  • Deze kracht F is de resultante van de zwaartekracht F_1=m.g en de wrijving F_2=-k.v, waarbij k een evenredigheidsfactor is.
  • Dus

        \[m.a=m.g-kv\]

  • Nu weten we dat a=v'. Bijgevolg is m.v'=m.g-k.v.
  • We kunnen dit herschrijven als \frac{dv}{m.g-kv}=\frac{dt}{m}.</li> <li>Als we beide kanten integreren krijgen we :-\frac{1}{k}\ln (m.g-k.v)=\frac{t}{m}+c, waarbij c de integratieconstante voorstelt.</li> <li>Uitwerken geeft:m.g-k.v=A.e^{-\frac{kt}{m}.</li> <li>Alst=0, veronderstellen we datv=0. Hieruit vinden we datA=m.g$.
  • Vullen we dit in en lossen we op naar v, dan vinden we uiteindelijk

        \[v=\frac{m.g}{k}\Big( 1-e^{-\frac{kt}{m}\Big)\]

  • We zien dat na zekere tijd de regendruppel mat praktisch constante snelheid zal vallen.