Ilosc rozwiazan rownania

[mdcbnmw2000]

Ile jest calkowitoliczbowych nieujemnych rozwiazan rownania :
\(\displaystyle{ a + b + c + d = 12}\)
gdzie \(\displaystyle{ a,b,c,d \le 5}\).

Proszę o pomoc.
Przy podobnych zadaniach tworzyłem zazwyczaj zmienne pomocnicze po czym stosowałem kombinację ale z tym nie wiem co mam zrobić

[kerajs]

Jakie sumy spełniające założenie wynoszą 12?
Składające się z liczb:
5,5,2,0
5,5,1,1
5.4,3,0
5,4,3,1
5,3,3,1
5,3,2,2
4,4,4,0
4,4,3,1
4,4,2,2
4,3,3,2
3,3,3,3
Teraz wystarczy dla każdego układu policzyć ilość permutacji i je zsumować otrzymując liczbę rozwiązań.

[mdcbnmw2000]

Dziękuje! Czy znasz może jakiś szybszy sposób niż wypisywanie?

[kerajs]

Przypuszczam że to najszybszy sposób.

[Gouranga]

kerajs, źle Ci się wydaje
hasło kluczowe to "Funkcje generujące"
dla \(\displaystyle{ a}\) możemy wybrać wartości od 0 do 5, tak samo dla każdej pozostałej stąd mamy:
\(\displaystyle{ \left(z^0+z^1+z^2+z^3+z^4+z^5\right)^4}\)
potęgi reprezentują tu wartości a potęga 4 dlatego że dla każdej zmiennej mamy ten sam wybór, po przemnożeniu wszystkiego (co można zrobić np. wolframem: ... 5E5%29%5E4) patrzymy na współczynnik przy \(\displaystyle{ z^{12}}\) bo taka suma nas interesowała (w wolframie patrz na "expanded form"), wychodzi 125 ale przy zadaniach tego typu akceptowalną odpowiedzią jest taki zapis:
\(\displaystyle{ \left(z^0+z^1+z^2+z^3+z^4+z^5\right)^4 \quad \left[z^{12}\right]}\)
to znaczy dokładnie tyle że chodzi nam o ten współczynnik w kwadratowych nawiasach z podanego wyrażenia

[kerajs]

Moim zdaniem sposób który podałeś nie jest szybszy wtym zadaniu. Pisemne mnożenie i porządkowanie wielomianu jest czasochłonne, a samo szukanie współczynników przy \(\displaystyle{ z ^{12}}\) sprowadza się do znalezienia permutacji między odpowiednimi potęgami czyli do wypisania układów wykładników .




Ps. W piątym układzie zamiast \(\displaystyle{ 5,3,3,1}\) ma być \(\displaystyle{ 5,3,2,1}\).

[Gouranga]

dobrze, to rozwiąż to samo ale ze zmienioną treścią:
\(\displaystyle{ x_1 + x_2 + \ldots + x_{10} = 31\\
x_3 \in \{2,3,5\}\\
x_5, x_6 > 4\\
x_8 \le 2}\)
powodzenia w wypisywaniu, a funkcja generująca działa dokładnie tak samo

[kerajs]

@Gouranga,

Jak się często w takich dyskusjach zdarza problem znika jeśli ustali sie co dla oponentów jest przedmiotem sporu. Ja , i sądząc po Twoim pierwszym poscie także Ty, ustosunkowywałem sie do szybkości rozwiązywania tego konkretnego zadania.

[Gouranga]

kerajs, no właśnie ja podałem sposób na ten typ zadań a nie na konkretny przykład
ale to normalne zważywszy na fakt, że jestem informatykiem, informatyk nigdy nie napisze programu Destroy Bagdad, napisze program Destroy City i poda Bagdad jako konkretny przykład

[mdcbnmw2000]

A czy poprawnym będzie rozwiązanie \(\displaystyle{ {15 \choose 3} - 4 * {10 \choose 3}}\) ?

[kerajs]

Odpowiedź już padła : 125

\(\displaystyle{ {15 \choose 3} - 4 * {10 \choose 3}=455-4 \cdot 120=-15}\)

[norwimaj]

A czy poprawnym będzie rozwiązanie \(\displaystyle{ {15 \choose 3} - 4 * {10 \choose 3}}\) ?

Mało brakowało, abyś napisał najprostsze rozwiązanie w tym temacie.

\(\displaystyle{ \binom{15}3-4\cdot\binom93+\binom42\cdot\binom33=455-336+6=125.}\)

Rozwiązanie Kerajsa jest dość pracochłonne, a rozwiązanie Gourangi chyba niepełne (nie dopatrzyłem się metody znajdowania odpowiedniego wyrazu wielomianu).

[Gouranga]

norwimaj, odpowiedni współczynnik znajdujemy rozwijając wyrażenie i porządkując je ale nie trzeba tego robić, wystarczy podanie odpowiedzi który współczynnik z jakiej funkcji

[norwimaj]

wystarczy podanie odpowiedzi który współczynnik z jakiej funkcji

A dlaczego nie wystarczy po prostu odpowiedź, że chodzi o liczbę całkowitoliczbowych, nieujemnych rozwiązań równania \(\displaystyle{ a + b + c + d = 12,}\) gdzie \(\displaystyle{ a,b,c,d \le 5 ?}\)

[Gouranga]

norwimaj, bo nie wiemy ile ich jest natomiast wiemy jaki jest współczynnik przy \(\displaystyle{ z^{12}}\) w tym wielomianie (wiemy = jesteśmy w stanie to obliczyć), nie trzeba przemnażać tego do konkretnej liczby ręcznie ale można się posłużyć odpowiednim do tego programem.