Problem B. 4091. (April 2008)

B. 4091. Prove that

$\sum_{k=0}^m \binom mk \binom{t+k}{m} =\sum_{k=0}^m\binom mk\binom tk\cdot2^k$

for arbitrary positive integers m, t.

(5 pont)

Deadline expired on May 15, 2008.

Sorry, the solution is available only in Hungarian. Google translation

Megoldás: A jobboldali kifejezést könnyebb értelmezni, kezdjük ezzel. Legyen M és T két diszjunkt halmaz úgy, hogy |M|=m és |T|=t. Számoljuk meg, hányféleképpen lehet kiválasztani A,B,C halmazokat úgy, hogy $C\subseteq A\subseteq M$ , $B\subseteq T$ és |A|=|B|. Ekkor nyilván |A| $\le$ m, tehát alkalmas 0 $\le$ k $\le$ m számmal |A|=|B|=k, ezen feltétel mellett A és B megválasztására egymástól függetlenül ${m\choose k}$ , illetve ${t\choose k}$ lehetőségünk van, ha pedig A-t és B-t már megválasztottuk, akkor A-n belül C kiválasztására 2^k lehetőség van. Ezért a jobboldalon álló összeg a fenti tulajdonságokkal rendelkező (A,B,C) hármasokat számolja össze.

Ugyanezt most számoljuk össze másképpen. Kezdjük C kiválasztásával: ha C elemszáma m-k (ahol 0 $\le$ k $\le$ m), akkor erre éppen ${m\choose k}$ különböző lehetőségünk van. Ehhez megfelelő A és B halmazt úgy kapunk, hogy T-ből alkalmas q-val kiválasztunk egy q elemű B részhalmazt, a k elemű M\C halmazból pedig egy m-q elemű részhalmazt választunk ki, amit az M\A halmaznak fogunk fel. Vagyis arról van szó, hogy ha C-t már kiválasztottuk a |C|=m-k feltétel mellett, akkor kölcsönösen egyértelmű megfeleltetést létesíthetünk az adott C-hez tartozó (A,B,C) hármasok és a t+k elemű (M\C) $\cup$ T halmaz m elemű részhalmazai között. Ez a megfeleltetés mutatja, hogy a baloldalon álló összeg is ugyanazokat az (A,B,C) hármasokat számolja össze.

Statistics:

30 students sent a solution.

5 points: Bálint Dániel, Bencs 111 Ferenc, Blázsik Zoltán, Bodor Bertalan, Dudás 002 Zsolt, Éles András, Fonyó Dávid, Gévay Gábor, Kiss 243 Réka, Kovács 729 Gergely, Lovas Lia Izabella, Márkus Bence, Muszka Balázs, Nagy 648 Donát, Perjési Gábor, Réti Dávid, Somogyi Ákos, Szalkai Balázs, Tossenberger Anna, Tóth 369 László Márton, Varga 171 László, Véges Márton, Vincze Ákos, Zelena Réka, Zieger Milán.

1 point: 1 student.

0 point: 4 students.

Problems in Mathematics of KöMaL, April 2008

30 students sent a solution.
5 points:	Bálint Dániel, Bencs 111 Ferenc, Blázsik Zoltán, Bodor Bertalan, Dudás 002 Zsolt, Éles András, Fonyó Dávid, Gévay Gábor, Kiss 243 Réka, Kovács 729 Gergely, Lovas Lia Izabella, Márkus Bence, Muszka Balázs, Nagy 648 Donát, Perjési Gábor, Réti Dávid, Somogyi Ákos, Szalkai Balázs, Tossenberger Anna, Tóth 369 László Márton, Varga 171 László, Véges Márton, Vincze Ákos, Zelena Réka, Zieger Milán.
1 point:	1 student.
0 point:	4 students.

Already signed up?
New to KöMaL?