A C. 1892. feladat (2026. február)

C. 1892. Bizonyítsuk be, hogy

\(\displaystyle \binom{\binom{n}{2}}{3}=15\binom{n}{6}+30\binom{n}{5}+16\binom{n}{4}+\binom{n}{3} \)

teljesül minden pozitív egész \(\displaystyle n\) számra.

Javasolta: Paulovics Zoltán (Budapest)

(5 pont)

A beküldési határidő 2026. március 10-én LEJÁRT.

Megoldás. Az \(\displaystyle n\) csúcsú teljes gráf éleiből szeretnénk kiválasztani hármat. Ezt számoljuk meg kétféleképpen.

Egyrészt \(\displaystyle \binom{\binom{n}{2}}{3}\) éppen azt számolja meg, hogy az \(\displaystyle \binom{n}{2}\) darab élből hányféleképpen választhatunk ki három különbözőt. Ez tehát a bal oldal.

A jobb oldalon esetszétválasztást alkalmazunk aszerint, hogy a kiválasztott élek összesen hány csúcsát fogják le a gráfnak. (Figyeljünk, hogy különbözőek a csúcsok, így két eset hiába izomorf, még különbözőnek számít.)

Ha összesen 6 csúcsot fognak le, akkor először \(\displaystyle \binom{n}{6}\)-féleképpen kiválasztjuk ezt a 6 különböző csúcsot. Azt kell megszámolnunk, hogy hányféleképpen tudjuk ezeket párokba rendezni (úgy, hogy a párok sorrendje nem számít). Ez – az eddigi választásainktól függetlenül – \(\displaystyle \dfrac{\binom{6}{2} \cdot \binom{4}{2} \cdot \binom{2}{2}}{3!} = 15\) esetet ad, így tehát ekkor \(\displaystyle 15\binom{n}{6}\) esetet találtunk.

Ha összesen 5 csúcsot fognak le, akkor először \(\displaystyle \binom{n}{5}\)-féleképpen kiválasztjuk ezt az 5 különböző csúcsot. Ekkor pontosan egy csúcsra két él illeszkedik. \(\displaystyle 5\)-féleképpen eldöntjük, hogy melyikre, majd \(\displaystyle \binom{4}{2}\)-féleképpen kiválasztjuk a két szomszédját. Így ekkor \(\displaystyle 5 \cdot \binom{4}{2} = 30\) miatt, \(\displaystyle 30\binom{n}{5}\) esetet találtunk.

Ha összesen 4 csúcsot fognak le, akkor először \(\displaystyle \binom{n}{4}\)-féleképpen kiválasztjuk ezt az 4 különböző csúcsot. 4 esetben van harmadfokú csúcs, különben a részgráf egy \(\displaystyle 3\)-hosszú út. Ezekből éppen \(\displaystyle \dfrac{4 \cdot 3 \cdot 2}{2}=12\) darab van. Így összesen \(\displaystyle 16\binom{n}{4}\) esetet találtunk.

Ha összesen 3 csúcsot fog le a 3 él, akkor az pont egy háromszög. És \(\displaystyle \binom{n}{3}\) darab háromszög található a gráfban.

Mivel más eset nincs, így ezek összegzéseképpen – mint második megoldás – adódik a jobb oldal, és ezzel az állítás bizonyítása.

Statisztika:

A C. 1892. feladat értékelése még nem fejeződött be.

A KöMaL 2026. februári matematika feladatai