Matematyka.pl

Witam. Jak policzyć następującą sumę?

\(\displaystyle{ {n \choose 2} + {n-2 \choose 2} + {n-4 \choose 2} + ... + {2 \choose 2}}\)

Gdy "góra" zmienia się co 1, podaną sumę interpretuje się jako wybór 3 elementów, z których najmniejszym jest kolejno 1, 2, 3 ... itd., ale tutaj jakoś nic nie przychodzi mi do głowy.

Koniecznie chcesz kombinatorycznie, czy może być jakkolwiek?

Q.

Jakkolwiek.

Zauważmy najpierw, że \(\displaystyle{ n}\) musi być parzyste, żeby ten napis wielokropkowy miał sens. Oznaczmy tę sumę przez \(\displaystyle{ A_n}\), a sumę w której górny wskaźnik zmienia się po liczbach nieparzystych od \(\displaystyle{ 3}\) do \(\displaystyle{ n-1}\) przez \(\displaystyle{ B_n}\). Jak wiadomo: \(\displaystyle{ A_n+B_n= {n+1 \choose 3}}\).

Z drugiej strony, jeśli rozpiszemy każdy napis \(\displaystyle{ {k \choose 2} ={k-1 \choose 2}+{k-1 \choose 1}}\), to otrzymamy:
\(\displaystyle{ A_n=B_n+ {n-1 \choose 1} +{n-3 \choose 1} +\ldots + {1 \choose 1} =B_n+\frac{n^2}{4}}\)
(suma ciągu arytmetycznego)

Mamy więc dwie zależności na \(\displaystyle{ A_n, B_n}\), z których łatwo dostajemy wynik
\(\displaystyle{ A_n=\frac{{n+1 \choose 3}+\frac{n^2}{4}}{2}}\)

Q.

Dzięki!

No to jeszcze kombinatorycznie:

Ustawmy \(\displaystyle{ n+2}\) elementy w rzędzie i pogrupujmy je po 2 elementy, tzn. pierwszy i drugi od lewej stanowią grupę pierwszą, trzeci i czwarty - drugą itd.
Na ile sposobów możemy wybrać \(\displaystyle{ 3}\) elementy spośród wszystkich \(\displaystyle{ n+2}\) tak, żeby dwa z nich, leżące najbardziej z lewej strony nie należały do tej samej grupy? Osoba najbardziej z lewej będzie liderem tej grupy.

Z jednej strony będzie to \(\displaystyle{ {2 \choose 1} {n \choose 2}+{2 \choose 1} {n-2 \choose 2}+ \ldots + {2 \choose 1} {2 \choose 2}}\) - z każdej grupy wybieramy lidera, resztę dobieramy z osób z prawej strony.

Inaczej licząc wybieramy dowolny trzyosobowy podzbiór, ale odejmujemy te, w których dwa elementy najbardziej na lewo, należą do jednej grupy, tzn. jest ich \(\displaystyle{ { n+2 \choose 3} - \left( n + (n-2) + (n-4) + \ldots + 2 \right) = {n+2 \choose 3} - \frac{(n+2)}{2} \cdot \frac{n}{2}}\)

ostateczny wynik to \(\displaystyle{ \boxed{\frac{{n+2\choose 3} - \frac{n(n+2)}{4}}{2}}}\)