Kezdőlap


Feladat:	F.1800	Korcsoport: 16-17	Nehézségi fok: nehéz
Megoldó(k):	Bálint László , Balogh Zoltán , Bara Tamás , Császár Gyula , Deák Péter , Füredi Zoltán , Gál Péter , Gáspár Gyula , Gergely István , Kémeri Viktória , Kovács István , Lakner Péter , Oláh Vera , Pálffy László , Pallagi Dezső , Ribli Ágnes , Sebő András , Smohay Ferenc , Stachó Balázs , Szalai-Dobos István , Szigeti Gábor , Tóth Károly , Turán György , Turi Erzsébet , Varga Mária , Wettl Ferenc
Füzet:	1972/november, 137 - 139. oldal		PDF \| MathML
Témakör(ök):	Azonosságok, Összefüggések binomiális együtthatókra, Kombinációk, Feladat
Hivatkozás(ok):	Feladatok: 1971/december: F.1800

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.

Azt fogjuk megmutatni, hogy (1)-nek mindkét oldalán $k$ -tól függetlenül $(n + 1)$ különböző elem $(m + 1)$ -edosztályú (ismétlés nélküli) kombinációinak $(\binom{n + 1}{m + 1})$ száma áll. Pontosabban azt, hogy ha e kombinációk halmazát két megadandó, különböző szempont szerint osztályozzuk közös kombinációt nem tartalmazó részhalmazokba, akkor a két összeg tagjai rendre az egy‐egy részhalmazba jutott kombinációk számai és az összegezés mindkét oldalon sorra veszi az illető szempont szerinti összes részhalmazt.
Elemekként az első $(n + 1)$ természetes számra gondolunk, ezzel mindjárt könnyen sorszámokat is rendelhetünk hozzájuk, legegyszerűbben úgy, hogy mindegyik számunk sorszáma önmaga legyen.
a) Először (1) jobb oldalára bizonyítjuk állításunkat. Minden egyes tag két tényezője maga is bizonyos kombinációk száma, és észrevesszük, hogy bennük a ,,felső'' számok ‐ azaz a választható számok számai ‐ összegül $(n + 1)$ -et adnak, az ,,alsó'' számok pedig ‐ vagyis a kiválasztott számok számai ‐ összegül $(m + 1)$ -et. Továbbá az $i$ összegezési betűtől csak az alsó számok függnek. Ezt használjuk fel az osztályozásban: az első $(n + 1)$ szám $(m + 1)$ elemű kombinációit aszerint rendezzük részhalmazokba, hogy hányat tartalmaznak az első $k$ szám közül. Ugyanis az ilyen számok számát jelölve $i$ -vel, egyrészt erre $(\binom{k}{i})$ különböző lehetőségünk van, másrészt ekkora hátralevő ${(m + 1) - i}$ számot csak a $k$ -nál nagyobb számok közül választhatjuk, az ilyenek száma, ${(n + 1) - k}$ ‐ ami mindenesetre $≧ 1$ ‐, a kiválasztási lehetőségek száma $(\binom{n + 1 - k}{m + 1 - i})$ ezek szerint pedig a jobb oldal általános tagja azt adja meg, hogy az $i$ indexű részhalmaz hány összekapcsolást tartalmaz, ha az $i$ elemű kiválasztások mindegyikét összekapcsoljuk az $(m + 1 - i)$ elemű kiválasztások mindegyikével egy‐egy $(m + 1)$ elemű kombinációvá. $i$ értéke minden kombinációra egyértelműen meghatározza, hogy azt melyik részhalmazban vesszük számba, tehát amíg $i$ végigfut az előírt 0, 1, $...$ , $m + 1$ értékeken, addig minden egyes kombinációnkat számba vesszük egy és csak egy részhalmazban. ‐ Ezzel állításunkat a jobb oldalra bebizonyítottuk.
Megjegyezzük még: előfordul, hogy az összeg egy vagy több tagja 0-val egyenlő, ilyen mindjárt $i = m + 1$ , amikor is $i > k$ , és ezért $(\binom{k}{i}) = 0$ ; szóban: az első $k$ számból $k < m + 1$ miatt nem lehet képezni $(m + 1)$ elemű kombinációt (ismétlés nélkül). Ha viszont $i$ ,,kicsi'', akkor előfordulhat, hogy $m + 1 - i > n + 1 - k$ , ekkor a második tényező 0, pl. $i = 0$ és $m + 1 > n + 1 - k$ mellett nem lehet $(m + 1)$ elemű kombinációt képezni anélkül, hogy legalább egyet ne használjunk fel az első $k$ szám közül. Az $i$ -nek ilyen ,,meddő'' értékei természetesen nem érintik a bizonyított állítás érvényességét.

b) Az (1) bal oldala tagjainak két‐két tényezője ugyancsak kombinációk száma, bennük a felső számok összege

n

, az alsóké

m

, és az

i

összegezési betűtől itt csak a felső számok függnek, vagyis a választható számok számai. Az, hogy a talált

n

is,

m

is 1‐1 hiányt mutat a jobb oldali megfelelő

(n + 1)

, illetőleg

(m + 1)

együttes elemszámmal szemben, azt az ötletet adja, hogy itt tagról tagra egy‐egy szám elő van írva a kombinációba, ezért lehet együttvéve csak

n

szám közül választani és együttvéve csak

m

számot választani. A részhalmazokba osztályozáshoz ismét használható az

i

szám: az

(\binom{i}{k}) (\binom{n - i}{m - k})

szorzat a fentihez hasonló meggondolással az olyan

(m + 1)

elemű kombinációk száma az első

(n + 1)

természetes szám közül, amelyekben a

(k + 1)

-edik helyen az

i + 1

szám áll; ugyanis az ilyenekben az első

k

helyre csak az első

i

szám közül választhatunk, a további helyekre pedig ‐ más szóval a kombináció ,,végén'' álló

(m + 1) - (k + 1) = m - k

számú helyre ‐ csak az

(i + 1)

-nél nagyobb számok közül, amelyeknek száma

(n + 1) - (i - 1) = n - i

. (Ezzel biztosítjuk a három részből összekapcsolt egymásutánban a növekvő sorrendet.)
A föltevés szerint

k ≦ 1

alapján az

(m + 1)

elemű kombinációkban van

(k + 1)

sorszámú elem; továbbá minden kombinációról a

(k + 1)

-edik eleme egyértelműen eldönti, hogy melyik részhalmazban vesszük számba a kombinációt. ‐ Ezzel a bevezetőül kimondott állításunkat a bal oldalra is bebizonyítottuk, s evvel a feladatot megoldottuk.
Az összegezés a bal oldalon is tartalmaz 0 értékű tagokat, éspedig egyrészt az

i ≦ k - 1

értékekre, másrészt azokra, amelyekre

n - (m - k) < i ≦ n

, ilyenek akkor vannak (legalább 1), ha

k < m

Balogh Zoltán (Debrecen, Fazekas M. Gimn., IV. o. t.)

Megjegyzés. Az (1) jobb oldalán álló összeg értelmezésében nélkülözhetjük azt a nagysági, sorrendi rendezést, ami természetes számok közt eleve fennáll. Beszélhetünk ehelyett pl.

(n + 1)

különböző tárgyról, amelyek közül

k

darab piros színű, a többi kék, hiszen a választás minden tagban a pirosak, ill kékek közül történik. A bal oldali összeg értelmezése esetében viszont minden tagban másik‐másik az a szám, amely az adottakat kettéosztja a kombináció elülső és hátsó részkomponensében választható számok céljára.