 |
A B. 4793. feladat (2016. április) |
B. 4793. Hány olyan permutációja van az \(\displaystyle 1, 2, 3, \ldots, n\) számoknak, amelyekben pontosan
\(\displaystyle a)\) egyszer,
\(\displaystyle b)\) kétszer fordul elő, hogy két szomszédos helyen álló szám közül a bal oldali a nagyobb?
(6 pont)
A beküldési határidő 2016. május 10-én LEJÁRT.
Megoldás. a) Legyen egy ilyen permutáció \(\displaystyle a_1,a_2,\dots,a_n\). A feltétel szerint pontosan egy olyan \(\displaystyle 2\leq i\leq n\) van, amelyre \(\displaystyle a_{i-1}>a_i\). Ekkor az \(\displaystyle a_1<a_2<\dots<a_{i-1}\) és az \(\displaystyle a_i<a_{i+1}<\dots<a_n\) részek is monoton növekedőek. Így, ha kiválasztjuk, hogy mi legyen az \(\displaystyle A=\{a_1,a_2,\dots,a_{i-1}\}\) halmaz, akkor a sorrendjük már egyértelmű, és a többi szám sorrendje szintén egyértelmű. Továbbá \(\displaystyle a_{i-1}>a_i\) csak akkor nem teljesül, ha \(\displaystyle a_1<a_2<\dots<a_n\), vagyis ha \(\displaystyle \{a_1,a_2,\dots,a_{i-1}\}=\{1,2,\dots,i-1\}\), azaz az első \(\displaystyle i-1\) számot választottuk ki. Az \(\displaystyle A\subseteq \{1,2,\dots,n\}=N\) halmaz megválasztására \(\displaystyle 2^n\) féle lehetőség van, ezek közül pontosan akkor nem kapunk megfelelő permutációt, ha \(\displaystyle A\) üres, minden elemet tartalmaz, vagy valamely \(\displaystyle 2\leq i\leq n\) mellett \(\displaystyle A=\{1,2,\dots,i-1\}\). Ez azt jelenti, hogy a megfelelő permutációk száma \(\displaystyle 2^n-(n+1)\).
b) A feladat b) részében szereplő feltételt egy \(\displaystyle a_1,a_2,\dots,a_n\) permutáció pontosan akkor elégíti ki, ha valamely \(\displaystyle 2\leq i<j\leq n\) mellett \(\displaystyle a_1<a_2<\dots<a_{i-1}\), \(\displaystyle a_i<a_{i+1}<\dots<a_{j-1}\), \(\displaystyle a_j<a_{j+1}<\dots<a_n\), továbbá \(\displaystyle a_{i-1}>a_i\) és \(\displaystyle a_{j-1}>a_j\). Legyen \(\displaystyle A=\{a_1,a_2,\dots,a_{i-1}\}\), \(\displaystyle B=\{a_i,a_{i+1},\dots,a_{j-1}\}\), \(\displaystyle C=\{a_j,a_{j+1},\dots,a_n\}.\) Az \(\displaystyle A,B,C\subseteq N\) halmazok páronként diszjunktak és \(\displaystyle A\cup B\cup C=N\). A (feltételeket kielégítő) permutációt \(\displaystyle A,B,C\) egyértelműen meghatározza, hiszen a permutáció az \(\displaystyle A\)-beli elemek növekvő felsorolásával kezdődik, majd következnek \(\displaystyle B\) elemei szintén növekvő sorrendben, végül \(\displaystyle C\) elemei növekvő sorrendben. Pontosan akkor kapunk megfelelő permutációt, ha:
(i) \(\displaystyle A\) legnagyobb eleme nagyobb, mint \(\displaystyle B\) legkisebb eleme, továbbá
(ii) \(\displaystyle B\) legnagyobb eleme nagyobb, mint \(\displaystyle C\) legkisebb eleme.
Minden megfelelő permutációt csak egyetlen \(\displaystyle (A,B,C)\) hármasnál kapunk meg. Az \(\displaystyle \{1,2,\dots,n\}\) halmaz minden eleme 3 féle helyre kerülhet: \(\displaystyle A\)-ba, \(\displaystyle B\)-be, vagy \(\displaystyle C\)-be, így \(\displaystyle 3^n\) darab \(\displaystyle (A,B,C)\) hármas adható meg úgy, hogy azok diszjunkt uniója \(\displaystyle N\) legyen. Számoljuk meg, hogy hány olyan van közöttük, ami nem a feltételnek megfelelő permutációt ad. Azon hármasok száma, amelyeknél \(\displaystyle A\), \(\displaystyle B\), \(\displaystyle C\) valamelyike üres \(\displaystyle 3\cdot 2^n-3\), ugyanis ha például \(\displaystyle A=\emptyset\), akkor a \(\displaystyle B\) halmaz \(\displaystyle 2^n\)-féle lehet (és ez \(\displaystyle C\)-t már meghatározza), azonban az ebből adódó \(\displaystyle 3\cdot 2^n\) darab hármas között azok a hármasok, amelyeknek két tagja is üres, kétszer szerepelnek. Ilyen hármasból három van: \(\displaystyle (\emptyset,\emptyset,N),(\emptyset,N,\emptyset),(N,\emptyset,\emptyset)\), vagyis azon hármasok száma, ahol a három halmaz közül legalább az egyik üres valóban \(\displaystyle 3\cdot 2^n-3\). A továbbiakban csak olyan hármasokkal foglalkozunk, amelyekben \(\displaystyle A,B,C\) egyike sem üres. Ha \(\displaystyle A\) legnagyobb eleme kisebb, mint \(\displaystyle B\) legkisebb eleme és \(\displaystyle B\) legnagyobb eleme kisebb, mint \(\displaystyle C\) legkisebb eleme, akkor az \(\displaystyle 1,2,\dots,n\) permutációt kapjuk, ami nem megfelelő. Ilyen hármasból \(\displaystyle \binom{n-1}{2}\) van, hiszen az \(\displaystyle A\) legnagyobb elemét és \(\displaystyle B\) legnagyobb elemét tartalmazó halmaz az \(\displaystyle N\setminus \{n\}\) halmaz tetszőleges 2 elemű részhalmaza lehet. Végül számoljuk meg, hány hármas esetén kapunk olyan permutációt, melyeknél (i) és (ii) közül pontosan az egyik teljesül. Egy ilyen hármas olyan permutációt ad, amiben pontosan egyszer fordul elő, hogy két szomszédos elem közül a bal oldali a nagyobb. Valamint annak is teljesülnie kell, hogy (i) sérülése esetén ettől a ponttól balra, (ii) sérülése esetén ettől a ponttól jobbra legalább két elem van.
Vegyünk egy a)-nak eleget tevő permutációt, és vizsgáljuk meg, hány \(\displaystyle (A,B,C)\) hármas adja ezt. Ha a bal oldali részben csak egy elem van, akkor ez az elem alkotja \(\displaystyle A\)-t, míg \(\displaystyle B\) megválasztására \(\displaystyle n-2\) lehetőség van (a megmaradó elemek közül kell kiválasztunk az \(\displaystyle i\) darab legkisebbet valamely \(\displaystyle 1\leq i\leq n-2\)-re). Ehhez hasonlóan, ha a jobb oldali részben csak egy elem van, akkor \(\displaystyle C\)-ben csak ez az elem van, míg \(\displaystyle B\)-re \(\displaystyle n-2\) lehetőség van. Ha a bal oldali részben \(\displaystyle 2\leq k\leq n-2\) elem van, a jobb oldaliban pedig \(\displaystyle n-k\), akkor ha a bal oldali rész lesz \(\displaystyle A\cup B\) ((i) sérülése esetén), akkor a lehetőségek száma \(\displaystyle k-1\), ha pedig a jobb oldali rész lesz \(\displaystyle B\cup C\) ((ii) sérülése esetén), akkor a lehetőségek száma \(\displaystyle (n-k)-1\). Így a lehetőségek száma összesen ismét \(\displaystyle (k-1)+(n-k-1)=n-2\). Ez azt jelenti, hogy az a)-nak eleget tevő permutációk mindegyikét \(\displaystyle (n-2)\)-szer kapjuk meg egy hármasból.
Tehát a b)-nek megfelelő permutációk száma \(\displaystyle 3^n-(3\cdot 2^n-3)-\binom{n-1}{2}-(n-2)(2^n-n-1)=3^n-(n+1)2^n+\frac{n^2+n}{2}\). (Ha \(\displaystyle n\leq 2\), akkor nincs ilyen permutáció, és a kapott formula is 0-t ad.)
Megjegyzés. A feladat kapcsolódik az A. 671. feladathoz.
Statisztika:
A KöMaL 2016. áprilisi matematika feladatai