msleziak.com

Ukážte, že pre $n\in\mathbb N_0$ platí $$\binom{\binom n2}2=3\binom n4+3\binom n3.$$

Kombinatoricky. Číslo $\binom{\binom n2}2$ vyjadruje to, koľkými spôsobmi môžeme vybrať 2-prvkovú podmnožinu z množiny všetkých dvojprvkových podmnožín.
Máme teda k dispozícii všetky 2-prvkové podmnožiny a spomedzi nich chceme vybrať dva rôzne prvky.
Sú dve možnosti:
A. Vybraté množiny sú disjunktné.
B. Prienik vybratých množín je jeden prvok.

V prvom prípade tieto dve množiny obsahujú štyri prvky. Označme si ich $a$, $b$, $c$, $d$. Pre výber štyroch prvkov máme práve $\binom n4$ možností. Z~nich môžeme dve dvojice množín vytvoriť práve troma spôsobmi:
* $\{\{a,b\}, \{c,d\}\}$
* $\{\{a,c\}, \{b,d\}\}$
* $\{\{a,d\}, \{b,c\}\}$

V druhom prípade máme tri prvky, označme ich $a$, $b$, $c$. Máme $\binom n3$ možností, ako vybrať tieto prvky. A z nich môžeme troma spôsobmi poskladať dve 2-prvkové podmnožiny:
* $\{a,b\},\{a,c\}$
* $\{a,b\},\{b,c\}$
* $\{a,c\},\{b,c\}$

Pre istotu ešte zdôrazním aj to, že $\binom{\binom n2}2$ ráta počet množín, a teda nezáleží na poradí. Napríklad výber $\{a,b\}$ a $\{c,d\}$ je to isté ako výber $\{c,d\}$ a $\{a,b\}$.

Výpočtom.
Môžeme jednoducho zobrať vyjadrenie pre ľavú resp. pre pravú stranu a snažiť sa ich upraviť. Ak si všimneme, že oba sčítance na pravej strane obsahujú súčin $n(n-1)(n-2)$, tak vyzerá pomerne rozumne snažiť sa využiť takéto výrazy aj na ľavej strane, ak sa niekde objavia.

\begin{align*}
\binom{\binom n2}2
&=\frac{\binom n2\left(\binom n2-1\right)}2\\
&=\frac{\frac{n(n-1)}2\cdot\frac{n^2-n-2}2}2\\
&=\frac{n(n-1)(n-2)(n+1)}8
\end{align*}

\begin{align*}
3\binom n4+3\binom n3
&=3\frac{n(n-1)(n-2)(n-3)}{4\cdot3\cdot2}+3\frac{n(n-1)(n-2)}{3\cdot2}\\
&=\frac{n(n-1)(n-2)(n-3)}{4\cdot2}+\frac{n(n-1)(n-2)}{2}\\
&=\frac{n(n-1)(n-2)[(n-3)+4]}8\\
&=\frac{n(n-1)(n-2)(n+1)}8
\end{align*}

Výraz na pravej strane by sme asi o trochu rýchlejšie upravili pomocou Pascalovej identity:
\begin{align*}
3\binom n4+3\binom n3
&=3\binom{n+1}4\\
&=3\cdot\frac{(n+1)n(n-1)(n-2)}{4\cdot3\cdot2}\\
&=\frac{(n+1)n(n-1)(n-2)}8
\end{align*}

Linky.
Napríklad Prove the following identity combinatorially a Combinatorial Proof for Composite/Nested Binomial Coefficient.