Test Arka: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
← poprzednia edycja
WizualnieWikikod
Arek (dyskusja | edycje)
687 edycji
Nie podano opisu zmian
m Zastępowanie tekstu – „\displaystyle ” na „”
 
(Nie pokazano 17 wersji utworzonych przez 3 użytkowników)
Linia 1: Linia 1:
==Problemy ze wzorami na osiłku==
<quiz type="exclusive">
<math>\displaystyle M</math> <math>\displaystyle M'</math> <math>\displaystyle M' </math>
When working with character arrays, always reserve enough array elements to hold the string AND its null-terminating character (\0).
<math>\displaystyle {\large a^{\sum_{i=1}^{10}i}}</math>
<rightoption>True</rightoption>
<wrongoption>False</wrongoption>
</quiz>
==Testy==


A powinno to wyglądać tak:
<quiz type="exclusive">
http://www.ii.uj.edu.pl/~pawlik1/MediaWiki
When working with character arrays, always reserve enough array elements to hold the string AND its null-terminating character (\0).
<rightoption>True</rightoption>
<wrongoption>False</wrongoption>
</quiz>


<hr>
<quiz>
When working with character arrays, always reserve enough array elements to hold the string AND its null-terminating character (\0).
<rightoption>True</rightoption>
<wrongoption>False</wrongoption>
</quiz>


<table>
<quiz type="exclusive">
<tr><td>zxczxc</td><td>zxczxc</td></tr>
In C++, 14 % 4 =
</table>
<option reply="Za mało">1</option>
<option>2</option>
<option reply="Za dużo">3</option>
<wrongoption reply="O wiele za dużo">4</wrongoption>
</quiz>
<quiz>
In C++, 14 % 4 =
<option reply="Za mało">1</option>
<option>2</option>
<option reply="Za dużo">3</option>
<wrongoption reply="O wiele za dużo">4</wrongoption>
</quiz>


[[Konwersja Arka]]
<quiz>
[[Konwersja Arka 2]]
Variables that are declared, but not initialized, contain
[[Konwersja Arka 3]]
<wrongoption>blank spaces</wrongoption>
<rightoption reply="Tak, pod warunkiem, że są globalne">zeros</rightoption>
<rightoption reply="Jeśli nie są globalne">"garbage" values</rightoption>
<wrongoption reply="Dostajesz pałę!">nothing - they are empty</wrongoption>
</quiz>


<quiz type="exclusive">
Variables that are declared, but not initialized, contain
<wrongoption>blank spaces</wrongoption>
<rightoption reply="Tak, pod warunkiem, że są globalne">zeros</rightoption>
<rightoption reply="Jeśli nie są globalne">"garbage" values</rightoption>
<wrongoption reply="Dostajesz pałę!">nothing - they are empty</wrongoption>
</quiz>


<hr>


{thm}{Twierdzenie}
<div style="background-color: #bbbbbb; padding: 2em; border: 1px solid black">
{obs}[thm]{Obserwacja}
Dlaczego suma <math>\sum_{i=1}^{10}i</math> jest źle wyświetlana w wykładniku potęgi?
{con}[thm]{Wniosek}


{article}
<math>z^{\sum_{i=1}^{10}i}</math>
{../makraB}


==Funkcje tworzące==


