Uogólniony wzór Newtona
Uogólniony wzór Newtona
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}}\)?
- miki999
- 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
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.
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.
Uogólniony wzór Newtona
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
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
- 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
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.
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.