Równanie w liczbach całkowitych

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
PoweredDragon
Użytkownik
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

Równanie w liczbach całkowitych

Post autor: PoweredDragon »

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.)
Kaf
Użytkownik
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

Post autor: Kaf »

\(\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
PoweredDragon
Użytkownik
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

Post autor: PoweredDragon »

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.
ODPOWIEDZ