{{przyklad|[Uzupelnij]||
</div>


Słynny matematyk Georg Pólya rozważał problem polegający na
policzeniu wszystkich możliwych sposobów, na które można rozmienić 50 centów używając
jednocentówek <math>\left( 1 \right)</math>,
pięciocentówek <math>\left( 5 \right)</math>,
dziesięciocentówek <math>\left( 10 \right)</math>,
ćwierćdolarówek <math>\left( 25 \right)</math>,
oraz półdolarówki <math>\left( 50 \right)</math>.
Rozważania te doprowadziły go do użycia analitycznych metod funkcji tworzących
w zaproponowanym przez niego rozwiązaniu.
W tym i następnym wykładzie poznamy te metody
i zobaczymy jak mogą być pomocne w zliczaniu rożnych obiektów kombinatorycznych.


Wracając do problemu rozmieniania monet, wygodnie nam będzie posiadać
<div id="content">
jeszcze monetę <math>\left[0\right]</math>, którą możemy interpretować jako brak monet.
<div id="navcontainer">
Wypiszmy teraz (nadużywając trochę notacji)
<ul id="navlist">
nieskończoną sumę wszystkich  możliwości rozmiany dowolnej kwoty
<div><a href="index.xml" class="withChild">Start</a></div>
za pomocą jednocentówek


<center><math>A_1=\left[0\right]+\left( 1 \right)+\left( 1 \right)\left( 1 \right)+\left( 1 \right)\left( 1 \right)\left( 1 \right)+\left( 1 \right)\left( 1 \right)\left( 1 \right)\left( 1 \right)+\ldots
<div id="active" class="withoutChild">Zadanie 1.</div>
</math></center>
<div><a href="zadanie_2.xml" class="withoutChild">Zadanie 2.</a></div>
<div><a href="zadanie_3.xml" class="withoutChild">Zadanie 3.</a></div>
<div><a href="zadanie_4.xml" class="withoutChild">Zadanie 4.</a></div>
<div><a href="zadanie_5.xml" class="withoutChild">Zadanie 5.</a></div>
<div><a href="zadanie_6.xml" class="withoutChild">Zadanie 6.</a></div>


i analogicznie przeanalizujmy sumę dla pieciocentówek
</ul>
</div>
<div id="main">
<div id="nodeDecoration">
<p id="nodeTitle">Zadanie 1.</p>
</div>
<script type="text/javascript" src="common.js"></script> <script
type="text/javascript" src="libot_drag.js"></script>
<div class="iDevice emphasis1"><img alt="Ikona obiektu Pytanie"
class="iDevice_icon" src="icon_question.gif" /> <span
class="iDeviceTitle">Zadanie 1,</span><br />
<div class="iDevice_inner">
Liczba <math><msqrt><mrow><mn>3</mn>


<center><math>A_5=\left[0\right]+\left( 5 \right)+\left( 5 \right)\left( 5 \right)+\left( 5 \right)\left( 5 \right)\left( 5 \right)+\left( 5 \right)\left( 5 \right)\left( 5 \right)\left( 5 \right)+\ldots
<mo class="MathClass-bin">+</mo> <mn>2</mn><msqrt><mrow>
</math></center>
<mn>2</mn></mrow></msqrt></mrow></msqrt> <mo class="MathClass-bin">&minus;</mo><msqrt><mrow><mn>3</mn>
<mo class="MathClass-bin">&minus;</mo> <mn>2</mn><msqrt><mrow>
<mn>2</mn></mrow></msqrt></mrow></msqrt></math> &nbsp;&nbsp;
<table>
<tbody>


Wtedy zbiór par  <math>A_1 \times A_5</math>
<tr>
jest zbiorem wszystkich możliwości rozmiany kwoty mając do dyspozycji
<td><input type="checkbox" name="option9" id="ia0b9"
dowolnie wiele jednocentówek oraz pięciocentówek.
value="vTrue"
onclick="document.getElementById('sa0b9').style.display = this.checked ? 'block' : 'none';" /></td>
<td>jest dodatnia</td>
<td>
<div id="sa0b9" style="color: rgb(0, 51, 204);display: none;">Poprawnie</div>
</td>
</tr>
<tr>


<center><math>\aligned B= A_1 \times A_5
<td><input type="checkbox" name="option9" id="ia1b9"
&=&\left( \left[0\right]+\left( 1 \right)+\left( 1 \right)\left( 1 \right)+\left( 1 \right)\left( 1 \right)\left( 1 \right)+\left( 1 \right)\left( 1 \right)\left( 1 \right)\left( 1 \right)+\ldots \right)\\
value="vTrue"
&&\times\left( \left[0\right]+\left( 5 \right)+\left( 5 \right)\left( 5 \right)+\left( 5 \right)\left( 5 \right)\left( 5 \right)+\left( 5 \right)\left( 5 \right)\left( 5 \right)\left( 5 \right)+\ldots \right)\\
onclick="document.getElementById('sa1b9').style.display = this.checked ? 'block' : 'none';" /></td>
&=&\left[0\right]+\left( 1 \right)+\left( 5 \right)+\left( 1 \right)\left( 1 \right)+\left( 1 \right)\left( 5 \right)+\left( 5 \right)\left( 5 \right)+\left( 1 \right)\left( 1 \right)\left( 1 \right)+\ldots
<td>jest wymierna</td>
\endaligned</math></center>
<td>
<div id="sa1b9" style="color: rgb(0, 51, 204);display: none;">Poprawnie</div>
</td>
</tr>
<tr>
<td><input type="checkbox" name="option9" id="ia2b9"
value="vFalse"
onclick="document.getElementById('sa2b9').style.display = this.checked ? 'block' : 'none';" /></td>


Sumy wszystkich możliwości rozmiany za pomocą dziesięciocentówek <math>\left( 10 \right)</math>,
<td>nale&raquo;y do tr&oacute;jkowego zbioru Cantora.</td>
ćwierćdolarówek <math>\left( 25 \right)</math>,
<td>
oraz półdolarówek <math>\left( 50 \right)</math> wyglądają następująco:
<div id="sa2b9" style="color: rgb(0, 51, 204);display: none;">Źle</div>
 
</td>
<center><math>\aligned A_{10} &=& \left[0\right]+\left( 10 \right)+\left( 10 \right)\left( 10 \right)+\left( 10 \right)\left( 10 \right)\left( 10 \right)+\left( 10 \right)\left( 10 \right)\left( 10 \right)\left( 10 \right)+\ldots\\
</tr>
A_{25} &=& \left[0\right]+\left( 25 \right)+\left( 25 \right)\left( 25 \right)+\left( 25 \right)\left( 25 \right)\left( 25 \right)+\left( 25 \right)\left( 25 \right)\left( 25 \right)\left( 25 \right)+\ldots\\
</tbody>
A_{50} &=& \left[0\right]+\left( 50 \right)+\left( 50 \right)\left( 50 \right)+\left( 50 \right)\left( 50 \right)\left( 50 \right)+\left( 50 \right)\left( 50 \right)\left( 50 \right)\left( 50 \right)+\ldots.
</table>
\endaligned</math></center>
 
Dodając kolejno  monety <math>\left( 10 \right)</math>, <math>\left( 25 \right)</math>,
i na końcu <math>\left( 50 \right)</math>
do możliwych rozmian uzyskujemy odpowiednio:
 
<center><math>\aligned C&=&B\times\left( \left[0\right]+\left( 10 \right)+\left( 10 \right)\left( 10 \right)+\left( 10 \right)\left( 10 \right)\left( 10 \right)+\left( 10 \right)\left( 10 \right)\left( 10 \right)\left( 10 \right)+\ldots \right)\\
D&=&C\times\left( \left[0\right]+\left( 25 \right)+\left( 25 \right)\left( 25 \right)+\left( 25 \right)\left( 25 \right)\left( 25 \right)+\left( 25 \right)\left( 25 \right)\left( 25 \right)\left( 25 \right)+\ldots \right)\\
E&=&D\times\left( \left[0\right]+\left( 50 \right)+\left( 50 \right)\left( 50 \right)+\left( 50 \right)\left( 50 \right)\left( 50 \right)+\left( 50 \right)\left( 50 \right)\left( 50 \right)\left( 50 \right)+\ldots \right)\\
&=&\left[0\right]+\left( 1 \right)+\left( 5 \right)+\left( 10 \right)+\left( 25 \right)+\left( 50 \right)+\left( 1 \right)\left( 1 \right)+\left( 1 \right)\left( 5 \right)+\left( 1 \right)\left( 10 \right)+\ldots
\endaligned</math></center>
 
Grupując teraz składniki sumy <math>E</math> w podsumy o tych samych wartościach
dostajemy wyrażenie:
 
<center><math>\begin{array} {rcl}
E&=&\big(\left( 1 \right)\big)+\big(\left( 1 \right)\left( 1 \right)\big)+\big(\left( 1 \right)\left( 1 \right)\left( 1 \right)\big)+\big(\left( 1 \right)\left( 1 \right)\left( 1 \right)\left( 1 \right)\big)\\
&&+\big(\left( 1 \right)\left( 1 \right)\left( 1 \right)\left( 1 \right)\left( 1 \right)+\left( 5 \right)\big)\\
&&+\big(\left( 1 \right)\left( 1 \right)\left( 1 \right)\left( 1 \right)\left( 1 \right)\left( 1 \right)+\left( 5 \right)\left( 1 \right)\big)+\ldots
\end{array}
</math></center>
 
Zliczając zaś tylko składniki w podsumie odpowiadającej  wartości <math>n</math> centów,
otrzymujemy liczbę sposobów, na które można rozmienić <math>n</math> centów przy użyciu monet
<math>\left( 1 \right)</math>, <math>\left( 5 \right)</math>, <math>\left( 10 \right)</math>, <math>\left( 25 \right)</math>, oraz <math>\left( 50 \right)</math>.
Pomysłem pochodzącym od Pólya, było zastąpienie
monety <math>\left( 1 \right)</math> przez zmienną <math>x</math>,
monety <math>\left( 5 \right)</math> przez <math>x\cdot x\cdot x\cdot x\cdot x=x^5</math>
i analogicznie <math>\left( 10 \right)</math> przez <math>x^{10}</math>,
<math>\left( 25 \right)</math> przez <math>x^{25}</math>,
oraz <math>\left( 50 \right)</math> przez <math>x^{50}</math>.
Uzyskujemy w ten sposób nieskończony szereg zmiennej <math>x</math>:
 
<center><math>\aligned  E\!\left( x \right)&=&\left( 1+x+x^2+x^3\ldots \right)\cdot\left( 1+x^5+x^{10}+x^{15}\ldots \right)\cdot\left( 1+x^{10}+x^{20}+x^{30}\ldots \right)\\
&&\cdot\left( 1+x^{25}+x^{50}+x^{75}\ldots \right)\cdot\left( 1+x^{50}+x^{100}+x^{150}\ldots \right)\\
&=&1+x+x^2+x^3+x^4+2x^5+2x^6+2x^7+2x^8+2x^9+4x^{10}+\ldots
\endaligned</math></center>
 
Godne zauważenia jest, że liczba różnych możliwych sposobów rozmiany <math>n</math> centów
(równa liczbie grup monet w odpowiednim nawiasie we wzorze ([[##int wzor S|Uzupelnic int wzor S|]]))
jest równa współczynnikowi stojącemu przy jednomianie <math>x^n</math>.
}}
 
'''Funkcja tworząca''' <math> G\!\left( x \right)</math> dla ciągu liczb rzeczywistych
(lub zespolonych) <math>\left( g_0,g_1,g_2,g_3,\ldots \right)</math>
to szereg funkcyjny zmiennej rzeczywistej (lub zespolonej) <math>x</math> postaci
 
<center><math> G\!\left( x \right)=\sum_{n=0}^{\infty}{g_nx^n}=g_0+g_1x+g_2x^2+g_3x^3+g_4x^4+\ldots.
</math></center>
 
Na oznaczenie współczynnika <math>n</math>-tego wyrazu szeregu <math> G\!\left( x \right)</math>
używać będziemy  oznaczenia  <math>\left[x^n\right] G\!\left( x \right)=g_n</math>.
 
{{uwaga|[Uzupelnij]||
 
Na funkcje tworzące można spojrzeć dwoiście.
Pierwszym sposobem jest potraktowanie <math> G\!\left( x \right)</math> jako szeregu liczb rzeczywistych
(lub ogólniej zespolonych).
Oczywistym pytaniem jest tu kwestia zbieżności szeregu
<math> G\!\left( x \right)=\sum_{n=0}^{\infty}{g_nx^n}</math>.
Z wykładu Analiza Matematyczna wiemy,
że szereg <math> G\!\left( x \right)</math> jest zbieżny wtedy i tylko wtedy,
gdy istnieje stała <math>M\geq0</math> ograniczająca wszystkie skończone początkowe sumy, tzn.
 
<center><math>\left\vert g_0 \right\vert+\left\vert g_1x \right\vert+\left\vert g_2x^2 \right\vert+\ldots+\left\vert g_nx^n \right\vert\leq M
</math></center>
 
zachodzi dla dowolnego <math>n\geq0</math>.
Ponadto jeśli dla pewnej liczby <math>x_0\in\mathbb{R}</math>
szereg <math> G\!\left( x_0 \right)=g_0+g_1x_0+g_2x_0^2+\ldots</math> jest zbieżny,
to i także szereg <math> G\!\left( x_1 \right)=g_0+g_1x_1+g_2x_1^2+\ldots</math>
jest zbieżny dla dowolnego <math>x_1\in\mathbb{R}</math> spełniającego <math>\left\vert x_1 \right\vert\leq\left\vert x_0 \right\vert</math>.
Możemy więc określić  ''promień zbieżności'' szeregu
jako taką liczbę <math>r\in\mathbb{R}_*\cup\left\lbrace \infty \right\rbrace=\left[0,+\infty\right]</math>, że
 
* jeśli <math>x<r</math>, to  <math> G\!\left( x \right)</math> jest zbieżny;
 
* jeśli <math>x>r</math>, to  <math> G\!\left( x \right)</math> jest rozbieżny.
 
Szereg <math> G\!\left( x \right)=g_0+g_1x+g_2x^2+\ldots</math> można więc potraktować jako funkcję
 
<center><math>G:\left( -r,r \right)\longrightarrow\mathbb{R},
</math></center>
 
o wartościach
<math> G\!\left( x \right)=\lim_{n\rightarrow\infty}{\left( g_0+g_1x+g_2x^2+\ldots+g_nx^n \right)}.
</math>
Oczywiście <math> G\!\left( 0 \right)=g_0</math>, więc dla <math>x=0</math> szereg <math> G\!\left( x \right)</math> jest zbieżny.
 
Drugim podejściem, bardziej użytecznym w praktycznych obliczeniach i przekształceniach
jest spojrzenie na szereg <math> G\!\left( x \right)=g_0+g_1x+g_2x^2+\ldots</math>
jako formę zapisu ciągu <math>\left( g_0,g_1,g_2,\ldots \right)</math>,
czyli jedynie jako ciąg symboli.
Równości pomiędzy odpowiednimi wzorami służą rozwiązaniu problemów kombinatorycznych,
tak więc traktujemy je jako równości dwu wyrażeń,
a nie jako równość dwu funkcji rzeczywistych,
pomimo że mają one uzasadnienia w języku analizy matematycznej.
 
Jak zobaczymy na wielu przykładach,
funkcje tworzące są bardzo użytecznym narzędziem
przy wyznaczaniu wartości elementów ciągu.
Jeśli bowiem <math> G\!\left( x \right)=g_0+g_1x+g_2x^2+\ldots</math>
jest funkcją tworzącą ciągu <math>\left( g_0,g_1,g_2,g_3,\ldots \right)</math>,
oraz w jakiś sposób będziemy w stanie poznać postać zwartą funkcji <math>G(x)</math>,
to rozwijając tę postać zwartą w szereg Taylora,
poznamy kolejne współczynniki tego rozwinięcia.
A współczynniki te, to właśnie kolejne wyrazy naszego ciągu.
 
Będziemy się zajmowali jedynie tymi funkcjami, dla których promień zbieżności <math>r>0</math>.
Ponadto będziemy pomijać problem zbieżności oraz wartość <math>r</math> promienia zbieżności,
skupiając się jedynie na przekształceniach wzorów.
Poniżej zebrane zostały te własności,
które często wykorzystywane są w takich przekształceniach.
}}
 
{{obserwacje|[Uzupelnij]||
 
Dla dwu funkcji tworzących <math> F\!\left( x \right)=f_0+f_1x+f_2x^2+\ldots</math>
oraz  <math> G\!\left( x \right)=g_0+g_1x+g_2x^2+\ldots</math> mamy:
 
<center><math>\aligned  F\!\left( x \right)= G\!\left( x \right)&\Leftrightarrow& f_0=g_0,\ f_1=g_1,\ f_2=g_2,\ \ldots\\
&&\\
\alpha\cdot F\!\left( x \right)+\beta\cdot G\!\left( x \right)&=& \sum_{n=0}^{\infty}{\left( \alpha\cdot f_n+\beta\cdot g_n \right)x^n}\\
&=&\left( \alpha\cdot f_0+\beta\cdot g_0 \right) + \left( \alpha\cdot f_1+\beta\cdot g_1 \right)x + \left( \alpha\cdot f_2+\beta\cdot g_2 \right)x^2 + \ldots\\
&&\\
F\!\left( x \right)\cdot G\!\left( x \right)&=&\sum_{n=0}^{\infty}\left( \sum_{k=0}^n f_k g_{n-k} \right) x^n\\
&=& f_0g_0 + \left( f_0g_1+f_1g_0 \right)x\\
&& + \left( f_0g_2+f_1g_1+f_2g_0 \right)x^2\\
&& + \left( f_0g_3+f_1g_2+f_2g_1+f_3g_0 \right)x^3+\ldots\\
\endaligned</math></center>
 
}}
 
Wyrażenie <math> F\!\left( x \right)\cdot G\!\left( x \right)</math> nazywać będziemy splotem szeregów <math> F\!\left( x \right)</math> oraz <math> G\!\left( x \right)</math>.
 
{{twierdzenie|[Uzupelnij]||
 
Funkcja tworząca postaci
 
<center><math> G\!\left( x \right)=g_0+g_1x+g_2x^2+g_3x^3+\ldots
</math></center>
 
ma odwrotną względem mnożenia (splotu),
tzn. istnieje funkcja tworząca <math> U\!\left( x \right)</math> taka,
że <math> U\!\left( x \right) G\!\left( x \right)=1</math>,
wtedy i tylko wtedy, gdy <math>g_0\neq0</math>.
}}
 
Następne własności są bardzo pomocne w dokonywanych przekształceniach
funkcji tworzących.
 
{{obserwacje|[Uzupelnij]||
 
Dla dwu funkcji tworzących <math> F\!\left( x \right)=f_0+f_1x+f_2x^2+\ldots</math>
oraz  <math> G\!\left( x \right)=g_0+g_1x+g_2x^2+\ldots</math> mamy:
 
<center><math>\aligned x^m G\!\left( x \right)&=&0+\ldots+0x^{m-1}+g_0x^m+g_1x^{m+1}+g_2x^{m+2}+\ldots\\
\frac{ G\!\left( x \right)-\sum_{i=0}^{m-1}{g_ix^i}}{x^{m}}&=&g_m+g_{m+1}x+g_{m+2}x^{2}+g_{m+3}x^{3}+g_{m+4}x^{4}+\ldots\\
G\!\left( \alpha x \right)&=&g_0+g_1\alpha x+g_2\alpha^2x^2+g_3\alpha^3x^3+g_4\alpha^4x^4+\ldots\\
G'\!\left( x \right)&=&g_1+2g_2x+3g_3x^2+4g_4x^3+5g_5x^4+\ldots\\
\int  G\!\left( x \right)dx &=& 0+g_0x+\frac{1}{2}g_1x^2+\frac{1}{3}g_2x^3+\frac{1}{4}g_3x^4+\ldots\\
\frac{ G\!\left( x \right)}{1-x}&=&g_0+\left( g_0+g_1 \right)x+\left( g_0+g_1+g_2 \right)x^2+\ldots
\endaligned</math></center>
 
}}
 
===Funkcje tworzące w zliczaniu===
 
Widzieliśmy już, że dla <math>n\in \mathbb{N}</math>
 
<center><math>\left( 1+x \right)^m
={m \choose 0}x^0 + {m \choose 1}x + {m \choose 2}x^2+\ldots+{m \choose m-1}x^{m-1}+{m \choose m}x^m
=\sum_{n=0}^\infty {m \choose n}x^n.
</math></center>
 
Przyjrzyjmy się teraz rozwinięciu w szereg funkcji <math>\left( 1+x \right)^y</math>,
gdzie <math>y\in\mathbb{R}</math> jest parametrem.
Rozwinięcie takie okaże się bardzo przydatne w rozwiązywaniu wielu przykładów.
Aby poznać ciąg odpowiadający tej funkcji wprowadźmy definicję.
 
'''Uogólniony symbol dwumianowy''' <math>{ y \choose n }</math>, gdzie <math>y\in\mathbb{R}</math> oraz <math>n\in\mathbb{N}</math> jest oznaczeniem na
 
<center><math>{ y \choose n }\ =\ \frac{y^{\underline{n}}}{n!}\ =\
\frac{y\cdot\left( y-1 \right)\cdot\ldots\cdot\left( y-\left( n-1 \right) \right)}{1\cdot2\cdot\ldots\cdot\left( n-1 \right)\cdot n}.
</math></center>
 
{{uwaga|[Uzupelnij]||
 
Oczywiście dla <math>y\in\mathbb{N}</math> spełniającego dodatkowo <math>y\geq n</math>,
uogólniony symbol dwumianowy <math>{ y \choose n }</math>
jest liczbą <math>n</math>-elementowych podzbiorów zbioru <math>y</math>-elementowego.
}}
 
{{twierdzenie|[Uzupelnij]||
 
Dla liczby rzeczywistej <math>y</math> oraz liczby naturalnej <math>n</math> zachodzi
 
<center><math>\left( 1+x \right)^y=\sum_{n=0}^{\infty}{ y \choose n }x^n.
</math></center>
 
}}
 
{{wniosek|[Uzupelnij]||
 
Dla liczby naturalnej <math>m</math> zachodzi
 
<center><math>\frac{1}{\left( 1-x \right)^{m+1}}=\sum_{n=0}^{\infty}{ m+n \choose n }x^n.
</math></center>
 
}}
 
{{dowod|[Uzupelnij]||
 
Dowód zostawiony jest jako ćwiczenie '''[ex][ex newton for integer]'''.
}}
 
{{przyklad|[Uzupelnij]||
 
Policzmy sumę
 
<center><math>\sum_{k=0}^nk^2=1+4+9+\ldots+n^2.
</math></center>
 
Zacznijmy od znalezienia zwartej postaci funkcji tworzącej
<math> G\!\left( x \right)=\sum_{n=0}^{\infty}n^2x^n</math>.
Korzystając z Wniosku [[##con newton for integer|Uzupelnic con newton for integer|]] otrzymujemy:
 
<center><math>\aligned \frac{1}{1-x}&=&\sum_{n=0}^{\infty}{n \choose n}x^n=\sum_{n=0}^{\infty}x^n,\\
\frac{1}{\left( 1-x \right)^2}&=&\sum_{n=0}^{\infty}{n+1 \choose n
}x^n\ =\ \sum_{n=0}^{\infty}nx^n+\sum_{n=0}^{\infty}x^n.
\endaligned</math></center>
 
Po przekształceniu równości ([[##eq 11|Uzupelnic eq 11|]]) uzyskuje się
 
<center><math>
\sum_{n=0}^{\infty}nx^n= \frac{1}{\left( 1-x \right)^2}
-\frac{1}{1-x}.
</math></center>
 
Powołując się ponownie na Wniosek [[##con newton for integer|Uzupelnic con newton for integer|]] otrzymujemy
 
<center><math>\frac{1}{\left( 1-x \right)^3}
=\sum_{n=0}^{\infty}{ n+2 \choose n}x^n
=\frac{1}{2}\sum_{n=0}^{\infty}n^2x^n+\frac{3}{2}\sum_{n=0}^{\infty}nx^n+\sum_{n=0}^{\infty}x^n,
</math></center>
 
co w połączeniu z równościami ([[##eq 11|Uzupelnic eq 11|]]) oraz ([[##eq 122|Uzupelnic eq 122|]])
daje zwartą postać funkcji tworzącej <math> G\!\left( x \right)</math> dla ciągu <math>1,4,9,\ldots,n^2,\ldots</math>:
 
<center><math> G\!\left( x \right)=\sum_{n=0}^{\infty}n^2x^n
=\frac{2}{\left( 1-x \right)^3}-\frac{3}{\left( 1-x \right)^2}+\frac{1}{1-x}.
</math></center>
 
Naszym zadaniem było jednakże policzenie funkcji tworzącej <math>H(x)</math> dla ciągu
<math>1,1+4,1+4+9,\ldots,1+4+9+\ldots+n^2,\ldots</math>,
tzn. ciągu sum początkowych wyrazów ciągu <math>1,4,9,\ldots,n^2,\ldots</math>.
Aby uzyskać <math> H\!\left( x \right)</math> wystarczy więc skorzystać ze wzoru ([[##eq 1 przez 1-x|Uzupelnic eq 1 przez 1-x|]])
i podzielić <math> G\!\left( x \right)</math> przez <math>1-x</math>.
Tak więc poszukiwanym rozwiązaniem są współczynniki funkcji tworzącej
 
<center><math> H\!\left( x \right)=\frac{ G\!\left( x \right)}{1-x}
=\frac{2}{\left( 1-x \right)^4}-\frac{3}{\left( 1-x \right)^3}+\frac{1}{\left( 1-x \right)^2}.
</math></center>
 
Korzystając po raz kolejny z Wniosku [[##con newton for integer|Uzupelnic con newton for integer|]] otrzymujemy
 
<center><math>\aligned  H\!\left( x \right)
&=&2\sum_{n=0}^{\infty}{n+3 \choose n}x^n-3\sum_{n=0}^{\infty}{n+2 \choose n}x^n+\sum_{n=0}^{\infty}{n+1 \choose n}x^n\\
&=&\sum_{n=0}^{\infty}\left( \frac{1}{3}n^3+\frac{1}{2}n^2+\frac{1}{6}n \right)x^n.
\endaligned</math></center>
 
W konsekwencji zachodzi równość
 
<center><math>\sum_{k=1}^nk^2=\left[x^n\right] H\!\left( x \right)=\frac{2n^3+3n+n}{6}.
</math></center>
 
}}
 
{{przyklad|[Uzupelnij]||
 
Wracamy  do przykładu z monetami.
Występowały tam funkcje tworzące postaci
 
<center><math> A_k\!\left( x \right) = 1+x^k+x^{2k}+x^{3k}+\ldots,
</math></center>
 
dla <math>k=1,5,10,25</math> i <math>50</math>.
Z równości ([[##eq 1 przez 1-x|Uzupelnic eq 1 przez 1-x|]]) wiemy, że
 
<center><math>1+x^k+x^{2k}+x^{3k}+\ldots, =\frac{1}{1-x^k}
</math></center>
 
tak więc:
 
<center><math>\aligned  A\!\left( x \right)=  A_1\!\left( x \right)&=& \frac{1}{1-x},\\
B\!\left( x \right)=  A\!\left( x \right)\cdot  A_5\!\left( x \right) &=&\frac{ A\!\left( x \right)}{1-x^5},\\
C\!\left( x \right)=  B\!\left( x \right)\cdot  A_{10}\!\left( x \right) &=&\frac{ B\!\left( x \right)}{1-x^{10}},\\
D\!\left( x \right)=  C\!\left( x \right)\cdot  A_{25}\!\left( x \right) &=&\frac{ C\!\left( x \right)}{1-x^{25}},\\
E\!\left( x \right)=  D\!\left( x \right)\cdot  A_{50}\!\left( x \right) &=&\frac{ D\!\left( x \right)}{1-x^{50}},
\endaligned</math></center>
 
skąd natychmiast:
 
<center><math>\aligned  A\!\left( x \right)&=&1+x A\!\left( x \right),\\
B\!\left( x \right)&=& A\!\left( x \right)+x^5 B\!\left( x \right),\\
C\!\left( x \right)&=& B\!\left( x \right)+x^{10} C\!\left( x \right),\\
C\!\left( x \right)&=& D\!\left( x \right)+x^{25} C\!\left( x \right),\\
D\!\left( x \right)&=& E\!\left( x \right)+x^{50} D\!\left( x \right).
\endaligned</math></center>
 
Równości te dają zależności między współczynnikami:
 
<center><math>a_n=1,\quad b_n=a_n+b_{n-5},\quad c_n=b_n+c_{n-10},\quad
d_n=c_n+d_{n-25},\quad e_n=d_n+e_{n-50}.
</math></center>
 
Wykorzystując te zależności rekurencyjne możemy wypełnić następującą tabelę:
 
{-2cm}
 
{| border=1
|+ <span style="font-variant:small-caps">Uzupelnij tytul</span>
|-
| <math>n</math> || 0 || 5 || 10 || 15 || 2 || 25 || 30 || 35 || 40 || 45 || 50 || 55 || 60 || 65 || 70 || 75 || 80 || 85 || 90 || 95 || 100
|-
| <math>a_n</math> || 1 || 1 || 1 || 1 || 1 || 1 || 1 || 1 || 1 || 1 || 1 || 1 || 1 || 1 || 1 || 1 || 1 || 1 || 1 || 1 || 1
|-
| <math>b_n</math> || 1 || 2 || 3 || 4 || 5 || 6 || 7 || 8 || 9 || 10 || 11 || 12 || 13 || 14 || 15 || 16 || 17 || 18 || 19 || 20 || 21
|-
| <math>c_n</math> || 1 || 2 || 4 || 6 || 9 || 12 || 16 || 10 || 25 || 30 || 36 || 42 || 49 || 56 || 64 || 72 || 81 ||  || 100 ||  || 121
|-
| <math>d_n</math> || 1 ||  ||  ||  ||  || 13 ||    ||    ||    ||    || 49 ||    ||    ||    ||  || 121 ||    ||  ||    ||  || 242
|-
| <math>e_n</math> || 1 ||  ||  ||  ||  ||    ||    ||    ||    ||    || 50 ||    ||    ||    ||  ||    ||    ||  ||    ||  || 292
|}
 
Pół dolara można rozmienić na <math>50</math> sposobów.
Z kolei rozmieniać jednego dolara można na aż <math>292</math> sposoby.
Do problemu tego wrócimy jeszcze w następnym wykładzie.
}}
 
===Funkcje tworzące w rozwiązywaniu zależności rekurencyjnych.===
 
{{przyklad|[Uzupelnij]||
 
Rozważmy ciąg Fibonacci'ego, tzn. ciąg <math>\left( f_0,f_1,f_2,f_3,\ldots \right)</math>
zdefiniowany w następujący sposób:
 
<center><math>\aligned f_0&=&0,\\
f_1&=&1,\\
f_n&=&f_{n-1}+f_{n-2}\quad\textrm{dla}\ n\geq2.
\endaligned</math></center>
 
Znamy już postać zwartą jego wyrazów.
Tym razem zobaczymy jak można ją otrzymać używając funkcji tworzących.
Zależności rekurencyjne dla <math>f_n</math> przekładają się natychmiast na
następujące równanie, jakie musi spełniać funkcja tworząca <math> F\!\left( x \right)</math>
dla ciągu Fibonacci'ego
 
<center><math> F\!\left( x \right)
=\sum_{n=0}^{\infty}f_nx^n
=x+\sum_{n=2}^{\infty}\left( f_{n-1}+f_{n-2} \right)x^n=1+x+x F\!\left( x \right)+x^2 F\!\left( x \right).
</math></center>
 
Przekształcając powyższe równanie otrzymujemy:
 
<center><math>
F\!\left( x \right)=\frac{x}{1-x-x^2}.
</math></center>
 
Celem, który chcemy osiągnąć to wykorzystanie funkcji <math>\frac{x}{1-x-x^2}</math>
do przedstawienia współczynników <math>f_n</math> w postaci zwartej.
Pierwszym krokiem będzie rozłożenie ułamka w równaniu ([[##eq fib|Uzupelnic eq fib|]])
na sumę ułamków o mianownikach będących funkcjami liniowymi
 
<center><math> F\!\left( x \right)=\frac{x}{1-x-x^2}
=\frac{x}{\left( 1-\varphi x \right)\left( 1-\overline{\varphi} x \right)}
=\frac{1}{\sqrt{5}}\left( \frac{1}{\left( 1-\varphi x \right)}-\frac{1}{\left( 1-\overline{\varphi} x \right)} \right),
</math></center>
 
gdzie <math>\varphi=\frac{1+\sqrt{5}}{2}</math> jest złotą liczbą
oraz <math>\overline{\varphi}=\frac{1-\sqrt{5}}{2}</math> liczbą do niej sprzężoną.
Korzystając z równania ([[##eq 1 przez 1-x|Uzupelnic eq 1 przez 1-x|]]) otrzymujemy teraz
 
<center><math> F\!\left( x \right)
=\frac{1}{\sqrt{5}}\left( \sum_{n=1}^{\infty}{\varphi^nx^n}-\sum_{n=1}^{\infty}{\overline{\varphi}^nx^n} \right)
=\frac{1}{\sqrt{5}}\sum_{n=1}^{\infty}{\left( \varphi^n-\overline{\varphi}^n \right)x^n}.
</math></center>
 
Tak więc dostajemy szybko znaną nam już postać zwartą
<math>f_n=\frac{1}{\sqrt{5}}\left( \varphi^n-\overline{\varphi}^n \right)</math>.
}}
 
Podczas rozwiązywania przykładu związanego z liczbami Fibonacci'ego
natrafiliśmy na problem polegający na przedstawieniu w postaci szeregu wyrażenia
<math>\frac{x}{1-x-x^2}</math>.
Przyjrzymy się dokładniej tego typu wyrażeniom.
 
'''Stopień wielomianu''' <math>{\sf deg}\  P\!\left( x \right)=n</math>,
jeśli <math> P\!\left( x \right)=p_0+p_1x+\ldots+p_nx^n</math>.
 
'''Funkcja wymierna''' <math> R\!\left( x \right)</math> to funkcja postaci <math>\frac{ P\!\left( x \right)}{ Q\!\left( x \right)}</math>, gdzie <math> P\!\left( x \right)</math> oraz <math> Q\!\left( x \right)\neq0</math> są wielomianami skończonego stopnia.
 
{{obserwacje|[Uzupelnij]||
 
Niech <math> A\!\left( x \right)</math> oraz <math> B\!\left( x \right)</math> będą wielomianami
<math>{\sf deg}\  A\!\left( x \right)\geq {\sf deg}\  B\!\left( x \right)</math>.
Wtedy istnieją wielomiany <math> Q\!\left( x \right)</math> oraz <math> R\!\left( x \right)</math> takie, że
 
<center><math> A\!\left( x \right)= Q\!\left( x \right) B\!\left( x \right)+ R\!\left( x \right),
</math></center>
 
gdzie <math>{\sf deg}\  R\!\left( x \right)<{\sf deg}\  A\!\left( x \right)={\sf deg}\  Q\!\left( x \right)+{\sf deg}\  B\!\left( x \right)</math>.
}}
 
{{przyklad|[Uzupelnij]||
 
Niech
 
<center><math> A\!\left( x \right)=3x^5+5x^4+2x^3+x^2+2\quad\textrm{oraz}\quad B\!\left( x \right)=x^3+2x^2-1.
</math></center>
 
Wtedy wielomiany
 
<center><math> Q\!\left( x \right)=3x^2-x+3\quad\textrm{oraz}\quad R\!\left( x \right)=x+2
</math></center>
 
spełniają
 
<center><math>\aligned  A\!\left( x \right)&=&3x^5+5x^4+2x^3+x^2+2\\
&=&\left( 3x^2-x+3 \right)\cdot\left( x^3+2x^2-1 \right)+x+2\\
&=& Q\!\left( x \right) B\!\left( x \right)+ R\!\left( x \right).
\endaligned</math></center>
 
Ponadto <math>{\sf deg}\  A\!\left( x \right)=5=2+3={\sf deg}\  Q\!\left( x \right)+{\sf deg}\  B\!\left( x \right)</math>.
}}
 
{{wniosek|[Uzupelnij]||
 
Niech <math> P\!\left( x \right)</math> oraz <math> Q\!\left( x \right)</math> będą wielomianami takimi,
że <math>{\sf deg}\  P\!\left( x \right)\geq{\sf deg}\  Q\!\left( x \right)</math>.
Wtedy funkcję wymierną
<math> R\!\left( x \right)= P\!\left( x \right)/ Q\!\left( x \right),
</math>
można przedstawić w postaci
 
<center><math> R\!\left( x \right)=\frac{ P\!\left( x \right)}{ Q\!\left( x \right)}= A\!\left( x \right)+\frac{ B\!\left( x \right)}{ Q\!\left( x \right)},
</math></center>
 
dla pewnych wielomianów <math> A\!\left( x \right)</math> oraz <math> B\!\left( x \right)</math>
spełniających <math>{\sf deg}\  B\!\left( x \right)<{\sf deg}\  Q\!\left( x \right)</math>.
}}
 
Będziemy więc skupiali się jedynie nad takimi funkcjami wymiernymi <math> R\!\left( x \right)= P\!\left( x \right)/ Q\!\left( x \right),
</math> dla których <math>{\sf deg}\  P\!\left( x \right)<{\sf deg}\  Q\!\left( x \right)</math>.
 
{{twierdzenie|[Uzupelnij]||
 
Niech <math> P\!\left( x \right)</math> oraz <math> Q\!\left( x \right)</math> będą wielomianami takimi, że
 
* <math>{\sf deg}\  P\!\left( x \right)<{\sf deg}\  Q\!\left( x \right)</math>,
 
* <math> Q\!\left( x \right)= S\!\left( x \right) T\!\left( x \right)</math>,
gdzie oba wielomiany <math> S\!\left( x \right), T\!\left( x \right)</math> są stopnia co najmniej <math>2</math>,
 
* <math>q_0\neq0</math>.
 
Wtedy istnieją wielomiany
<math> A\!\left( x \right)</math> oraz <math> B\!\left( x \right)</math> takie, że
<math>{\sf deg}\  A\!\left( x \right)<{\sf deg}\  S\!\left( x \right)</math> i
<math>{\sf deg}\  B\!\left( x \right)<{\sf deg}\  T\!\left( x \right)</math>
oraz
 
<center><math>\frac{ P\!\left( x \right)}{ Q\!\left( x \right)}
=\frac{ A\!\left( x \right)}{ S\!\left( x \right)}+\frac{ B\!\left( x \right)}{ T\!\left( x \right)}.
</math></center>
 
}}
 
{{uwaga|[Uzupelnij]||
 
Twierdzenie [[##thm PQ <nowiki>=</nowiki> AS BT|Uzupelnic thm PQ <nowiki>=</nowiki> AS BT|]] pozwala na rozbijanie skomplikowanych funkcji wymiernych na sumę prostszych.
}}
 
{{dowod|[Uzupelnij]||
[Metoda rozwijania funkcji wymiernej w szereg.]
Rozważmy funkcję wymierną w postaci
 
<center><math> R\!\left( x \right)=\frac{ P\!\left( x \right)}{ Q\!\left( x \right)},
</math></center>
 
gdzie <math>{\sf deg}\  P\!\left( x \right)<{\sf deg}\  Q\!\left( x \right)</math>, oraz <math>q_0\neq0</math>.
Załóżmy ponadto, że wielomian <math> Q\!\left( x \right)</math> rozkłada się na
następujący iloczyn czynników liniowych
 
<center><math> Q\!\left( x \right)
=q_0\left( 1-\rho_1x \right)^{m_1}\cdot\left( 1-\rho_2x \right)^{m_2}\cdot\ldots\cdot\left( 1-\rho_kx \right)^{m_k}.
</math></center>
 
Warto wspomnieć, że dalecy nie każdy wielomian ma taki rozkład.
Na przykład <math>1+x^2</math> jest nierozkładalny i nieliniowy.
Wykorzystując parokrotnie Twierdzenie [[##thm PQ <nowiki>=</nowiki> AS BT|Uzupelnic thm PQ <nowiki>=</nowiki> AS BT|]]
otrzymujemy wielomiany <math> P_1\!\left( x \right),\ldots, P_k\!\left( x \right)</math> takie, że
 
<center><math> R\!\left( x \right)
=\frac{ P\!\left( x \right)}{ Q\!\left( x \right)}=\frac{ P_1\!\left( x \right)}{\left( 1-\rho_1x \right)^{m_1}}+\frac{ P_2\!\left( x \right)}{\left( 1-\rho_2x \right)^{m_2}}+\ldots+\frac{ P_k\!\left( x \right)}{\left( 1-\rho_kx \right)^{m_k}},
</math></center>
 
gdzie <math>{\sf deg}\  P_i\!\left( x \right)<m_i</math>.
Na mocy Obserwacji [[##obs div|Uzupelnic obs div|]] możemy sprowadzić wielomian <math> P_i\!\left( x \right)</math> do
 
<center><math>\aligned  P_i\!\left( x \right)&=& P_i^1\!\left( x \right)\left( 1-\rho_ix \right)+\gamma_{m_i}\\
&=& P_i^2\!\left( x \right)\left( 1-\rho_ix \right)^2+\gamma_{m_i-1}\left( 1-\rho_ix \right)+\gamma_{m_i}\\
&\vdots&\\
&=&\gamma_1\left( 1-\rho_ix \right)^{m_i-1}+\ldots+\gamma_{m_i-1}\left( 1-\rho_ix \right)+\gamma_{m_i},
\endaligned</math></center>
 
gdzie <math>m_i\geq{\sf deg}\  P_i\!\left( x \right)>{\sf deg}\  P_i^1\!\left( x \right)>{\sf deg}\  P_i^2\!\left( x \right)>\ldots</math>.
W konsekwencji otrzymamy
 
<center><math> R\!\left( x \right)\ =\ \sum_{i=1}^k{\left( \frac{\gamma_{i,1}}{1-\rho_ix}+\frac{\gamma_{i,2}}{\left( 1-\rho_ix \right)^2}+\ldots+\frac{\gamma_{i,m_i}}{\left( 1-\rho_ix \right)^{m_i}} \right)}.
</math></center>
 
Mnożąc teraz obie strony przez
 
<center><math> Q\!\left( x \right)/q_0=\left( 1-\rho_1x \right)^{m_1}\cdot\left( 1-\rho_2x \right)^{m_2}\cdot\ldots\cdot\left( 1-\rho_kx \right)^{m_k}
</math></center>
 
i porównując współczynniki przy odpowiadających potęgach <math>x^i</math>
uzyskujemy pewien układ równań, rozwiązanie którego da nam
poszukiwane współczynniki <math>\gamma_{i,j}</math>.
Z drugiej strony, z wniosku [[##con newton for integer|Uzupelnic con newton for integer|]] wynika, że
 
<center><math>\frac{1}{\left( 1-\rho x \right)^{m+1}}
=\sum_{n=1}^{\infty}{ { m+n \choose m } \rho^n x^n}
</math></center>
 
i w konsekwencji:
 
<center><math>
[x^n] R\!\left( x \right)\ =\ \sum_{i=1}^k{\left( \gamma_{i,1}+
\gamma_{i,2}{n+1\choose 1}+
\ldots+
\gamma_{i,m_i}{n+m_i-1\choose m_i}
\right)}\rho_i^n.
</math></center>
 
}}
 
{{przyklad|[Uzupelnij]||
 
Opisaną wyżej metodę ogólną zilustrujemy na przykładzie funkcji
 
<center><math> R\!\left( x \right)=\frac{x^2}{1-x-x^2+x^3}.
</math></center>
 
Wielomian <math>1-x-x^2+x^3</math>
ma jeden podwójny pierwiastek  <math>x=1</math>
oraz jeden pojedynczy <math>x=-1</math>.
Poznana metoda rozwijania funkcji wymiernej w szereg daje więc
 
<center><math> R\!\left( x \right)
=\frac{x^2}{\left( 1-x \right)^2\cdot\left( 1+x \right)}=\frac{\alpha}{1-x}+\frac{\beta}{\left( 1-x \right)^2}+\frac{\gamma}{1+x}.
</math></center>
 
Mnożąc obie strony przez <math>\left( 1-x \right)^2\cdot\left( 1+x \right)</math> otrzymujemy:
 
<center><math>x^2=\alpha\left( 1-x^2 \right)+\beta\left( 1+x \right)+\gamma\left( 1-2x+x^2 \right).
</math></center>
 
Dwa wielomiany są równe,
gdy współczynniki przy odpowiadających potęgach są sobie równe.
Wartości <math>\alpha, \beta, \gamma</math> można więc wyliczyć z układu równań
 
<center><math>\left\lbrace\begin{array} {rrrcl}
\alpha & +\ \beta &  +\ \gamma & = & 0\\
\alpha &          & -\ 2\gamma & = & 0\\
& -\ \beta &  +\ \gamma & = & 1.
\end{array} \right.
</math></center>
 
Rozwiązaniem powyższego układu są wartości
<math>\alpha=-\frac{1}{4},\
\beta=\frac{1}{2},\
\gamma=-\frac{1}{4}.
</math>
W konsekwencji otrzymujemy szereg
 
<center><math>\aligned  R\!\left( x \right)&=&\sum_{n=0}^{\infty}\left( -\frac{1}{4}+\frac{1}{2}\left( n+1 \right) - \frac{1}{4}\left( -1 \right)^n \right)x^n\\
&=&x^2+x^3+2x^4+2x^5+3x^6+3x^7+4x^8+\ldots.
\endaligned</math></center>
 
}}
 
Jeżeli mianownik <math> Q\!\left( x \right)</math>
funkcji wymiernej <math> R\!\left( x \right)=\frac{ P\!\left( x \right)}{ Q\!\left( x \right)}</math>
posiada jedynie pierwiastki jednokrotne,
to następne twierdzenie znacznie przyspiesza rozkład  <math> R\!\left( x \right)</math> na sumę.
 
{{twierdzenie|[Uzupelnij]||
 
Jeśli <math> R\!\left( x \right)= P\!\left( x \right)/ Q\!\left( x \right)</math>,
gdzie <math> Q\!\left( x \right)=q_0\cdot\left( 1-\rho_1x \right)\cdot\ldots\cdot\left( 1-\rho_1x \right)</math>
i liczby <math>\rho_1,\ldots,\rho_l</math> są parami różne,
to w przypadku gdy <math> P\!\left( x \right)</math> jest wielomianem stopnia mniejszego niż <math>l</math>, zachodzi
 
<center><math>\left[x^n\right] R\!\left( x \right)
=a_1\rho_1^n+\ldots+a_l\rho_l^n,
\quad\textrm{dla}\  a_k=\frac{-\rho_k\cdot P\!\left( 1/\rho_k \right)}{ Q'\!\left( 1/\rho_k \right)}.
</math></center>
 
}}
 
{{przyklad|[Uzupelnij]||
 
Mianownik <math> Q\!\left( x \right)</math> funkcji wymiernej
 
<center><math> R\!\left( x \right)=\frac{ P\!\left( x \right)}{ Q\!\left( x \right)}=\frac{2x}{1-5x-2x^2+24x^3}.
</math></center>
 
ma trzy różne pierwiastki i można <math> R\!\left( x \right)</math> przedstawić jako
 
<center><math> R\!\left( x \right)=\frac{2x}{\left( 1+2x \right)\left( 1-3x \right)\left( 1-4x \right)}.
</math></center>
 
Na mocy twierdzenia [[##thm wymierne|Uzupelnic thm wymierne|]] otrzymujemy więc, że
 
<center><math>\left[x^n\right] R\!\left( x \right)=-\frac{2}{15}\left( -2 \right)^n-\frac{6}{5}3^n+\frac{4}{3}4^n.
</math></center>
 
}}
 
Jak widzieliśmy na przykładzie ciągu Fibonacci'ego,
funkcje tworzące mogą być bardzo pomocne przy szukaniu postaci zwartej
pewnych ciągów zadanych rekurencyjnie.
 
'''Jednorodne, liniowe równanie rekurencyjne''' to równanie postaci
 
<center><math>\left\lbrace
\begin{array} {rcl}
r_0&=&c_0,\\
&\cdots&\\
r_{k-1}&=&c_{k-1},\\
r_n&=&a_1r_{n-1}+a_2r_{n-2}+\ldots+a_kr_{n-k}\quad\textrm{dla}\ n\geq k,
\end{array}
\right.
</math></center>
 
gdzie <math>c_0,\ldots,c_{k-1},a_1,\ldots,a_k</math> są liczbami rzeczywistymi
(niezależnymi od parametru rekurencyjnego <math>n</math>).
 
Rozważmy najpierw przypadek, gdy <math>k=2</math>, tzn. równanie postaci
 
<center><math>
\left\lbrace
\begin{array} {rcl}
r_0&=&c_0,\\
r_1&=&c_1,\\
r_n&=&a_1r_{n-1}+a_2r_{n-2}\quad\textrm{dla}\ n\geq 2.
\end{array}
\right.
</math></center>
 
Przykładem takiego równania była zależność opisująca ciąg Fibonacci'ego.
Zastosowanie ostatniej równości z ([[##eq rec 2|Uzupelnic eq rec 2|]])
do funkcji tworzącej ciągu <math>\left( r_0,r_1,r_2,\ldots \right)</math> daje:
 
<center><math>\aligned  R\!\left( x \right)&=&r_0+r_1x+r_2x^2+r_3x^3+\ldots+r_nx^n+\ldots\\
&=&c_0+c_1x+\left( a_1r_1+a_2r_0 \right)x^2+\ldots+\left( a_1r_{n-1}+a_2r_{n-2} \right)x^n+\ldots\\
&=&c_0+\left( c_1-a_1c_0 \right)x+a_1x R\!\left( x \right)+a_2x^2 R\!\left( x \right),
\endaligned</math></center>
 
tak więc
 
<center><math> R\!\left( x \right)\ =\ \frac{c_0+\left( c_1-a_1c_0 \right)x}{1-a_1x-a_2x^2}
</math></center>
 
Dla funkcji <math> A\!\left( x \right)=1-a_1x-a_2x^2=\left( 1-\rho_1x \right)\left( 1-\rho_2x \right)</math>
mogą zajść trzy przypadki:
 
* <math>\rho_1 \neq \rho_2</math> są różnymi liczbami rzeczywistymi. Wtedy
 
<center><math>r_n\ =\ \alpha\rho_1^n+\beta\rho_2^n,
</math></center>
 
gdzie <math>\alpha</math> oraz <math>\beta</math> są liczbami rzeczywistymi.
 
* <math>\rho_1 = \rho_2</math>.  Wtedy
 
<center><math>r_n\ =\ \left( \alpha n+\beta \right)\rho_1^n,
</math></center>
 
gdzie <math>\alpha</math> oraz <math>\beta</math> są liczbami rzeczywistymi.
 
*  <math>\bigtriangledown</math> 
Wartości <math>\rho_1</math> oraz <math>\rho_2</math> są różnymi liczbami zespolonymi.
W tym wypadku całe rozumowanie przeprowadzone wcześniej dla liczb rzeczywistych
pozostaje w mocy, tyle że dokonywane jest teraz na liczbach zespolonych.
Dostajemy więc
 
<center><math>r_n\ =\ \alpha\rho_1^n+\beta\rho_2^n.
</math></center>
 
gdzie <math>\alpha</math> oraz <math>\beta</math> są pewnymi liczbami zespolonymi.
Przypadek pierwszy jest więc szczególną sytuacją obecnego przypadku.
Może być jednak rozważany bez znajomości liczb zespolonych.
{<math>\bigtriangleup</math>} 
 
Wracamy teraz do ogólnego, jednorodnego liniowego równania rekurencyjnego.
Analogicznie do przypadku, gdy <math>k=2</math>, otrzymujemy że
 
<center><math> R\!\left( x \right)\ =\ \frac{ P\!\left( x \right)}{1-a_1x-a_2x^2-\ldots-a_kx^k},
</math></center>
 
gdzie <math> P\!\left( x \right)</math> jest wielomianem co najwyżej stopnia <math>k-1</math>,
zależnym od wartości <math>c_0,\ldots,c_{k-1},a_1,\ldots,a_k</math>.
Korzystając z ogólnej metody rozwijania funkcji wymiernej w szereg,
możemy odzyskać wyrazy ciągu <math>r_n</math>,
jako współczynniki <math>[x^n] R\!\left( x \right)</math> zgodnie z równaniem ([[##eq R(x)|Uzupelnic eq R(x)|]]).
 
{{przyklad|[Uzupelnij]||
 
Równanie rekurencyjne ma następującą postać
 
<center><math>\left\lbrace
\begin{array} {rcl}
r_0&=&0,\\
r_1&=&0,\\
r_2&=&1,\\
r_n&=&r_{n-1}+r_{n-2}-r_{n-3}\quad\textrm{dla}\ n\geq 3.
\end{array}
\right.
</math></center>
 
Ostatnia zależność prowadzi do  funkcji tworzącej <math> R\!\left( x \right)</math> spełniającej
 
<center><math> R\!\left( x \right)=x^2 + x R\!\left( x \right) + x^2 R\!\left( x \right) - x^3 R\!\left( x \right).
</math></center>
 
Po dokonaniu prostego wyliczenia dostajemy: 
 
<center><math> R\!\left( x \right)=\frac{x^2}{1-x-x^2+x^3}.
</math></center>
 
W przykładzie omawianym przy okazji metody rozwijania funkcji wymiernej w szereg,
wyliczyliśmy współczynniki <math>[x^n] R\!\left( x \right)</math>, a zatem mamy:
 
<center><math>r_n=-\frac{1}{4}+\frac{1}{2}\left( n+1 \right) - \frac{1}{4}\left( -1 \right)^n\quad\textrm{dla dowolnego}\ n=0,1,2,3,\ldots.
</math></center>


}}
</div>
</div>
<div class="noprt" align="right"><a href="index.xml">&laquo;
previous</a> | <a href="zadanie_2.xml">next &raquo;</a></div>
</div>
</div>

Aktualna wersja na dzień 08:57, 28 sie 2023

When working with character arrays, always reserve enough array elements to hold the string AND its null-terminating character (\0).

True

False

Testy

When working with character arrays, always reserve enough array elements to hold the string AND its null-terminating character (\0).

True

False

When working with character arrays, always reserve enough array elements to hold the string AND its null-terminating character (\0).

True

False

In C++, 14 % 4 =

1

2

3

4

In C++, 14 % 4 =

1

2

3

4

Variables that are declared, but not initialized, contain

blank spaces

zeros

"garbage" values

nothing - they are empty

Variables that are declared, but not initialized, contain

blank spaces

zeros

"garbage" values

nothing - they are empty


Dlaczego suma ∑i=110i jest źle wyświetlana w wykładniku potęgi?

z∑i=110i



Zadanie 1.

<script type="text/javascript" src="common.js"></script> <script type="text/javascript" src="libot_drag.js"></script>

<img alt="Ikona obiektu Pytanie"

class="iDevice_icon" src="icon_question.gif" /> Zadanie 1,

Liczba Parser nie mógł rozpoznać (błąd składni): {\displaystyle <msqrt><mrow><mn>3</mn> <mo class="MathClass-bin">+</mo> <mn>2</mn><msqrt><mrow> <mn>2</mn></mrow></msqrt></mrow></msqrt> <mo class="MathClass-bin">&minus;</mo><msqrt><mrow><mn>3</mn> <mo class="MathClass-bin">&minus;</mo> <mn>2</mn><msqrt><mrow> <mn>2</mn></mrow></msqrt></mrow></msqrt>}   

<tbody> </tbody>
<input type="checkbox" name="option9" id="ia0b9"

value="vTrue"

onclick="document.getElementById('sa0b9').style.display = this.checked ? 'block' : 'none';" />		 jest dodatnia
<input type="checkbox" name="option9" id="ia1b9"

value="vTrue"

onclick="document.getElementById('sa1b9').style.display = this.checked ? 'block' : 'none';" />		 jest wymierna
<input type="checkbox" name="option9" id="ia2b9"

value="vFalse"

onclick="document.getElementById('sa2b9').style.display = this.checked ? 'block' : 'none';" />		 nale»y do trójkowego zbioru Cantora.
<a href="index.xml">« previous</a> | <a href="zadanie_2.xml">next »</a>
Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=Test_Arka&oldid=79852”