Problem C. 1892. (February 2026)

C. 1892. Prove that \(\displaystyle \binom{\binom{n}{2}}{3}=15\binom{n}{6}+30\binom{n}{5}+16\binom{n}{4}+\binom{n}{3}\) is true for every positive integer \(\displaystyle n\).

Proposed by Zoltán Paulovics, Budapest

(5 pont)

Deadline expired on March 10, 2026.

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

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.

Statistics:

33 students sent a solution.
5 points:	Aaishipragya Kahaly, Albert Luca Liliána, Bao Nguyen Gia, Farkas Noémi , Hirmann Dorottya, Kátai Zalán, Márfai Lili, Markovics Dóra, Máté Kristóf, Mateas Isabelle, Németh Ábel, Szathmáry Zalán, Szekeres Anina, Válek Péter	(14 students).
4 points:	Áron Bence, Budai Máté, Halász Jonatán, Hetyei Dániel, Kun Petra, Móricz Zsombor, Ónody Ágnes, Papp Emese Petra, Schneider Péter, Szabados Zoltán , Viczián Adél	(11 students).
3 points:	4 students.
2 points:	1 student.
1 point:	1 student.

Problems in Mathematics of KöMaL, February 2026