Zauważmy, że

$$\binom{\binom{k}{2}}{2} = \binom{\frac{k(k-1)}{2}}{2} = \frac{1}{2}\frac{k(k-1)}{2}\frac{(k+1)(k-2)}{2} = \frac{4!}{8}\frac{(k+1)k(k-1)(k-2)}{4!} = 3 \binom{k+1}{4}$$.

Korzystając ze wzoru Pascala otrzymujemy

$$3\binom{k+1}{4} = 3\binom{k}{4} + 3\binom{k}{3}$$.

Zadanie więc sprowadza się do policzenia sumy

$$\sum_{k=0}^{n}\binom{\binom{k}{2}}{2} = 3\sum_{k=0}^{n}\binom{k}{4} + 3\sum_{k=0}^{n}\binom{k}{3}$$.

W ogólności zastanówmy się jak policzyć sumę \(\sum_{k=0}^{n}\binom{k}{l} \). Posłużmy się interpretacją kombinatoryczną. Wiadomo (z ćwiczeń), że \( \binom{n-1}{l-1} \) to liczba rozwiązań (w liczbach całkowitych dodatnich) równania \( x_1 + x_2 + ... + x_l = n \). Zatem szukana suma to liczba rozwiązań nierówności \( x_1 + x_2 + ... + x_{l + 1} \leq n+1\), gdzie \( k \), po którym sumujemy spełnia \( k + 1 = x_1 + x_2 + ... + x_{l + 1}\).

Zastanówmy się jak inaczej przedstawić liczbę rozwiązań (w liczbach całkowitych dodatnich) takiej nierówności. Weźmy sobie \( n+1 \) kulek. Ustawiamy kulki w rzędzie i każda po prawej ma jedno puste miejsce. Tych miejsc jest oczywiście tyle co kulek, czyli \( n+1 \). W te \( n+1 \) pustych miejsc wstawiamy \( l + 1 \) patyków. Ilość kulek na lewo od pierwszego patyka to \( x_1\), ilość kulek między pierwszym, a drugim patykiem to \( x_2 \) itd. aż do \(l+1\) patyka. Takie rozwiązanie spełnia nierówność. Zatem liczba rozwiązań tej nierówności to \(\sum_{k=0}^{n}\binom{k}{l} = \binom{n+1}{l+1} \).

Mając policzoną tę sumę możemy napisać ostateczne rozwiązanie

$$\sum_{k=0}^{n}\binom{\binom{k}{2}}{2} = 3\binom{n+1}{5} + 3\binom{n+1}{4}$$.

1. Prawa strona: Cykle \( n \) permutacji rozmieszczamy w \( k \) blokach. Takie rozmieszczenie możemy zakodować, zapisując każdy cykl począwszy od największego elementu i ustawiając cykle w każdym bloku w rosnącej kolejności początkowych elementów. W ten sposób otrzymujemy zbiór \( k \) niepustych list zawierających łącznie \( n \) elementów.

   Lewa strona: Tak samo jak w treści zadania, każdy podział można przedstawić jako zbiór \( k \) niepustych list zawierających łącznie \( n \) elementów.

   Stosując się do wyżej wymienionych zasad zapisu każdy taki zapis możemy zamienić na podział na bloki i cykle i na odwrót. Powielając przykład z treści zadania:

   • \( \{1, 23\} = [(1)],[(2)(3)] \)
   • \( \{1, 32\} = [(1)],[(32)] \)
   • \( \{2, 13\} = [(2)],[(1)(3)] \)
   • \( \{2, 31\} = [(2)],[(31)] \)
   • \( \{3, 12\} = [(3)],[(1)(2)] \)
   • \( \{3, 21\} = [(3)],[(21)] \)

2. Lewa strona: Robimy tak samo jak w podpunkcie a, tylko, że tym razem ustawiamy bloki w kolejności rosnącej początkowych elementów początkowych cyklów. W ten sposób otrzymujemy listę \( k \) niepustych list zawierających łącznie \( n \) elementów, posortowaną względem początkowych elementów tych list.

   Prawa strona: Permutujemy \( n \) elementów, wyróżniamy pierwszą pozycję oraz \( k - 1 \) spośród \( n - 1 \) pozostałych. Wyróżnione elementy odpowiadają początkom list. Następnie zaniedbujemy kolejność list ustawiając je w rosnącej kolejności początkowych elementów. Można to zrobić na \( {n-1\choose k-1}\frac{n!}{k!} \) sposobów.