Liczba jednomianów w wielomianie

[Bran]

Udowodnij, że maksymalna liczba jednomianów (które nie są podobne) wielomianu \(\displaystyle{ n}\) zmiennych stopnia \(\displaystyle{ d}\) jest równa \(\displaystyle{ {n+d \choose n}.}\)

[Dasio11]

Wskazówka: parami niepodobnych jednomianów \(\displaystyle{ x_1^{d_1} \cdot \ldots \cdot x_n^{d_n}}\) jest tyle co ciągów ich wykładników \(\displaystyle{ (d_1, \ldots, d_n)}\).

[Bran]

Co to jest \(\displaystyle{ x_1,x_2,\dots, x_n}\)?

[Dasio11]

Wielomian \(\displaystyle{ n}\) zmiennych zazwyczaj zapisuje się jako \(\displaystyle{ W(x_1, x_2, \ldots, x_n)}\), a \(\displaystyle{ x_1, x_2,\ldots, x_n}\) to właśnie te zmienne.

[Bran]

Czyli wystarczy dowieść, że
\(\displaystyle{ {n+d \choose n} = (d+1)^n}\)?

[Dasio11]

Nie, zresztą to nieprawda. Jaki warunek muszą spełniać wykładniki jednomianu \(\displaystyle{ x_1^{d_1} \cdot x_2^{d_2} \cdot \ldots \cdot x_n^{d_n}}\) aby mógł on wystąpić w wielomianie stopnia \(\displaystyle{ d}\) ?

[Bran]

Muszą być to liczby naturalne i przynajmniej jedna z nich musi być równa \(\displaystyle{ d}\)?

[Dasio11]

Kod: Zaznacz cały

https://pl.wikipedia.org/wiki/Stopie%C5%84_wielomianu

[Bran]

Znakiem tego, aby taki jednomian mógł wystąpić w wielomianie, to jest wykładniki muszą się sumować do liczby naturalnej nie większej niż \(\displaystyle{ d.}\)

[Dasio11]

Dobrze - zatem do policzenia jest liczba ciągów \(\displaystyle{ (d_1, \ldots, d_n)}\) liczb całkowitych nieujemnych spełniających \(\displaystyle{ d_1 + \ldots + d_n \le d}\).

[Bran]

Różnych rozwiązań równania \(\displaystyle{ d_1 + \ldots + d_n = d}\) jest \(\displaystyle{ {d+n-1 \choose d} }\)
dla równania \(\displaystyle{ d_1 + \ldots + d_n = d-1}\) otrzymujemy wzór \(\displaystyle{ {(d-1)+n-1 \choose d} }\)

Zatem ilość rozwiązań żądanej nierówności, to \(\displaystyle{ \sum_{k=0}^{d} {(d-k)+n-1 \choose d}}\) i właśnie tyle jest takich ciągów?

[Dasio11]

Raczej: \(\displaystyle{ \sum_{k=0}^d \binom{(d-k)+n-1}{d-k}}\).

Ale prościej jest zauważyć, że rozwiązań nierówności \(\displaystyle{ d_1 + \ldots + d_n \le d}\) w liczbach całkowitych nieujemnych jest tyle co rozwiązań równania \(\displaystyle{ d_1 + \ldots + d_n + u = d}\) w liczbach całkowitych nieujemnych, bo każdy układ spełniający nierówność można zamienić w układ spełniający równość, kładąc \(\displaystyle{ u := d - (d_1 + \ldots + d_n)}\).

[Bran]

Czyli \(\displaystyle{ {d+n \choose d+1}}\) ?

[Dasio11]

Nie.

[Bran]

\(\displaystyle{ {d+n \choose d} = {d+n \choose d+n-d} = {d+n \choose n}}\)

i to jest koniec zadania (?)

Da się to zrobić również indukcyjnie? (bo autor zadania umieścił zadanie w dziale o indukcji, nie wymusza rozwiązania indukcyjnego w treści, ale domyślam się, że jednak mógł mieć taki zamysł)