Kezdőlap


Feladat:	F.2526	Korcsoport: 18-	Nehézségi fok: átlagos
Megoldó(k):	Bán Rita , Beke T. , Bóna M. , Boros Z. , Csizmadia Gy. , Deák Csaba , Dinnyés Enikő , Edvi T. , Fülöp T. , Grallert Ágnes , Heller Judit , Hetyei Judit , Íjjas Cs. , Kocsis 443 Katalin , Kós G. , Licsik I. , Ligeti Z. , Limbek Cs. , Majzik I. , Makay G. , Montágh B. , Olasz-Szabó M. , Pfeil T. , Pintér A. , Regős G. , Ribényi Á. , Sobor G.
Füzet:	1986/november, 361 - 362. oldal		PDF \| MathML
Témakör(ök):	Összefüggések binomiális együtthatókra, Kombinatorikai leszámolási problémák, Kombinációk, Variációk, Számsorozatok, Teljes indukció módszere, Feladat
Hivatkozás(ok):	Feladatok: 1985/április: F.2526

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.

I. megoldás. Próbáljunk jelentést tulajdonítani az egyenlőség két oldalán álló mennyiségeknek! Tekintsük ehhez az $n$ hosszúságú 0‐1 sorozatokat. Azoknak a sorozatoknak a száma, amelyek pontosan $j$ darab 1-est tartalmaznak, éppen $(\binom{n}{j})$ , az 1-esek helyét ugyanis ennyiféleképpen választhatjuk meg. Az egyenlőség bal oldalán eszerint azoknak az $n$ hosszúságú 0‐1 sorozatoknak a száma áll, amelyek pontosan $0, 1, 2, ..., k$ darab azaz legfeljebb $k$ darab 1-est tartalmaznak.
Vegyük most szemügyre a jobb oldalon álló összeg egy tagját. Az első tényező, $(\binom{n - 1 - j}{k - j})$ azoknak az $n - 1 - j$ hosszúságú 0‐1 sorozatoknak a száma, amelyek $k - j$ darab 1-est tartalmaznak. Ami a második tényezőt illeti, összesen $2^{j}$ darab $j$ hosszúságú 0‐1 sorozat van. A szorzat így azoknak az $n - 1$ hosszúságú 0‐1 sorozatoknak a száma, amelyekben az első $n - 1 - j$ helyen éppen $k - j$ darab 1-es fordul elő. Ha minden egyes ilyen sorozatban az $(n - j)$ -edik helyre egy 0-t illesztünk, akkor olyan, most már $n$ hosszúságú sorozatokat kapunk, amelyekben legfeljebb $k$ darab 1-es van, az első $n - 1 - j$ elem között pontosan $k - j$ , az utolsó $j$ elem között pedig legfeljebb $j$ . Az utólag beillesztett 0 pedig éppen az $(n - k)$ -adik 0 a sorozatban.
Csoportosítsuk tehát aszerint a legfeljebb $k$ darab 1-est ‐ és így legalább $n - k$ darab 0-t ‐ tartalmazó $n$ hosszúságú 0‐1 sorozatokat, hogy az $n - k$ -adik 0 hányadik helyen fordul elő a sorozatban. Ennek a 0-nak a pozíciója $(n - k)$ -tól $n$ -ig változhat, tekintsük azt az esetet, amikor ez épp az $(n - j)$ -edik elem $(0 \leq j \leq k)$ . Ekkor az ezt a 0-t megelőző $n - j - 1$ elem között $n - k - 1$ darab 0 és így $k - j$ darab 1-es van, az utolsó $j$ elem mindegyike lehet 0 vagy 1, az ilyen sorozatok száma tehát valóban $(\binom{n - 1 - j}{k - j}) \cdot 2^{j}$ . Így az összes olyan 0‐1 sorozatok száma, amelyek legfeljebb $k$ darab 1-est tartalmaznak, valóban

\begin{matrix} \sum_{j = 0}^{k} (\binom{n - 1 - j}{k - j}) \cdot 2^{j} \end{matrix}

II. megoldás. Az

n

-re vonatkozó teljes indukcióval bizonyítjuk az állítást. Ha

k = 0

, akkor a bizonyítandó egyenlőség minden

n

-re az 1=1 alakot ölti, ha pedig

k = n - 1

, akkor ugyancsak minden

n

-re a bal oldal

\begin{matrix} \sum_{j = 0}^{n - 1} (\binom{n}{j}) = 2^{n} - 1, \end{matrix}

a jobb oldal pedig

\begin{matrix} \sum_{j = 0}^{n - 1} (\binom{n - 1 - j}{n - 1 - j}) \cdot 2^{j} = \sum_{j = 0}^{}^{n - 1} 2^{j} = 2^{n} - 1, \end{matrix}

az állítás tehát minden

n

-re igaz, ha

k = 0

vagy

k = n - 1

. Innen következik, hogy

n = 1

és

n = 2

esetekben fennáll (1).
Tegyük most fel, hogy

1 \leq k \leq n - 1

és az állítás

n - 1

-re igaz. Ekkor az

(n - 1, k)

és az

(n - 1, k - 1)

párokra értelmes és igaz az (1) egyenlőség, azaz

\begin{matrix} \sum_{j = 0}^{k} (\binom{n - 1}{j}) = \sum_{j = 0}^{k} (\binom{n - 2 - j}{k - j}) \cdot 2^{j}, és & (2) \\ \sum_{j = 0}^{k - 1} (\binom{n - 1}{j}) = \sum_{j = 0}^{k - 1} (\binom{n - 2 - j}{k - j - 1}) \cdot 2^{j} . & (3) \end{matrix}

A (3) összefüggés bal oldala

\sum_{j = 1}^{k} (\binom{n - 1}{j - 1})

alakban is írható. Ha összeadjuk a két egyenlőséget, és felhasználjuk az

(\binom{m}{0}) = 1

, illetve az

(\binom{m}{r}) + (\binom{m}{r - 1}) = (\binom{m + 1}{r})

összefüggéseket, akkor éppen a bizonyítandó állítást kapjuk.

Megjegyzés. A legtöbb megoldás

k

-ra vonatkozó teljes indukciót használt. Volt, aki észrevette, hogy az

f (n, k) + f (n, k + 1) = f (n + 1, k + 1)

összefüggés fennáll az (1) két oldalán szereplő mennyiségekre és így a kezdeti értékek egyenlőségéből következik az állítás.