Feladat:	B.4793	Korcsoport: 16-17	Nehézségi fok: nehéz
Megoldó(k):	Fuisz Gábor
Füzet:	2016/október, 410 - 411. oldal		PDF  |  MathML
Témakör(ök):	Feladat, Természetes számok, Permutációk
Hivatkozás(ok):	Feladatok: 2016/április: B.4793

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.   Megoldás. $a)$ Az ilyen permutációk esetén egy bizonyos számig a sorozat monoton növekvő, utána egy csökkenés, majd ismét monoton növekvő rész következik. Osszuk két halmazba a számokat, legyenek ezek az $x$ és az $y$ halmazok. Rendezzük $x$-et és $y$-t is növekvő sorrendbe, végül írjuk le $x$, majd $y$ elemeit egymás után. A számok két halmazba való rendezését $\left(2^n\right)$-féleképpen tehetjük meg. Ezek közül azok az elrendezések nem teljesítik a feltételt, melyek végig monoton növekedőek. Ez vagy akkor van így, ha az egyik halmaz üres halmaz, vagy pedig akkor, ha $x$ legnagyobb eleme kisebb, mint $y$ legkisebb eleme, vagyis ahol $x$ minden eleme kisebb $y$ összes eleménél. (A halmazokon belül biztos nem lesz balra mutató reláció, mert azokat rendeztük.) Ekkor $x$-be 1-től $k$-ig kerülnek a számok, $y$-ba pedig $\left(k+1\right)$-től $n$-ig, ahol $k$ legkisebb értéke 1, legnagyobb értéke pedig $n-1$. Ez $n-1$ lehetőséget jelent. (Egyszerűbben is ki lehet számolni, hiszen az 1-től $n$-ig terjedő számokat sorban egymás után írva, előttük-köztük-mögöttük összesen $n+1$ hely van, amiből 1-et kell kiválasztani. Ha pl. az előtte levőt választjuk, akkor az $x$ üres halmaz lesz.) Minden ilyen rendezésnek megfeleltethető egy jó permutáció és viszont. Tehát $2^n-2-\left(n-1\right)=2^n-n-1$ a jó permutációk száma. $b)$ Ebben az esetben osszuk három halmazba a számokat, $x$-be, $y$-ba és $z$-be, majd a halmazokon belüli rendezés után írjuk le egymás után $x$, $y$, végül $z$ elemeit. A három halmazt $3^n$-féleképpen hozhatjuk létre. Ebből le kell vonni a rossz elrendezéseket, vagyis azokat, amikor 0 vagy 1 balra mutató reláció van a permutációban. (Ha $x$, $y$ vagy $z$ üres halmaz, akkor is 0 vagy 1 a balra mutató relációk száma.) Ez akkor fordulhat elő, ha $x$-ben minden elem kisebb $y$ minden eleménél, vagy ha $y$ minden eleme kisebb $z$ elemeinél. Mindkét eset tekinthető úgy, mintha a számokat két halmazba rendeznénk, az $A=x\cup y$ és a $B=z$, illetve az $A=x$ és a $B=y\cup z$ halmazba. Az elemeket az $A$ és a $B$ halmazba $2^n$-féleképp helyezhetjük el, majd $n+1$ helyen húzhatjuk meg a ,,belső'' halmazok határát. Tehát $3^n$-ből le kell vonnunk $2^n\left(n+1\right)$-et. Azonban kétszer vontuk le azokat az eseteket, amikor egyszerre teljesül, hogy $x$-ben minden elem kisebb $y$ minden eleménél, és $y$ minden eleme kisebb $z$ elemeinél. Vagyis ezeknek számát egyszer hozzá kell adni. Ebben az esetben $n+1$ helyből kell kettőt kiválasztani, ami $\left(\genfrac{}{}{0ex}{}{n+1}{2}\right)=\frac{\left(n+1\right)n}{2}$ eset. Így a megoldás: $\begin{array}{c}{\displaystyle 3^n-2^n\left(n+1\right)+\frac{n\left(n+1\right)}{2}\mathrm{.}}\end{array}$   Megjegyzések. 1. A feladat kapcsolódik az A. 671. feladathoz. 2. A megoldásban többen hivatkoztak egy tételre, amiből egy sorban kijött a megoldás. Az eddigi Versenykiírás alapján ezt elfogadtuk, azonban a 2016‐2017-es tanévtől ez módosul.