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.
Pokazać kombinatorycznie, sumy
- Zordon
- Użytkownik
- Posty: 4977
- Rejestracja: 12 lut 2008, o 21:42
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 75 razy
- Pomógł: 910 razy
Pokazać kombinatorycznie, sumy
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)
\(\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)
-
- Użytkownik
- Posty: 1251
- Rejestracja: 30 sty 2007, o 20:22
- Płeć: Mężczyzna
- Lokalizacja: Koziegłówki/Wrocław
- Podziękował: 352 razy
- Pomógł: 33 razy
Pokazać kombinatorycznie, sumy
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(3) to przecież zwykły wzór dwumienny Newtona
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
- Użytkownik
- Posty: 1657
- Rejestracja: 6 paź 2008, o 16:47
- Płeć: Mężczyzna
- Lokalizacja: Katowice
- Podziękował: 7 razy
- Pomógł: 472 razy
Pokazać kombinatorycznie, sumy
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}}\)
\(\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}}\)