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

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,

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