Matematyka.pl

Witam

Jak policzyć ile maksymalnie powinien mieć wyrazów wielomian stopnia \(\displaystyle{ k}\) o \(\displaystyle{ n}\) zmiennych?

W tym celu należy obliczyć liczbę rozwiązań nierówności
\(\displaystyle{ x_1+x_2+\ldots+x_n\le k}\) w liczbach całkowitych nieujemnych. By to osiągnąć, można postąpić co najmniej dwojako:
1) na siłkę, czyli dla \(\displaystyle{ i\in\left\{0,1\ldots k\right\}}\) znaleźć liczbę rozwiązań równania
\(\displaystyle{ x_1+x_2+\ldots+x_n=i}\) w całkowitych nieujemnych, po czym zsumować. To powinno nam dać coś takiego:
\(\displaystyle{ \displaystyle{\sum_{i=0}^{k}{i+n-1 \choose n-1}}}\)
2) Troszkę sprytniej. Zauważmy, że liczba rozwiązań nierówności
\(\displaystyle{ x_1+x_2+\ldots+x_n\le k}\) w całkowitych nieujemnych to liczba rozwiązań równania
\(\displaystyle{ x_1+x_2+\ldots+x_{n+1}=k}\) w całkowitych nieujemnych, czyli \(\displaystyle{ \displaystyle{{n+k\choose n}}}\)

Też doszedłem do tej sumy. Jak ją obliczyć?

Podałem przecież szybsze rozwiązanie i od razu masz postać zwartą. Ale skoro chcesz…

Interpretacja kombinatoryczna.
Ustawiamy w rzędzie \(\displaystyle{ n+k}\) osób (numerując je) i wybieramy spośród nich \(\displaystyle{ n}\) osób do drużyny. Z jednej strony oczywiście możemy to uczynić na \(\displaystyle{ \displaystyle{{n+k\choose n}}}\) sposobów. Z drugiej strony możemy spojrzeć na sprawę tak:
ostatnia osoba w tym rzędzie, którą wybierzemy, będzie miała numer \(\displaystyle{ n+i}\) dla pewnego \(\displaystyle{ i\in\left\{0,1\ldots k\right\}}\). Jeżeli ustalimy tę osobę, to spośród osób o numerach mniejszych, których jest dokładnie \(\displaystyle{ n+i-1}\), wybierzemy do drużyny dokładnie \(\displaystyle{ n-1}\) (by w sumie było \(\displaystyle{ n}\) osób). Stąd jest druga postać, czyli
\(\displaystyle{ \displaystyle{\sum_{i=0}^{k}{i+n-1\choose n-1}}}\) (no i oczywiście te liczby muszą być równe).

Liczba rozwiązań całkowitych nieujemnych równania \(\displaystyle{ x_1+\dots+x_{n+1}=k}\) równa się liczbie rozwiązań całkowitych dodatnich równania \(\displaystyle{ x_1+\dots+x_{n+1}=n+k+1}\). By ją wyliczyć wyobrażamy sobie centymetr krawiecki (lub pasek papieru) długości \(\displaystyle{ n+k+1}\) centymetrów (podzielony na działki centymetrowe \(\displaystyle{ n+k}\) kreskami). Rozwiązanie drugiego równania wyobrażamy sobie jak podział tego paska kolejnymi \(\displaystyle{ n}\) cięciami wzdłuż kresek podziału. Widać, że jest \(\displaystyle{ \displaystyle{{n+k\choose n}}}\) możliwości.

Bardzo dziękuję.
Wszystko zrozumiałem za wyjątkiem tego, dlaczego liczba rozwiązań w/w równania jest równa liczbie rozwiązań w/w nierówności.

Wszystko zrozumiałem za wyjątkiem tego, dlaczego liczba rozwiązań w/w równania jest równa liczbie rozwiązań w/w nierówności.

Dość łatwo widać, że istnieje bijekcja między zbiorem rozwiązań nierówności
\(\displaystyle{ x_1+x_2+\ldots+x_{n}\le k}\) a zbiorem rozwiązań równania \(\displaystyle{ x_1+x_2+\ldots+x_{n+1}=k}\) (oczywiście wszystko w całkowitych nieujemnych), mianowicie niech liczby całkowite nieujemne \(\displaystyle{ x_1, x_2\ldots x_n}\) spełniają zależność
\(\displaystyle{ x_1+x_2+\ldots+x_n\le k}\) i niech wtedy
\(\displaystyle{ f(x_1, x_2, \ldots x_n)=(x_1, x_2, \ldots x_n, k-(x_1+x_2+\ldots+x_n))}\).
Nie jesteśmy na wykładzie z cholernej aksjomatycznej teorii mnogości, oczywiste, że \(\displaystyle{ f}\) jest funkcją. Teraz:
1) \(\displaystyle{ f}\) jest injekcją: niech \(\displaystyle{ (x_1, x_2, \ldots x_n)}\) oraz \(\displaystyle{ (y_1, y_2,\ldots y_n)}\) będą n-kami liczb całkowitych nieujemnych spełniających wspomnianą nierówność. Jeśli \(\displaystyle{ f(x_1, x_2, \ldots x_n)=f(y_1, y_2,\ldots y_n)}\), to znaczy, że
\(\displaystyle{ (x_1, x_2, \ldots x_n, k-(x_1+x_2+\ldots+x_n))=(y_1, y_2, \ldots y_n, k-(y_1+y_2+\ldots+y_n))}\),
w szczególności \(\displaystyle{ x_1=y_1, x_2=y_2, \ldots x_n=y_n}\), czyli
\(\displaystyle{ (x_1, x_2, \ldots x_n)=(y_1, y_2,\ldots y_n)}\)
2) obrazem funkcji \(\displaystyle{ f}\) jest zbiór rozwiązań równania \(\displaystyle{ x_1+x_2+\ldots+x_n+x_{n+1}=k}\) w liczbach całkowitych nieujemnych.
Istotnie, ustalmy dowolne \(\displaystyle{ (x_1, x_2, \ldots x_n, x_{n+1})\in \mathbb{Z}_{+}^{n+1}}\) (tutaj wyjątkowo \(\displaystyle{ \mathbb{Z}_{+}}\) to zbiór liczb całkowitych nieujemnych!) spełniające warunek \(\displaystyle{ x_1+x_2+\ldots+x_n+x_{n+1}=k}\). Wówczas oczywiście \(\displaystyle{ f(x_1, x_2, \ldots x_n)=(x_1, x_2, \ldots x_{n+1})}\) i \(\displaystyle{ x_1+x_2+\ldots+x_n=k-x_{n+1}\le k}\), bo \(\displaystyle{ x_{n+1}\in \mathbb{Z}_{+}}\).

Bardzo drobiazgowo to rozpisałem (tak mi się przynajmniej wydaje), może teraz w końcu będzie jasne. Dla mnie to jest trywiał, ale może to być kwestia doświadczenia.

Dzięki.

W podręczniku do algebry znalazłem identyczną nierówność ze wskazówką, by danemu rozwiązaniu przyporządkować ciąg:
\(x_1+1; x_1+x_2+2;...; x_1+x_2+...+x_n+n\). I teraz: Tyle jest różnych rozwiązań nierówności, ile różnych ciągów przyporządkowanych ściśle rosnących. Te z kolei mają każdy k elementów i losujemy je ze zbioru: \(n+k\). Zainteresowanych odsyłam do książki: Elementy algebry wyższej, Mostowski Stark. Ustęp o wariacjach równoważnych.