Kezdőlap


Feladat:	F.2712	Korcsoport: 18-	Nehézségi fok: átlagos
Megoldó(k):	Antos András , Mezei József , Mohai Zsuzsanna , Révész Gabriella
Füzet:	1989/szeptember, 254 - 257. oldal		PDF \| MathML
Témakör(ök):	Algebrai átalakítások, Kombinatorikai leszámolási problémák, Összefüggések binomiális együtthatókra, Permutációk, Szitaformula, Teljes indukció módszere, Feladat
Hivatkozás(ok):	Feladatok: 1988/november: F.2712

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.

A két állítást (F. 2712. és F. 2717. feladat) együtt bizonyítjuk. Legyen

\begin{matrix} S_{n, k} = \sum_{i = 1}^{n} {(- 1)}^{i} (\binom{n}{i}) i^{k} . \end{matrix}

Belátjuk, hogy ha

n ≧ 2

, akkor

\begin{matrix} S_{n,0} = - 1, S_{n, k} = 0, ha 0 < k < n és S_{n, n} = {(- 1)}^{n} n! \end{matrix}

(1)

(Ebből

n = 100

helyettesítéssel következik mindkét feladat állítása.)

I. bizonyítás.

n

-re vonatkozó teljes indukciót alkalmazunk.

n = 2

-re:

\begin{matrix} S_{2,0} & = {(- 1)}^{1} (\binom{2}{1}) \cdot 1^{0} + {(- 1)}^{2} (\binom{2}{2}) \cdot 2^{0} = - 2 + 1 = - 1, \\ S_{2,1} & = {(- 1)}^{1} (\binom{2}{1}) \cdot 1 + {(- 1)}^{2} (\binom{2}{2}) \cdot 2 = - 2 + 2 = 0, \\ S_{2,2} & = {(- 1)}^{1} (\binom{2}{1}) \cdot 1^{2} + {(- 1)}^{2} (\binom{2}{2}) \cdot 2^{2} = - 2 + 4 = 2 = {(- 1)}^{2} \cdot 2! \end{matrix}

Legyen ezután

n ≧ 3

, és tegyük fel, hogy

n

helyett

n - 1

-et írva (1) igaz. A binomiális tétel alapján

\begin{matrix} S_{n,0} = \sum_{i = 0}^{n} {(- 1)}^{i} (\binom{n}{i}) \cdot i^{0} = \sum_{i = 1}^{n} {(- 1)}^{i} (\binom{n}{i}) 1^{n - i} = {(1 - 1)}^{n} - 1 = - 1. \end{matrix}

Legyen

k > 0

. Ha

1 ≦ i ≦ n

, akkor

(\binom{n}{i}) = \frac{n}{i} \cdot (\binom{n - 1}{i - 1})

, így

\begin{matrix} S_{n, k} = n \sum_{i = 1}^{n} {(- 1)}^{i} (\binom{n - 1}{i - 1}) \cdot i^{k - 1} = - n \sum_{j = 0}^{n - 1} {(- 1)}^{j} (\binom{n - 1}{j}) \cdot {(j + 1)}^{k - 1}, \end{matrix}

ahol

(i - 1)

helyett

j

-t írtunk. A

j = 0

értékhez tartozó tag a szummában

{(- 1)}^{0} (\binom{m - 1}{0}) 1^{k - 1} = 1

, ezt leválasztva

\begin{matrix} S_{n, k} = - n (1 + \sum_{j = 1}^{n - 1} {(- 1)}^{j} (\binom{n - 1}{j}) {(j + 1)}^{k - 1}) . \end{matrix}

Itt a szumma már erősen emlékeztet

S_{n - 1, k - 1}

-re, csak éppen

j^{k - 1}

helyett

{(j + 1)}^{k - 1}

áll. Ám ha ezt a binomiális tétel szerint kifejtjük,

S_{n - 1, t}

alakú tagok összegéhez jutunk:

