Pokazać kombinatorycznie, sumy

[patry93]

Witam.
Udowodnić kombinatorycznie, że zachodzą tożsamości:
\(\displaystyle{ (1) \ \sum_{k=2}^{n-1} (k-1)k(k+1) = 6 {n+1 \choose 4} \\ (2) \ \sum_{k=1}^{n} k^2 = 2 {n+1 \choose 3} + {n+1 \choose 2} \\ (3) \ \sum_{k=0}^{n} {n \choose k} (m-1)^{n-k} = m^n}\)

W (1) można lewą stronę oczywiście przekształcić do postaci
\(\displaystyle{ \sum_{k=1}^{n-1} k^3 - \sum_{k=1}^{n-1} k}\)
I wówczas sumę z sześcianami zinterpretować jako liczbę prostokątów, a drugą sumę jako liczbę odcinków łączących jakieś punkty, skąd dostaniemy \(\displaystyle{ {n \choose 2} ^2 - {n \choose 2}}\) i na siłę przekształcić do prawej strony, ale to tak alternatywnie, bo dowodem czysto kombinatorycznym tego raczej nie można nazwać, także pewnie można dużo prościej.
W (2) nasuwa mi się od razu wzór na sumę kwadratów, ale to też nie byłoby pokazanie kombinatoryczne. Natomiast lewą stronę można rozumieć jako liczbę kwadratów na szachownicy \(\displaystyle{ nxn}\), ale z prawą mam problem.
W (3) na prawą stronę potrafię patrzeć jedynie jak na liczbę n-wyrazowych wariacji z powtórzeniami ze zbioru m-elementowego, np. \(\displaystyle{ \{ 1,2, \ldots m \}}\), lecz chyba trzeba inaczej, ponieważ wtedy po lewej "\(\displaystyle{ m-1}\)" wymagałoby wyszczególnienia jednego z elementów (wyrzucenia?). Ułożyć tego nie potrafię...

Z góry dziękuję za pomoc.

[Dumel]

(3) to przecież zwykły wzór dwumienny Newtona. łatwo go uzasadnić kombinatorycznie po rozpisaniu nawiasów

[Zordon]

2) tak jak mówisz, ilość kwadratów na szachownicy, teraz popatrzmy na:
\(\displaystyle{ {n+1 \choose 3}}\) to ilość trójek uporządkowanych \(\displaystyle{ (a,x,y)}\) t.że \(\displaystyle{ a<x<y}\), czyli (bok, współrzędna prawego dolnego rogu przesunieta o (1,1)). Trzeba pomnożyć razy dwa, bo zawsze \(\displaystyle{ x<y}\). Drugi składnik sumy to to czego nie policzyliśmy (x=y)

[patry93]

(3) to przecież zwykły wzór dwumienny Newtona

Hahahahah! Nie ma to jak się naczytać o wariacjach, uogólnionych wzorach Newtona, a tu niespodzianka, najprostszy dwumian Świetna lekcja dla mnie, żeby nie we wszystkim widzieć tylko najbardziej skomplikowane obiekty

Zordon - troszeczkę trzeba poprawić chyba, bo np. bok nie może mieć długość 0, ale bez problemu \(\displaystyle{ a}\) może nam definiować dł. boku pomniejszonego o 1 i mnie jakoś naturalniej operuje się na dolnym lewym wierzchołku, ale to bez znaczenia

Na (1) nadal nie mam pomysłu niestety.

[timon92]

1. zliczamy wszystkie czteroelementowe podzbiory zbioru n+1 elementowego:

\(\displaystyle{ \frac{1}{6}n(n-1)(n-2)}\) - tyle jest podzbiorów zawierających jedynkę

\(\displaystyle{ \frac{1}{6}(n-1)(n-2)(n-3)}\) - tyle jest podzbiorów niezawierających jedynki, ale zawierających dwójkę

\(\displaystyle{ \frac{1}{6}(n-2)(n-3)(n-4)}\) - tyle jest podzbiorów niezawierających ani jedynki ani dwójki, ale zawierających trójkę

(za każdym razem dzielimy przez 6, bo sześciokrotnie zliczamy te same podzbiory)

postępując tak dalej dostaniemy lewą stronę podzieloną przez 6

z drugiej strony ta liczba jest równa oczywiście \(\displaystyle{ {n+1 \choose 4}}\)