telprobleem
Opgave - CanMO 1989 vraag 1
De natuurlijke getallen $1,2,...,n$ worden op gerangschikt zodat iedere waarde ofwel strikt groter is dan alle vorige waarden, ofwel strikt kleiner is dan alle vorige waarden. Op hoeveel manieren kan die gedaan worden?
- login om te reageren
Oplossing
Als we een rij reeds gestart zijn getallen tussen $n$ en $m$, dan geldt dat er een lager getal zal volgen (-) of een groter getal (+) dan voorgaande getallen.
Het nieuwe getal is uniek bepaald door het teken (+ of -) aangezien als we niet $n-1$ of $m+1$ nemen, dat getal later zal volgen en zowel groter als kleiner dan voorgaande getallen zal zijn.
Nemen we dus $k$ als beginterm, dan volgen er $k -1$ minnen en $n-k$ plussen, verdeeld over $n-1$ plaatsen.
Zo'n volgorde van plusjes en minnen zal een rangschikking uniek bepalen.
Het aantal mogelijkheden om dat te doen wordt gegeven door $\binom{n-1}{k-1}=\frac{(n-1)!}{(n-k)!(k-1)!}$.
Het totaal aantal mogelijkheden is de sommatie van deze uitdrukking voor alle $k$ van $1$ tem $n$. M.a.w.: $\sum_{k=1}^{n}\frac{(n-1)!}{(n-k)!(k-1)!}=\sum_{k=0}^{n-1}\binom{n-1}{k}=(1+1)^{n-1}=2^{n-1}.$