Uogólniony wzór Newtona

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
fibi

Uogólniony wzór Newtona

Post autor: fibi »

Czy jest jakiś szybki sposób, żeby bez wymnażania nawiasów obliczyć np. wspolczynnik przy \(\displaystyle{ x^{25}}\) w wyrazeniu \(\displaystyle{ (1+x+x^2+x^3+x^4+x^5)^{10}}\)?
Awatar użytkownika
miki999
Użytkownik
Użytkownik
Posty: 8691
Rejestracja: 28 lis 2007, o 18:10
Płeć: Mężczyzna
Lokalizacja: Gdańsk
Podziękował: 36 razy
Pomógł: 1001 razy

Uogólniony wzór Newtona

Post autor: miki999 »

Może coś z trójkątem Pascala pokombinować?

edit:
W sumie zagadnienie jest trochę trudniejsze niż myślałem. Może później trochę pomyślę. Jak jakiś Mod tu zajrzy, to może usunąć tego posta.

edit 2.:
Żeby mój post jednak coś wnosił, to coś napiszę, ale niestety nie jest to sprytny sposób, a z pewnością nie jest to coś, z czego mógłbym być dumny
Najpierw dla ułatwienia należy stworzyć sobie trójkąt Pascala (do 10. stopnia).
Teraz nasz wielomian sobie grupujemy:
\(\displaystyle{ (1+x+x^2+x^3+x^4+x^5)^{10}=(1+x+x^2+x^3(1+x+x^2))^{10}=(1+x+x^2)^{10}(x^3+1)^{10}}\)
Teraz, wierząc wzorowi z wiki:
\(\displaystyle{ (1 + x)^\alpha = \sum_{k=0}^{\alpha} \; {\alpha \choose k} \; x^k}\)
,liczymy:
\(\displaystyle{ (1+x^{3})^{10} \cdot (1+x+x^2)^{10}=[x^{30}+10x^{27}+45x^{24}+120x^{21}+212x^{18}+256x^{15}+212x^{12}+120x^{9}+45x^{6}+10x^{3}+1] \cdot (1+x+x^2)^{10}}\)
Podstawiając \(\displaystyle{ a=x+x^2}\), korzystamy z tego samego wzoru i mnożymy drugi nawias. Ja sobie czasu zaosczędze i od razu pod \(\displaystyle{ a}\) podstawię \(\displaystyle{ x+x^2}\):
\(\displaystyle{ (1+x+x^2)^{10}=(x+x^{2})^{10}+10(x+x^2)^9+45(x+x^2)^8+120(x+x^2)^7+212(x+x^2)^6+256(x+x^2)^5+212(x+x^2)^4+120(x+x^2)^3+45(x+x^2)^2+10x+10x^2+1}\)
Teraz wyłączamy w tym wyrażeniu z nawiasów liczbę \(\displaystyle{ x}\) i każdy z nich potęgujemy, jak te powyżej:
\(\displaystyle{ (x+x^{2})^{10}+10(x+x^2)^9+45(x+x^2)^8+120(x+x^2)^7+212(x+x^2)^6+256(x+x^2)^5+212(x+x^2)^4+120(x+x^2)^3+45(x+x^2)^2+10x+10x^2+1=x^{10}(1+x)^{10}+10x^{9}(1+x)^9+45x^8(1+x)^8+120x^7(1+x)^7+212x^6(1+x)^6+256x^5(1+x)^5+212x^4(1+x)^4+120x^3(1+x)^3+45x^2(1+x)^2+10x+10x^2+1=x^{10}[x^{10}+10x^9+45x^8+120x^7+212x^6+256x^5+212x^4+120x^3+45x^2+10x+1]+10x^9[x^9+9x^8+36x^7+84x^6+128x^5+128x^4+84x^3+36x^2+9x+1]+45x^8[x^8+8x^7+28x^6+56x^5+70x^4+56x^3+28x^2+8x+1]+120x^7[x^7+7x^6+21x^5+34x^4+35x^3+21x^2+7x+1]+212x^6[x^6+6x^5+15x^4+20x^3+15x^2+6x+1]+256x^5[x^5+5x^4+10x^3+10x^2+5x+1]+212x^4[x^4+4x^3+6x^2+4x+1]+120x^3[x^3+3x^2+3x+1]+45x^2[x^2+2x+1]+10x+10x^2+1]}\)
Dalej już prosto, ponieważ mamy mnożenie 2 nawiasów ( \(\displaystyle{ a)\ i\ b)}\) ):
\(\displaystyle{ a)\ [x^{30}+10x^{27}+45x^{24}+120x^{21}+212x^{18}+256x^{15}+212x^{12}+120x^{9}+45x^{6}+10x^{3}+1] \\ b)\ x^{10}[x^{10}+10x^9+45x^8+120x^7+212x^6+256x^5+212x^4+120x^3+45x^2+10x+1]+10x^9[x^9+9x^8+36x^7+84x^6+128x^5+128x^4+84x^3+36x^2+9x+1]+45x^8[x^8+8x^7+28x^6+56x^5+70x^4+56x^3+28x^2+8x+1]+120x^7[x^7+7x^6+21x^5+34x^4+35x^3+21x^2+7x+1]+212x^6[x^6+6x^5+15x^4+20x^3+15x^2+6x+1]+256x^5[x^5+5x^4+10x^3+10x^2+5x+1]+212x^4[x^4+4x^3+6x^2+4x+1]+120x^3[x^3+3x^2+3x+1]+45x^2[x^2+2x+1]+10x+10x^2+1]}\)
Czyli wystarczy przypasować odpowiednie potęgi z \(\displaystyle{ a)}\) odpowiednim nawiasom z \(\displaystyle{ b)}\).Naturalnie wszystkie powyżej \(\displaystyle{ 25.}\) potęgi omijamy. Pierwszym wyrazem z \(\displaystyle{ a)}\) jest \(\displaystyle{ 45x^{24}}\) musimy znaleźć wszystkie wyrazy z \(\displaystyle{ b)}\), gdzie potęga \(\displaystyle{ x}\) wynosi \(\displaystyle{ 1}\). Jedyny taki element znajduje się zaraz przy końcu. Mnożymy współczynniki. Następnie patrzymy kolejny wyraz z \(\displaystyle{ a)}\). Jest to \(\displaystyle{ 120x^{21}}\). Postępujemy analogicznie, czyli tym razem szukamy w \(\displaystyle{ b)}\) iksa podniesionego do potęgi \(\displaystyle{ 4.}\) Takowy znajduje się w pierwszym nawiasie od końca (jako iloczyn \(\displaystyle{ 45x^2\ z\ 2x}\) oraz nawias wcześniej jako iloczyn \(\displaystyle{ 120x^3\ z\ 3x}\) i jeszcze wcześniejszym nawiasie jako iloczyn: \(\displaystyle{ 212x^4\ z\ 1}\). I tak bawiąc się "chwilkę" dochodzimy do sumy:
\(\displaystyle{ 45 \cdot 10+120(45+120 \cdot 3+212)+212 \cdot (212 \cdot 4 + 2560+212 \cdot 6+120)+256(256+212 \cdot 15+120 \cdot 35+45 \cdot 28+10 \cdot 9+1)+212(120 \cdot 7+45 \cdot 56+10 \cdot 128+120)+120 \cdot (45+360+212)+10=4475932}\)

Program Mathematica pokazuje, że powinno wyjść: \(\displaystyle{ 4395456}\). Chyba nie masz do mnie żalu za błąd rachunkowy? Możesz poszukać błędu, jak masz ochotę.


Pozdrawiam.
fibi

Uogólniony wzór Newtona

Post autor: fibi »

Dzięki za tak długą odpowiedź Ale też nie ukrywam, że mnie ona nie satysfakcjonuje

Moze podam kontekst w jakim pojawia sie to rownanie:

"Na ile sposobow mozna uzyskac sume dwudziestu pieciu oczek na dziesieciu roznych kostkach do gry?"

Zadanie jest na funkcje tworzace, wiec ukladam sobie takowa: \(\displaystyle{ (x+x^2+x^3+x^4+x^5+x^6)^{10}}\) no i szukam wspolczynnika przy \(\displaystyle{ x^{25}}\), czyli de facto wspolczynnika przy \(\displaystyle{ x^{15}}\) dla \(\displaystyle{ (1+x+x^2+x^3+x^4+x^5)^{10}}\).

A na koncu ksiazki w odpowiedziach jest \(\displaystyle{ {24\choose 15}-10{18\choose 9}+{10 \choose 2}{12 \choose 3}}\) i ciekawi mnie skad sie wzial ten wynik...

Pozdrawiam
Użytkownik
Użytkownik
Posty: 9833
Rejestracja: 18 gru 2007, o 03:54
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 90 razy
Pomógł: 2632 razy

Uogólniony wzór Newtona

Post autor: »

Skorzystamy z faktu, że liczbę \(\displaystyle{ n}\) można rozłożyć na \(\displaystyle{ k}\) rozróżnialnych składników na \(\displaystyle{ {n+ k - 1 \choose n}}\) sposobów.

Mamy:
\(\displaystyle{ (1+x+x^2+x^3+x^4+x^5+x^6)^{10}= \\ \\ = \left( (1-x^6) \cdot \frac{1}{1-x}\right)^{10} = \\ \\ =
(1-x^6)^{10} \cdot (1+x+ x^2 + \dots )^{10}}\)


(bo \(\displaystyle{ \frac{1}{1-x} = (1+x+ x^2 + \dots )}\))

Mamy więc trzy możliwości - z lewego wielomianu bierzemy iksa w potędze zerowej, a z prawego w piętnastej, z lewego w szóstej, a z prawego w dziewiątej oraz z lewego w dwunastej, a z prawego w trzeciej. Ale to co stoi przy iksie do potęgi \(\displaystyle{ k}\) z prawej strony to ilość podziałów liczby \(\displaystyle{ k}\) na \(\displaystyle{ 10}\) rozróżnialnych części, czyli \(\displaystyle{ { k +10 -1 \choose k}}\). A to stoi przy iksie przy prawej to kolejne współczynniki rozwinięcia dwumianu Newtona.

Tak więc po zsumowaniu tych trzech możliwości dostaniemy:
\(\displaystyle{ {10 \choose 0 } \cdot { 15 +10 -1 \choose 15} - {10 \choose 1} \cdot { 9 +10 -1 \choose 9} + {10 \choose 2} \cdot { 3 +10 -1 \choose 3}}\)
i to jest właśnie szukana odpowiedź.

Q.
fibi

Uogólniony wzór Newtona

Post autor: fibi »

O to mi wlasnie chodzilo. Dzieki wielkie :)
ODPOWIEDZ