Witam. Czy potrafi ktoś uzasadnić, że dla
\(\displaystyle{ r \in \mathbb Z_+}\) istnieje dokładnie \(\displaystyle{ {r+n-1 \choose r}}\) rozwiązań równania \(\displaystyle{ \sum_{i=1}^{n} x_i = r}\) dla \(\displaystyle{ x_i \in \mathbb Z_+}\). Znalazłem kilka pdfów, w których owe twierdzenie się pojawiło, jednak nigdy z dowodem ani słownym opisem. Sam łatwiej formułuję wnioski niż uzasadniam cudze, dlatego poznawszy ten wzór nie widzę skąd on się wziął... (a wydaje się to rzeczą dość banalną; żałuję że wcześniej olewałem wszelkiego rodzaju równania diofantyczne, liniowe, itd.)
Równanie w liczbach całkowitych
-
- Użytkownik
- Posty: 817
- Rejestracja: 19 lis 2016, o 23:48
- Płeć: Mężczyzna
- wiek: 21
- Lokalizacja: Polska
- Podziękował: 3 razy
- Pomógł: 115 razy
-
- Użytkownik
- Posty: 826
- Rejestracja: 8 wrz 2013, o 11:31
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Pomógł: 187 razy
Re: Równanie w liczbach całkowitych
\(\displaystyle{ \mathbb Z_+}\) oznacza liczby całkowite nieujemne? Bo inaczej to nieprawda.
Przeformułujmy to tak, żeby uzyskać analogiczny problem, ale dla liczb całkowitych dodatnich: Zauważmy, że rozwiązania pierwotnego równania odpowiadają wzajemnie jednoznacznie rozwiązaniom równania \(\displaystyle{ (*) \sum_{i=1}^{n} y_i = r+n}\) - odpowiedniość jest dana przez \(\displaystyle{ x_i \mapsto x_i+1=y_i}\). Teraz już prosto: narysujmy \(\displaystyle{ r+n}\) kropek. Między nimi jest łącznie \(\displaystyle{ r+n-1}\) wolnych miejsc. Wybierzmy \(\displaystyle{ n-1}\) z nich, co możemy zrobić na \(\displaystyle{ {r+n-1 \choose n-1}}\) sposobów. Wystarczy teraz zauważyć, że taki ciąg kropek pooddzielanych kreskami to* rozwiązanie równania \(\displaystyle{ (*)}\). Voila
*jeśli się odpowiednio na to spojrzy
Przeformułujmy to tak, żeby uzyskać analogiczny problem, ale dla liczb całkowitych dodatnich: Zauważmy, że rozwiązania pierwotnego równania odpowiadają wzajemnie jednoznacznie rozwiązaniom równania \(\displaystyle{ (*) \sum_{i=1}^{n} y_i = r+n}\) - odpowiedniość jest dana przez \(\displaystyle{ x_i \mapsto x_i+1=y_i}\). Teraz już prosto: narysujmy \(\displaystyle{ r+n}\) kropek. Między nimi jest łącznie \(\displaystyle{ r+n-1}\) wolnych miejsc. Wybierzmy \(\displaystyle{ n-1}\) z nich, co możemy zrobić na \(\displaystyle{ {r+n-1 \choose n-1}}\) sposobów. Wystarczy teraz zauważyć, że taki ciąg kropek pooddzielanych kreskami to* rozwiązanie równania \(\displaystyle{ (*)}\). Voila
*jeśli się odpowiednio na to spojrzy
-
- Użytkownik
- Posty: 817
- Rejestracja: 19 lis 2016, o 23:48
- Płeć: Mężczyzna
- wiek: 21
- Lokalizacja: Polska
- Podziękował: 3 razy
- Pomógł: 115 razy
Re: Równanie w liczbach całkowitych
Ah tak; chodziło oczywiście o liczby całkowite nieujemne, mój błąd. Dzięki za wytłumaczenie, w sumie całkiem logiczne i proste.