 |
Az A. 671. feladat (2016. május) |
A. 671. Mutassuk meg, hogy
\(\displaystyle 0< \sum_{i=0}^k {(-1)}^{i}\binom{n+1}{i}{(k+1-i)}^n < n! \)
teljesül tetszőleges \(\displaystyle 0<k<n\) egész számok esetén.
(5 pont)
A beküldési határidő 2016. június 10-én LEJÁRT.
Megoldásvázlat. Az \(\displaystyle 1,2,\ldots,n\) számok egy \(\displaystyle (a_1,\ldots,a_n)\) permutációjáról mondjuk azt, hogy \(\displaystyle k\)-szor csökken, ha pontosan \(\displaystyle k\) különböző \(\displaystyle 1\le i<n\) index létezik, amikor \(\displaystyle a_i>a_{i+1}\). Jelölje \(\displaystyle E(n,k)\) a \(\displaystyle k\)-szor csökkenő permutációk számát. Megmutatjuk, hogy
| \(\displaystyle E(n,k) = \sum_{i=0}^k {(-1)}^{i}\binom{n+1}{i}{(k+1-i)}^n. \) | \(\displaystyle (1) \) |
Ebből a feladat állítása azonnal következik, mert létezik \(\displaystyle k\)-szor csökkenő permutáció: \(\displaystyle k=0\) esetén a \(\displaystyle (1,2,\ldots,n)\), \(\displaystyle k=n-1\) esetén az \(\displaystyle (n,n-1,\ldots,1)\), \(\displaystyle 0<k<n-1\) esetén az \(\displaystyle (k+1,k,\ldots,2,1,k+2,k+3,\ldots,n)\) permutáció ilyen, ezért \(\displaystyle E(n,k)>0\); másrészt nem az összes, \(\displaystyle n!\) permutáció ugyanannyiszor csökken, így \(\displaystyle E(n,k)<n!\).
Az (1) bizonyításához tetszőleges \(\displaystyle 0\le m<n\) egészre, az \(\displaystyle 1,2,\ldots,n\) számok egy-egy példányából és \(\displaystyle m\) darab \(\displaystyle *\) jelből készítsünk minden lehetséges módon \(\displaystyle n+m\) hosszú sorozatokat, amelyekben bármely két, közvetlenül egymás után következő szám közül a baloldali kisebb, mint a jobboldali. Az ilyen sorozatok halmazát jelöljük \(\displaystyle S_m\)-mel. Egy \(\displaystyle S_m\)-beli sorozatot úgy készíthetünk, hogy először elhelyezzük az \(\displaystyle m\) darab \(\displaystyle *\) jelet egy egyenesen (ezek az egyenest \(\displaystyle m+1\) intervallumra osztják), utána az \(\displaystyle 1,2,\ldots,n\) számok mindegyikéről eldöntjük, hogy melyik intervallumba kerüljön, végül minden egyes intervallumban nagyság szerint rendezzük a számokat. Az ilyen sorozatok száma tehát \(\displaystyle |S_m|=(m+1)^n\).
Most tekintsünk egy \(\displaystyle d\le m\)-szer csökkenő \(\displaystyle (a_1,\ldots,a_n)\) permutációt. A permutáció tagjait helyezzük el a számegyenesen (ezek az egyenest \(\displaystyle n+1\) intervallumra osztják), és minden olyan \(\displaystyle i\) indexnél, ahol \(\displaystyle a_i>a_{i+1}\), szúrjunk be a két szám közé egy \(\displaystyle *\) jelet, végül szúrjunk be további \(\displaystyle m-d\) darab "extra" \(\displaystyle *\) jelet tetszőlegesen. A \(\displaystyle *\) jelek egymás közötti sorrendje nem számít, és mindegyik extra \(\displaystyle *\) jelet az \(\displaystyle n+1\) intervallum bármelyikébe tehetjük, egy intervalumba többet is. Az extra \(\displaystyle *\) jelek elrendezései tehát az \(\displaystyle n+1\) intervallum \(\displaystyle (m-d)\)-adosztályú ismétléses kombinációi; az ilyenek száma \(\displaystyle \binom{n+m-d}{m-d}=\binom{n+m-d}{n}\). Ezért minden egyes, \(\displaystyle d\)-szer csökkenő permutációból \(\displaystyle \binom{n+m-d}{n}\) különböző \(\displaystyle S_m\)-beli sorozatot kaphatunk. A \(\displaystyle d\) szerint összegezve,
| \(\displaystyle \sum_{d=0}^m \binom{n+m-d}{n} E(n,d) = |S_m| = (m+1)^n. \) | \(\displaystyle (2) \) |
A (1) jobboldalát írjuk át úgy, hogy (2)-t az \(\displaystyle m=k-i\) választással alkalmazzuk, majd felcseréljük a szummákat:
\(\displaystyle \sum_{i=0}^k {(-1)}^{i}\binom{n+1}{i} {(k+1-i)}^n = \sum_{i=0}^k {(-1)}^{i}\binom{n+1}{i} \sum_{d=0}^{k-i} \binom{n+k-i-d}{n} E(n,d) = \)
\(\displaystyle = \sum_{d=0}^{k} E(n,d) \sum_{i=0}^{k-d} {(-1)}^{i}\binom{n+1}{i}\binom{n+k-i-d}{n} \)
A befejezéshez elég azt igazolnunk, hogy
\(\displaystyle \sum_{i=0}^{k-d} {(-1)}^{i}\binom{n+1}{i}\binom{n+k-i-d}{n} = \begin{cases} 1 & \text{ha } d=k; \\ 0 & \text{ha } 0\le d<k, \\ \end{cases} \)
avagy, a \(\displaystyle K=k-d\) helyettesítéssel,
\(\displaystyle \sum_{i=0}^K (-1)^i \binom{n+1}{i} \binom{n+K-i}{n} = \begin{cases} 1 & \text{ha } K=0; \\ 0 & \text{ha } 0<K\le k. \\ \end{cases} \)
Ez az azonosság leolvasható az \(\displaystyle (1-x)^{n+1}=\sum_{i=0}^{n+1}(-1)^i\binom{n+1}{i}x^i\) és \(\displaystyle \frac1{(1-x)^{n+1}}=\sum_{i=0}^\infty \binom{n+i}{i}x^i\) binomiális kifejtések szorzatából, de például \(\displaystyle n\)-szerinti indukcióval is könnyen igazolható.
Megjegyzések. 1. Az (1) képlet a B. 4793. feladat általánosítása.
2. Az \(\displaystyle E(n,k)\) számokat elsőfajú Euler-számoknak is nevezik, lásd pl. itt.
Statisztika:
7 dolgozat érkezett. 5 pontot kapott: Baran Zsuzsanna, Bodnár Levente, Polgár Márton, Williams Kada. 2 pontot kapott: 3 versenyző.
A KöMaL 2016. májusi matematika feladatai