Kezdőlap


Feladat:	F.1822	Korcsoport: 16-17	Nehézségi fok: átlagos
Megoldó(k):	Meszéna Géza
Füzet:	1972/december, 210 - 211. oldal		PDF \| MathML
Témakör(ök):	Összefüggések binomiális együtthatókra, Kombinációk, Feladat
Hivatkozás(ok):	Feladatok: 1972/április: F.1822

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 bizonyítandó egyenlőség jobb oldalán $2 n$ (különböző) elem $(n + k)$ -adosztályú (ismétlés nélküli) kombinációjának a száma áll. Megmutatjuk, hogy a bal oldali összeg ugyanezt adja, a kombinációknak egy bizonyos szempont szerint osztályokba rendezése után ‐ amikor minden kombinációt egy és csak egy osztályba sorolunk be ‐, mert az összeg tagjai éppen az egyes osztályokba sorolt kombinációk számai.
Gondoljuk, hogy elemeink egy iskola két párhuzamos osztályának, $A$ -nak és $B$ -nek tanulói, mindkét osztályban $n$ tanuló van, és köztük $(n + k)$ jegyet kívánunk kiosztani valamilyen rendezvényre. A kiosztási lehetőségek száma ‐ az $A$ -ba vagy $B$ -be tartozást nem tekintve ‐ éppen (1) jobb oldala.
Azokban a kombinációkban (kiosztásokban), amelyekben az $A$ osztály minden tanulója kap jegyet, a $B$ -sek közül csak $(n + k) - n = k$ kap. Az ilyenek száma ‐ mindjárt átalakítva célunk szerint :

\begin{matrix} (\binom{n}{k}) = 1 \cdot (\binom{n}{k}) = (\binom{n}{0}) \cdot (\binom{n}{k}), \end{matrix}

(2)

Ha az

A

-ból 1 tanulót ‐ majd általában

i

számú tanulót ‐ törlünk, akkor

B

-ből, 1-gyel ‐ illetve

i

-vel ‐ többen kapnak jegyet, és a kiosztási lehetőségek száma :

\begin{matrix} (\binom{n}{1}) \cdot (\binom{n}{k + 1}), \\ (\binom{n}{i}) \cdot (\binom{n}{k + i}), (i = 1, 2, ...) & (3) \end{matrix}

mert az első tényező az

A

-beli törlési, a második a

B

-beli kiválasztási lehetőségek száma. A (3) kifejezésben felismerjük (1) bal oldalának általános tagját.

i

-t csak addig van értelme növelnünk, míg a

B

-ben már mind az

n

tanuló kap jegyet, vagyis míg az

A

-ban már csak

k

tanuló kap, azaz míg itt

n - k

tanulót töröltünk. Éppen ez az (1) bal oldalán

i

legnagyobb figyelembe veendő értéke, tehát (2) és (3) alatt felsoroltuk egyrészt (1) bal oldalának összes tagját, másrészt az

(n + k)

jegy kiosztásának minden lehetőségét egyszer és csak egyszer. E két szám egyenlőségét akartuk bizonyítani.

Meszéna Géza (Budapest, Berzsenyi D. Gimn., II. o. t.)

Megjegyzések. 1. Írhatnánk a bal oldali összegezésben

n - k

helyett bármely nagyobb egész számot is, mert az így hozzágondolt tagok ‐ szorzatok ‐ egyik tényezője úgyis 0 lenne.
2. Általában az is igaz, hogy

\begin{matrix} (\binom{M}{N}) = \sum_{i = 0}^{m} (\binom{m}{i}) (\binom{M - n}{N - i}) . \end{matrix}

ahol

m

M

N

természetes számok, és

M

nagyobb

N

-nél és

m

-nél.