Ile jest rozwiązań w liczbach całkowitych

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
FaloZ
Użytkownik
Użytkownik
Posty: 12
Rejestracja: 30 wrz 2017, o 15:31
Płeć: Mężczyzna
Lokalizacja: Warszawa

Ile jest rozwiązań w liczbach całkowitych

Post autor: FaloZ »

Mam problem z takim zadankiem i prosiłbym o sprawdzenie mojego toku myślenia.

Ile jest rozwiązań w liczbach całkowitych równania postaci: \(\displaystyle{ x_{1} + x_{2} + x_{3} + x_{4} = 12}\), jeśli:

a) \(\displaystyle{ x_{1} \ge 0, i = 1,2,3,4}\)
b) \(\displaystyle{ x_{1} > 0, i = 1,2,3,4}\)

Rozw. (Zadanie robiliśmy na ćwiczeniach, ale nie wszystko zrozumiałem).
a) Po przemyśleniach: Kolejność liczb jest nie istotna, ponieważ z odpowiednich aksjomatów wiemy, że dodawanie jest przemienne. Liczby mogą się powtarzać, np. może wystąpić sytuacja \(\displaystyle{ x_{1} = 10 , x_{2} = 1, x_{3} = 1, x_{4} = 0}\). W takim razie słusznym pomysłem wydaje się użycie wzorku na kombinacje z powtórzeniami. Liczba \(\displaystyle{ k}\)-elementowych kombinacji z powtórzeniami zbioru \(\displaystyle{ n}\)-elementowego wygląda następująco:

\(\displaystyle{ {n+k-1 \choose k}}\)

Wynik na ćwiczeniach otrzymaliśmy taki:

\(\displaystyle{ {4+12- 1 \choose 12} = {15 \choose 12}}\)

A moim zdaniem powinno być tak:

\(\displaystyle{ {4+13- 1 \choose 12} = {16 \choose 13}}\)

Spieszę z wyjaśnieniem. \(\displaystyle{ n=4}\), ponieważ naszym \(\displaystyle{ n}\)-elementowym zbiorem będą tutaj niewiadome, z których "tworzymy" sumę równą \(\displaystyle{ 12}\). Jednak, czy tutaj \(\displaystyle{ k=13}\) ? Myślałem, że liczba \(\displaystyle{ k}\)-elementowych kombinacji będzie właśnie \(\displaystyle{ 13}\), ponieważ uwzględniamy liczby z przedziału \(\displaystyle{ \{0, ... , 12 \}}\). Jeśli jestem w błędzie to najwidoczniej nadal mam problemy ze zrozumieniem definicji kombinacji z powtórzeniami i prosiłbym o sprostowanie.

Przykład b) chyba jest dla mnie zrozumiały, względem wyniku uzyskanego na ćwiczeniach.. Uwzględniam "skrajny" przypadek, czyli np. \(\displaystyle{ x_{1} = 9 , x_{2} = 1, x_{3} = 1, x_{4} = 1}\). Dlaczego tak? Każda liczba musi być większa od zera, dlatego minimalną wartością dla każdej z trzech liczb będzie "\(\displaystyle{ 1}\)". Aby suma była równa \(\displaystyle{ 12}\), musimy dodać \(\displaystyle{ 9}\). W tym przypadku otrzymalibyśmy nadal \(\displaystyle{ n=4}\) i \(\displaystyle{ k=8}\), bo mamy liczby z przedziału \(\displaystyle{ \{1,....,8\}}\). Zatem otrzymujemy:

\(\displaystyle{ {4 + 8 - 1 \choose 8} = {11 \choose 8}}\)
Awatar użytkownika
MrCommando
Użytkownik
Użytkownik
Posty: 554
Rejestracja: 5 gru 2016, o 21:55
Płeć: Mężczyzna
Lokalizacja: Płock/MiNI PW
Podziękował: 48 razy
Pomógł: 107 razy

Ile jest rozwiązań w liczbach całkowitych

Post autor: MrCommando »

Najlepiej zadania tego typu rozrysować sobie graficznie - "metodą kropek i kresek".

Na przykład tak: \(\displaystyle{ |\cdot \cdot \cdot | \cdot \cdot \cdot \cdot | \cdot \cdot | \cdot \cdot \cdot|}\).

W powyższym schemacie kreski tworzą nam cztery przegródki z kropkami, których ilości odpowiadają wartościom niewiadomych \(\displaystyle{ x_1, x_2, x_3, x_4}\). Wszystkich kropek mamy \(\displaystyle{ 12}\). Łatwo zatem zauważyć, że ten schemat przedstawia czwórkę liczb \(\displaystyle{ (x_1,x_2,x_3,x_4)=(3,4,2,3)}\). Aby wyznaczyć liczbę wszystkich rozwiązań w liczbach naturalnych, należy obliczyć na ile sposobów możemy te kreski poprzestawiać. Załóżmy, że manipulujemy tylko trzema kreskami (te skrajne zostawiamy w spokoju). Generalnie kropek i kresek, które przestawiamy, jest razem \(\displaystyle{ 12+3=15}\) (zajmują one jakby \(\displaystyle{ 15}\) miejsc). Spośród tych \(\displaystyle{ 15}\) miejsc wybieramy \(\displaystyle{ 3}\), na których mają stać te kreski. Zatem możliwości wyboru jest \(\displaystyle{ {15 \choose 3}}\), co jest oczywiście równe \(\displaystyle{ {15 \choose 12}}\), czyli tyle ile uzyskaliście na ćwiczeniach.

Moim zdaniem w taki sposób jest lepiej podchodzić do takich problemów niż zapamiętywać na siłę różne wzory. Mam nadzieję, że w miarę jasno to wytłumaczyłem. Gdyby coś tu było nie do końca zrozumiałe, to pytaj dalej .

Analogicznie możesz wyznaczyć wzór na liczbę rozwiązań równania \(\displaystyle{ x_1+x_2+x_3+...+x_k=n}\) w liczbach naturalnych (nieujemnych). Nietrudno się przekonać, że rozwiązań tych jest \(\displaystyle{ {n+k-1 \choose k-1}}\), czy też jak wolisz \(\displaystyle{ {n+k-1 \choose n}.}\)

Można powiedzieć, że obliczasz ile jest dwunastoelementowych kombinacji z powtórzeniami zbioru czteroelementowego. Kropek (czyli elementów każdej kombinacji) jest \(\displaystyle{ 12}\), a przegródki są \(\displaystyle{ 4}\). Założenie o tej trzynastce było błędne, bo kropek w sumie zawsze będzie dwanaście, a nie trzynaście.

Z kolei gdybyś miał wyznaczyć liczbę rozwiązań takiego równania w liczbach naturalnych dodatnich, to troszeczkę inaczej będzie. Wtedy proponowałbym podstawić do tego równania \(\displaystyle{ y_i=x_i-1}\) (oczywiście \(\displaystyle{ 1\leq i \leq n\k}\)), a potem zastosować powyższą metodę dla zmiennych \(\displaystyle{ y_i}\) (sprowadzamy zagadnienie do poprzednio rozwiązanego problemu ).
ODPOWIEDZ