Mam problem z takim zdaniem, prosiłbym o jego rozwiązanie:
Na ile sposobów można wybrać trzy rozdziały spośród \(\displaystyle{ n}\) Rozwiąż to zadanie na dwa sposoby tak,aby wywnioskować tożsamość:
\(\displaystyle{ {n \choose 3} = {{n-1} \choose 2}+ {{n-2} \choose 2} + {{n-3} \choose 2}+...+ {2 \choose 2}}\)
Na ile sposobów można wybrać trzy rozdziały
- max
- Użytkownik
- Posty: 3306
- Rejestracja: 10 gru 2005, o 17:48
- Płeć: Mężczyzna
- Lokalizacja: Lebendigentanz
- Podziękował: 37 razy
- Pomógł: 778 razy
Na ile sposobów można wybrać trzy rozdziały
Najpierw zajmę się prawą stroną, bo jest ciekawsza
Ponumerujmy nasze rozdziały liczbami naturalnymi od 1 do n. Zliczamy możliwe do wylosowania trójki:
krok 1. -najpierw zliczamy wszystkie możliwe trójki zawierające pierwszy z rozdziałów. Jest ich \(\displaystyle{ {n - 1 \choose 2}}\)
krok 2. -dalej bierzemy pod uwagę wszystkie te zawierające drugi rozdział i nie zawierające pierwszego. Będzie ich \(\displaystyle{ {n - 2 \choose 2}}\)
krok 3. -dalej te które zawierają trzeci rozdział i nie zawierające dwóch pierwszych (wszak te już były podliczone wcześniej) - uzyskujemy następny wyraz sumy po prawej
...
krok (n - 2). -pozostaje tylko \(\displaystyle{ {2 \choose 2}}\) nie policzonych we wcześniejszych krokach trójek, zawierających element (n - 2), gdyż zliczyliśmy już wszystkie trójki zawierające n - 3 pierwsze elementy.
Teraz lewa strona: wybrane trzy rozdziały stanowią 3-elementową kombinację bez powtórzeń zbioru n-elementowego, a takich kombinacji jest właśnie \(\displaystyle{ {n \choose 3}}\)
Ponumerujmy nasze rozdziały liczbami naturalnymi od 1 do n. Zliczamy możliwe do wylosowania trójki:
krok 1. -najpierw zliczamy wszystkie możliwe trójki zawierające pierwszy z rozdziałów. Jest ich \(\displaystyle{ {n - 1 \choose 2}}\)
krok 2. -dalej bierzemy pod uwagę wszystkie te zawierające drugi rozdział i nie zawierające pierwszego. Będzie ich \(\displaystyle{ {n - 2 \choose 2}}\)
krok 3. -dalej te które zawierają trzeci rozdział i nie zawierające dwóch pierwszych (wszak te już były podliczone wcześniej) - uzyskujemy następny wyraz sumy po prawej
...
krok (n - 2). -pozostaje tylko \(\displaystyle{ {2 \choose 2}}\) nie policzonych we wcześniejszych krokach trójek, zawierających element (n - 2), gdyż zliczyliśmy już wszystkie trójki zawierające n - 3 pierwsze elementy.
Teraz lewa strona: wybrane trzy rozdziały stanowią 3-elementową kombinację bez powtórzeń zbioru n-elementowego, a takich kombinacji jest właśnie \(\displaystyle{ {n \choose 3}}\)