mooie rijtjes

Opgave - NWO 2012 vraag 5

De getallen 1 tot en met 12 worden in een rijtje achter elkaar gezet. Het aantal manieren waarop
dit kan is 12×11×10×· · ·×1. We noemen zo'n rijtje mooi als er precies één getal in staat dat kleiner is dan het getal dat er direct aan voorafgaat.
Hoeveel van de 12×11×10×· · ·×1 rijtjes zijn mooi?

Oplossing

Laten we het de plaats van het getal dat kleiner is dan het voorafgaande het breekpunt noemen. Aangezien het breekpunt de enige plaats is waar de rij daalt moeten alle getallen voor het breekpunt stijgen en alle getallen na en met het breekpunt stijgen. Aangezien er altijd juist 1 mannier is om verschillende getallen stijgend te ordenen is het aantal rijen die voor het breekpunt kunnen staan gelijk aan het aantal mogelijke combinaties van getallen die ervoor kunnen staan. Voor elke rij voor het breekpunt is er maar 1 mogelijk rij na het breekpunt.

De vraag is dus equivalent met: hoeveel verschillende combinaties kunnen er voor het breekpunt staan?
Een combinatie uit {1,2,...,12} kan pas een combinatie voor het breekpunt zijn als en slechts als er een element uit {1,2,...,12} en niet van de combinatie bestaat dat kleiner is dan dan het grootste element van de combinatie.

Voor elke lengte van rij voor het breekpunt is er juist 1 combinatie die niet aan de voorwaarde voldoet, namelijk de combinatie {1,2,...,n} met n de lengte van de rij.
Indien dat niet het geval is, bevat de tweede deelrij een element uit die {1,2,...,n} dat bijgevolg kleiner zal zijn dan het grootste element van de genomen deelrij, dat als breekpunt kan dienen.

Dus voor een rij voor het breekpunt van lengte n zijn er $C^n_{12}-1$ mogelijkheden. De rij voor het breekpunt kan een lengte van 1 tot 11 hebben dus is het totaal aantal mogelijkheden $\sum_{n=1}^{11}(C^n_{12} - 1) = \sum_{n=1}^{11}(C^n_{12})-11$
Nu merken we met het binomium van Newton op dat $(1+1)^{12}=\sum_{n=0}^{12} (C^n_{12})$
Hieruit volgt dat het totaal aantal mogelijkheden gelijk is aan $\sum_{n=1}^{11} (C^n_{12})-11= 2^{12} - 2-11= 4096 - 13= 4083$