\begin{matrix} S_{n, k} = - n (1 + \sum_{j = 1}^{n - 1} {(- 1)}^{j} (\binom{n - 1}{j}) (j^{k - 1} + (\binom{k - 1}{1}) j^{k - 2} + \\ + (\binom{k - 1}{2}) j^{k - 3} + ... + (\binom{k - 1}{t}) j^{k - t - 1} + ... + (\binom{k - 1}{k - 1}) j^{0}) = \\ = - n (1 + \sum_{j = 1}^{n} {(- 1)}^{j} (\binom{n - 1}{j}) j^{k - 1} + (\binom{k - 1}{1}) \sum_{j = 1}^{n - 1} {(- 1)}^{j} (\binom{n - 1}{j}) j^{k - 2} + ... + \\ + (\binom{k - 1}{t}) \sum_{j = 1}^{n - 1} {(- 1)}^{j} (\binom{n - 1}{j}) j^{k - t - 1} + ...) = \\ = - n (1 + S_{n - 1, k - 1} + (\binom{k - 1}{1}) S_{n - 1, k - 2} + (\binom{k - 1}{2}) S_{n - 1, k - 3} + ... + \\ + (\binom{k - 1}{t}) S_{n - 1, k - 1 - t} + ... + S_{n - 1,0}) . \end{matrix}

k < n

, akkor

k - 1 < n - 1, k - 2 < n - 1

stb., így a zárójelben az indukciós feltevés szerint az utolsó kivételével mindegyik

S

nulla, az utolsó

- 1

, tehát a zárójeles összeg értéke nulla. Ezért

S_{n, k} = 0

, ha

1 ≦ k < n

.
Ha

k = n

, akkor csak annyi a különbség, hogy az első

S

értéke indukciós feltevésünk értelmében

{(- 1)}^{n - 1} (n - 1)!

, a többi tag az utolsó kivételével most is nulla, az utolsó

- 1

, így a zárójeles összeg értéke ezúttal

{(- 1)}^{n - 1} (n - 1)!

, ezért

S_{n, n} = - n {(- 1)}^{n - 1} (n - 1)! = {(- 1)}^{n} n!

, amit bizonyítani akartunk.

Révész Gabriella (Komárom, Jókai M. Gimn., IV. o. t.)
dolgozata nyomán

II. bizonyítás. Csak

k ≧ 1

-re bizonyítjuk (1)-et. Tekintsük azt a feladatot, hogy hányféleképpen osztható el

k

db kártya

n

darab borítékba úgy, hogy mindegyik borítékba kerüljön kártya (a borítékok és kártyák megkülönböztethetők).

k

db kártyát

n

borítékba

n^{k}

-féleképpen oszthatunk el, de ebből le kell vonnunk azokat az eseteket, amikor legfeljebb

n - 1

borítékba került csak kártya. Az

n - 1

borítékot

(\binom{n}{n - 1})

-féleképpen választhatjuk ki, s minden választásnál

{(n - 1)}^{k}

-féleképpen oszthatók el a kártyák, összesen tehát

(\binom{n}{n - 1}) {(n - 1)}^{k}

esetet kell levonnunk. Most azonban többször vontuk le azokat az eseteket, amelyekben (legföljebb)

n - 2

borítékba került kártya, így az előzőhöz hasonló megfontolásból hozzá kell adnunk

(\binom{n}{n - 2}) {(n - 2)}^{k}

esetet. A logikai szita-formula szerint ezt az eljárást folytatva megkapjuk a jó esetek számát, ami

\begin{matrix} n^{k} - (\binom{n}{n - 1}) {(n - 1)}^{k} + (\binom{n}{n - 2}) {(n - 2)}^{k} - (\binom{n}{n - 3}) {(n - 3)}^{k} + ... + \\ + {(- 1)}^{t} (\binom{n}{n - t}) {(k - t)}^{k} + ... + {(- 1)}^{n} (\binom{n}{n}) 0^{k} . \end{matrix}

k ≧ 1

, így

0^{k} = 0

, tehát a keresett szám (

i = n - t

helyettesítéssel)

\begin{matrix} \sum_{i = 1}^{n} {(- 1)}^{n - i} (\binom{n}{i}) i^{k} = {(- 1)}^{n} \sum_{i = 1}^{n} {(- 1)}^{i} (\binom{n}{i}) i^{k} = (- 1) S_{n, k} . \end{matrix}

k < n

, akkor

k

kártyát akárhogyan teszünk is

n

borítékba, marad üres boríték; a fenti szám tehát nulla, s így

S_{n, k} = 0

.
Ha

k = n

akkor a jó esetek száma az

n

elemű permutációk száma,

n!

, tehát

{(- 1)}^{n} S_{n, n} = n!

, ahonnan

S_{n, n} = {(- 1)}^{n} n!

, amit bizonyítani kellett.

Mohai Zsuzsanna (Dombóvár, Gőgös I. Gimn., IV. o. t)
dolgozata nyomán

Megjegyzések. 1. A logikai szita-formula és annak bizonyítása megtalálható Hajós Gy.

-

Neukomm Gy.

-

Surányi J.: Matematikai versenytételek I. rész 124

-

125. oldalán. Ugyanitt olvasható annak a bizonyítása is, hogy

S_{n, n} = {(- 1)}^{n} n!

, és a bizonyításból könnyen megkapható a többi (1) alatti állítás is.

2. Mindkét megoldás módszerével igazolhatjuk, hogy

S_{n, n + 1} = {(- 1)}^{n} (n + 1)! \frac{n}{2}

, azaz

(n + 1)! \frac{n}{2}

-féleképpen osztható el

n + 1

kártya pontosan

n

borítékba.

3. Olvasóink bizonyára észrevették, hogy a 2712. feladat az októberi számunkban kitűzött 2704. feladatnak az általánosítása.