Matematyka dyskretna 1/Wykład 7: Funkcje tworzące: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
m Zastępowanie tekstu – „\displaystyle ” na „”
Nie podano opisu zmian
 
(Nie pokazano 8 pośrednich wersji utworzonych przez tego samego użytkownika)
Linia 32: Linia 32:
<center><math>\begin{align} A_{10} &= [0]+(10)+(10)(10)+(10)(10)(10)+(10)(10)(10)(10)+\ldots\\
<center><math>\begin{align} A_{10} &= [0]+(10)+(10)(10)+(10)(10)(10)+(10)(10)(10)(10)+\ldots\\
A_{25} &= [0]+(25)+(25)(25)+(25)(25)(25)+(25)(25)(25)(25)+\ldots\\
A_{25} &= [0]+(25)+(25)(25)+(25)(25)(25)+(25)(25)(25)(25)+\ldots\\
A_{50} &= [0]+(50)+(50)(50)+(50)(50)(50)+(50)(50)(50)(50)+\ldots.
A_{50} &= [0]+(50)+(50)(50)+(50)(50)(50)+(50)(50)(50)(50)+\ldots
\end{align}</math></center>
\end{align}</math></center>


Linia 61: Linia 61:




<center><math>\begin{align}{E}(x)&=\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)\\
<center><math>\begin{align}{E}(x)&=\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)\\
&\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
&=1+x+x^2+x^3+x^4+2x^5+2x^6+2x^7+2x^8+2x^9+4x^{10}+\ldots
\end{align}</math></center>
\end{align}</math></center>
Linia 72: Linia 72:




<center><math>{G}(x)=\sum_{n=0}^{\infty}{g_nx^n}=g_0+g_1x+g_2x^2+g_3x^3+g_4x^4+\ldots.
<center><math>{G}(x)=\sum_{n=0}^{\infty}{g_nx^n}=g_0+g_1x+g_2x^2+g_3x^3+g_4x^4+\ldots</math></center>
</math></center>




Linia 92: Linia 91:




<center><math>G:\left(-r,r\right)\longrightarrow\mathbb{R},
<center><math>G:\left(-r,r\right)\longrightarrow\mathbb{R}</math>,</center>
</math></center>




o wartościach <math>{G}(x)=\lim_{n\rightarrow\infty}{\left(g_0+g_1x+g_2x^2+\ldots+g_nx^n\right)}.</math> Oczywiście <math>{G}(0)=g_0</math>, więc dla <math>x=0</math> szereg <math>{G}(x)</math> jest zbieżny.
o wartościach <math>{G}(x)=\lim_{n\rightarrow\infty}{\left(g_0+g_1x+g_2x^2+\ldots+g_nx^n\right)}</math>. Oczywiście <math>{G}(0)=g_0</math>, więc dla <math>x=0</math> szereg <math>{G}(x)</math> jest zbieżny.


Drugim podejściem, bardziej użytecznym w praktycznych obliczeniach i przekształceniach jest spojrzenie na szereg <math>{G}(x)=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,  
Drugim podejściem, bardziej użytecznym w praktycznych obliczeniach i przekształceniach jest spojrzenie na szereg <math>{G}(x)=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,  
Linia 170: Linia 168:
<center><math>\left(1+x\right)^m
<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
={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}^m {m \choose n}x^n.
=\sum_{n=0}^m {m \choose n}x^n</math></center>
</math></center>




Linia 180: Linia 177:


<center><math>{ y \choose n }= \frac{y^{\underline{n}}}{n!}=
<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}.
\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>
</math></center>




Linia 192: Linia 188:




<center><math>\left(1+x\right)^y=\sum_{n=0}^{\infty}{ y \choose n }x^n.
<center><math>\left(1+x\right)^y=\sum_{n=0}^{\infty}{ y \choose n }x^n</math></center>
</math></center>




Linia 202: Linia 197:




<center><math>\frac{1}{\left(1-x\right)^{m+1}}=\sum_{n=0}^{\infty}{ m+n \choose n }x^n.
<center><math>\frac{1}{\left(1-x\right)^{m+1}}=\sum_{n=0}^{\infty}{ m+n \choose n }x^n</math></center>}}
</math></center>}}




Linia 214: Linia 208:




<center><math>\sum_{k=0}^nk^2=1+4+9+\ldots+n^2.
<center><math>\sum_{k=0}^nk^2=1+4+9+\ldots+n^2</math></center>
</math></center>




Linia 223: Linia 216:


{{wzor|wzor_8|8|
{{wzor|wzor_8|8|
<math>\frac{1}{1-x} = \sum_{n=0}^{\infty}{n \choose n}x^n=\sum_{n=0}^{\infty}x^n,</math>}}
<math>\frac{1}{1-x} = \sum_{n=0}^{\infty}{n \choose n}x^n=\sum_{n=0}^{\infty}x^n</math>,}}


{{wzor|wzor_9|9|
{{wzor|wzor_9|9|
<math>\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.
<math>\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</math>}}
</math>}}




Linia 236: Linia 228:
<math>
<math>
\sum_{n=0}^{\infty}nx^n= \frac{1}{\left(1-x\right)^2}
\sum_{n=0}^{\infty}nx^n= \frac{1}{\left(1-x\right)^2}
-\frac{1}{1-x}.
-\frac{1}{1-x}</math>}}
</math>}}




Linia 245: Linia 236:
<center><math>\frac{1}{\left(1-x\right)^3}
<center><math>\frac{1}{\left(1-x\right)^3}
=\sum_{n=0}^{\infty}{ n+2 \choose n}x^n
=\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,
=\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>
</math></center>




Linia 254: Linia 244:


<center><math>{G}(x)=\sum_{n=0}^{\infty}n^2x^n
<center><math>{G}(x)=\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}.
=\frac{2}{\left(1-x\right)^3}-\frac{3}{\left(1-x\right)^2}+\frac{1}{1-x}</math></center>
</math></center>




Linia 263: Linia 252:


<center><math>{H}(x)=\frac{{G}(x)}{1-x}
<center><math>{H}(x)=\frac{{G}(x)}{1-x}
=\frac{2}{\left(1-x\right)^4}-\frac{3}{\left(1-x\right)^3}+\frac{1}{\left(1-x\right)^2}.
=\frac{2}{\left(1-x\right)^4}-\frac{3}{\left(1-x\right)^3}+\frac{1}{\left(1-x\right)^2}</math></center>
</math></center>




Linia 279: Linia 267:




<center><math>\sum_{k=1}^nk^2={x^n}{H}(x)=\frac{2n^3+3n+n}{6}.
<center><math>\sum_{k=1}^nk^2={x^n}{H}(x)=\frac{2n^3+3n+n}{6}</math></center>
</math></center>




Linia 287: Linia 274:




<center><math>{A_k}(x) = 1+x^k+x^{2k}+x^{3k}+\ldots,
<center><math>{A_k}(x) = 1+x^k+x^{2k}+x^{3k}+\ldots</math>,</center>
</math></center>




Linia 325: Linia 311:


<center><math>a_n=1,\quad b_n=a_n+b_{n-5},\quad c_n=b_n+c_{n-10},\quad
<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</math><math>\quad e_n=d_n+e_{n-50}.
d_n=c_n+d_{n-25},\quad</math><math>\quad e_n=d_n+e_{n-50}</math></center>
</math></center>




Linia 372: Linia 357:
<center><math>{F}(x)
<center><math>{F}(x)
=\sum_{n=0}^{\infty}f_nx^n
=\sum_{n=0}^{\infty}f_nx^n
=x+\sum_{n=2}^{\infty}\left(f_{n-1}+f_{n-2}\right)x^n=x+x{F}(x)+x^2{F}(x).
=x+\sum_{n=2}^{\infty}\left(f_{n-1}+f_{n-2}\right)x^n=x+x{F}(x)+x^2{F}(x)</math></center>
</math></center>




Linia 381: Linia 365:
{{wzor|wzor_11|11|
{{wzor|wzor_11|11|
<math>
<math>
{F}(x)=\frac{x}{1-x-x^2}.
{F}(x)=\frac{x}{1-x-x^2}</math>}}
</math>}}




Linia 392: Linia 375:
<center><math>{F}(x)=\frac{x}{1-x-x^2}
<center><math>{F}(x)=\frac{x}{1-x-x^2}
=\frac{x}{\left(1-z_0 x\right)\left(1-z_1 x\right)}
=\frac{x}{\left(1-z_0 x\right)\left(1-z_1 x\right)}
=\frac{1}{\sqrt{5}}\left(\frac{1}{\left(1-z_0 x\right)}-\frac{1}{\left(1-z_1 x\right)}\right),
=\frac{1}{\sqrt{5}}\left(\frac{1}{\left(1-z_0 x\right)}-\frac{1}{\left(1-z_1 x\right)}\right)</math>,</center>
</math></center>




Linia 401: Linia 383:
<center><math>{F}(x)
<center><math>{F}(x)
=\frac{1}{\sqrt{5}}\left(\sum_{n=0}^{\infty}{{z_0}^nx^n}-\sum_{n=0}^{\infty}{{z_1}^nx^n}\right)
=\frac{1}{\sqrt{5}}\left(\sum_{n=0}^{\infty}{{z_0}^nx^n}-\sum_{n=0}^{\infty}{{z_1}^nx^n}\right)
=\frac{1}{\sqrt{5}}\sum_{n=0}^{\infty}{\left({z_0}^n-{z_1}^n\right)x^n}.
=\frac{1}{\sqrt{5}}\sum_{n=0}^{\infty}{\left({z_0}^n-{z_1}^n\right)x^n}</math></center>
</math></center>




Linia 422: Linia 403:




<center><math>{A}(x)={Q}(x){B}(x)+{R}(x),
<center><math>{A}(x)={Q}(x){B}(x)+{R}(x)</math>,</center>
</math></center>




Linia 432: Linia 412:




<center><math>{A}(x)=3x^5+5x^4+2x^3+x^2+2\quad\text{oraz}\quad{B}(x)=x^3+2x^2-1.</math></center>
<center><math>{A}(x)=3x^5+5x^4+2x^3+x^2+2\quad\text{oraz}\quad{B}(x)=x^3+2x^2-1</math>.</center>




Linia 454: Linia 434:


{{wniosek|7.7|wn 7.7|
{{wniosek|7.7|wn 7.7|
Niech <math>{P}(x)</math> oraz <math>{Q}(x)</math> będą wielomianami takimi, że <math>deg{{P}(x)}\geq deg{{Q}(x)}</math>. Wtedy funkcję wymierną <math>{R}(x)={P}(x)/ {Q}(x),</math> można przedstawić w postaci
Niech <math>{P}(x)</math> oraz <math>{Q}(x)</math> będą wielomianami takimi, że <math>deg{{P}(x)}\geq deg{{Q}(x)}</math>. Wtedy funkcję wymierną <math>{R}(x)={P}(x)/ {Q}(x)</math>, można przedstawić w postaci




<center><math>{R}(x)=\frac{{P}(x)}{{Q}(x)}={A}(x)+\frac{{B}(x)}{{Q}(x)},
<center><math>{R}(x)=\frac{{P}(x)}{{Q}(x)}={A}(x)+\frac{{B}(x)}{{Q}(x)}</math>,</center>
</math></center>




Linia 464: Linia 443:
spełniających <math>deg{{B}(x)}<deg{{Q}(x)}</math>.}}
spełniających <math>deg{{B}(x)}<deg{{Q}(x)}</math>.}}


Będziemy więc skupiali się jedynie nad takimi funkcjami wymiernymi <math>{R}(x)={P}(x)/{Q}(x), </math> dla których <math>deg{{P}(x)}<deg{{Q}(x)}</math>.
Będziemy więc skupiali się jedynie nad takimi funkcjami wymiernymi <math>{R}(x)={P}(x)/{Q}(x)</math> dla których <math>deg{{P}(x)}<deg{{Q}(x)}</math>.


{{twierdzenie|7.8|tw 7.8|
{{twierdzenie|7.8|tw 7.8|
Linia 480: Linia 459:


<center><math>\frac{{P}(x)}{{Q}(x)}
<center><math>\frac{{P}(x)}{{Q}(x)}
=\frac{{A}(x)}{{S}(x)}+\frac{{B}(x)}{{T}(x)}.
=\frac{{A}(x)}{{S}(x)}+\frac{{B}(x)}{{T}(x)}</math></center>
</math></center>




Linia 494: Linia 472:




<center><math>{R}(x)=\frac{{P}(x)}{{Q}(x)},
<center><math>{R}(x)=\frac{{P}(x)}{{Q}(x)}</math>,</center>
</math></center>




Linia 502: Linia 479:


<center><math>{Q}(x)
<center><math>{Q}(x)
=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}.
=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>
</math></center>




Linia 510: Linia 486:


<center><math>{R}(x)
<center><math>{R}(x)
=\frac{{P}(x)}{{Q}(x)}=\frac{{P_1}(x)}{\left(1-\rho_1x\right)^{m_1}}+\frac{{P_2}(x)}{\left(1-\rho_2x\right)^{m_2}}+\ldots+\frac{{P_k}(x)}{\left(1-\rho_kx\right)^{m_k}},
=\frac{{P}(x)}{{Q}(x)}=\frac{{P_1}(x)}{\left(1-\rho_1x\right)^{m_1}}+\frac{{P_2}(x)}{\left(1-\rho_2x\right)^{m_2}}+\ldots+\frac{{P_k}(x)}{\left(1-\rho_kx\right)^{m_k}}</math>,</center>
</math></center>




Linia 527: Linia 502:




<center><math>{R}(x)= \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)}.
<center><math>{R}(x)= \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>
</math></center>




Linia 555: Linia 529:
\ldots+
\ldots+
\gamma_{i,m_i}{n+m_i-1\choose m_i - 1}
\gamma_{i,m_i}{n+m_i-1\choose m_i - 1}
\right)}\rho_i^n.
\right)}\rho_i^n</math>}}
</math>}}




Linia 563: Linia 536:




<center><math>{R}(x)=\frac{x^2}{1-x-x^2+x^3}.
<center><math>{R}(x)=\frac{x^2}{1-x-x^2+x^3}</math></center>
</math></center>




Linia 571: Linia 543:


<center><math>{R}(x)
<center><math>{R}(x)
=\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}.
=\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>
</math></center>




Linia 578: Linia 549:




<center><math>x^2=\alpha\left(1-x^2\right)+\beta\left(1+x\right)+\gamma\left(1-2x+x^2\right).
<center><math>x^2=\alpha\left(1-x^2\right)+\beta\left(1+x\right)+\gamma\left(1-2x+x^2\right)</math></center>
</math></center>




Linia 589: Linia 559:
\alpha &          & -\ 2\gamma & = & 0\\
\alpha &          & -\ 2\gamma & = & 0\\
& -\ \beta &  +\ \gamma & = & 1.
& -\ \beta &  +\ \gamma & = & 1.
\end{array} \right.
\end{array} \right.</math></center>
</math></center>




Rozwiązaniem powyższego układu są wartości <math>\alpha=-\frac{1}{4},\  
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
\beta=\frac{1}{2},\ \gamma=-\frac{1}{4}</math>. W konsekwencji otrzymujemy szereg




Linia 610: Linia 579:
<center><math>{x^n}{R}(x)
<center><math>{x^n}{R}(x)
=a_1\rho_1^n+\ldots+a_l\rho_l^n,
=a_1\rho_1^n+\ldots+a_l\rho_l^n,
\quad\text{dla}\ a_k=\frac{-\rho_k\cdot{P}(1/\rho_k)}{{Q'}(1/\rho_k)}.
\quad\text{dla}\ a_k=\frac{-\rho_k\cdot{P}(1/\rho_k)}{{Q'}(1/\rho_k)}</math></center>
</math></center>




Linia 620: Linia 588:




<center><math>{R}(x)=\frac{{P}(x)}{{Q}(x)}=\frac{2x}{1-5x-2x^2+24x^3}.
<center><math>{R}(x)=\frac{{P}(x)}{{Q}(x)}=\frac{2x}{1-5x-2x^2+24x^3}</math></center>
</math></center>




Linia 627: Linia 594:




<center><math>{R}(x)=\frac{2x}{\left(1+2x\right)\left(1-3x\right)\left(1-4x\right)}.
<center><math>{R}(x)=\frac{2x}{\left(1+2x\right)\left(1-3x\right)\left(1-4x\right)}</math></center>
</math></center>




Linia 634: Linia 600:




<center><math>{x^n}{R}(x)=-\frac{2}{15}\left(-2\right)^n-\frac{6}{5}3^n+\frac{4}{3}4^n.
<center><math>{x^n}{R}(x)=-\frac{2}{15}\left(-2\right)^n-\frac{6}{5}3^n+\frac{4}{3}4^n</math></center>}}
</math></center>}}




Linia 650: Linia 615:
r_n&=&a_1r_{n-1}+a_2r_{n-2}+\ldots+a_kr_{n-k}\quad\text{dla}\ n\geq k,
r_n&=&a_1r_{n-1}+a_2r_{n-2}+\ldots+a_kr_{n-k}\quad\text{dla}\ n\geq k,
\end{array}  
\end{array}  
\right.
\right.</math></center>
</math></center>




Linia 667: Linia 631:
r_n&=&a_1r_{n-1}+a_2r_{n-2}\quad\text{dla}\ n\geq 2.
r_n&=&a_1r_{n-1}+a_2r_{n-2}\quad\text{dla}\ n\geq 2.
\end{array}  
\end{array}  
\right.
\right.</math>}}
</math>}}




Linia 691: Linia 654:
* <math>\rho_1 \neq \rho_2</math> są różnymi liczbami rzeczywistymi. Wtedy  
* <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,
<center><math>r_n= \alpha\rho_1^n+\beta\rho_2^n</math>,</center>
</math></center>




Linia 698: Linia 660:
* <math>\rho_1 = \rho_2</math>. Wtedy
* <math>\rho_1 = \rho_2</math>. Wtedy


<center><math>r_n= \left(\alpha n+\beta\right)\rho_1^n,
<center><math>r_n= \left(\alpha n+\beta\right)\rho_1^n</math>,</center>
</math></center>




Linia 706: Linia 667:




<center><math>r_n= \alpha\rho_1^n+\beta\rho_2^n.
<center><math>r_n= \alpha\rho_1^n+\beta\rho_2^n</math></center>
</math></center>




Linia 716: Linia 676:




<center><math>{R}(x)= \frac{{P}(x)}{1-a_1x-a_2x^2-\ldots-a_kx^k},
<center><math>{R}(x)= \frac{{P}(x)}{1-a_1x-a_2x^2-\ldots-a_kx^k}</math>,</center>
</math></center>




Linia 735: Linia 694:
r_n&=&r_{n-1}+r_{n-2}-r_{n-3}\quad\text{dla}\ n\geq 3.
r_n&=&r_{n-1}+r_{n-2}-r_{n-3}\quad\text{dla}\ n\geq 3.
\end{array}  
\end{array}  
\right.
\right.</math></center>
</math></center>




Linia 742: Linia 700:




<center><math>{R}(x)=x^2 + x{R}(x) + x^2{R}(x) - x^3{R}(x).
<center><math>{R}(x)=x^2 + x{R}(x) + x^2{R}(x) - x^3{R}(x)</math></center>
</math></center>




Linia 749: Linia 706:




<center><math>{R}(x)=\frac{x^2}{1-x-x^2+x^3}.
<center><math>{R}(x)=\frac{x^2}{1-x-x^2+x^3}</math></center>
</math></center>




Linia 756: Linia 712:




<center><math>r_n=-\frac{1}{4}+\frac{1}{2}\left(n+1\right) - \frac{1}{4}\left(-1\right)^n\quad\text{dla dowolnego}\ n=0,1,2,3,\ldots.
<center><math>r_n=-\frac{1}{4}+\frac{1}{2}\left(n+1\right) - \frac{1}{4}\left(-1\right)^n\quad\text{dla dowolnego}\ n=0,1,2,3,\ldots</math></center>}}
</math></center>}}

Aktualna wersja na dzień 22:35, 15 wrz 2023

Przykład

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 (1), pięciocentówek (5), dziesięciocentówek (10), ćwierćdolarówek (25), oraz półdolarówki (50). 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ć jeszcze monetę [0], którą możemy interpretować jako brak monet. Wypiszmy teraz (nadużywając trochę notacji) nieskończoną sumę wszystkich możliwości rozmiany dowolnej kwoty za pomocą jednocentówek


A1=[0]+(1)+(1)(1)+(1)(1)(1)+(1)(1)(1)(1)+


i analogicznie przeanalizujmy sumę dla pieciocentówek


A5=[0]+(5)+(5)(5)+(5)(5)(5)+(5)(5)(5)(5)+


Wtedy zbiór par A1×A5 jest zbiorem wszystkich możliwości rozmiany kwoty przy użyciu dowolnie wielu jednocentówek oraz pięciocentówek.


B=A1×A5=([0]+(1)+(1)(1)+(1)(1)(1)+(1)(1)(1)(1)+)×([0]+(5)+(5)(5)+(5)(5)(5)+(5)(5)(5)(5)+)=[0]+(1)+(5)+(1)(1)+(1)(5)+(5)(5)+(1)(1)(1)+


Sumy wszystkich możliwości rozmiany za pomocą dziesięciocentówek (10), ćwierćdolarówek (25), oraz półdolarówek (50) wyglądają następująco:


A10=[0]+(10)+(10)(10)+(10)(10)(10)+(10)(10)(10)(10)+A25=[0]+(25)+(25)(25)+(25)(25)(25)+(25)(25)(25)(25)+A50=[0]+(50)+(50)(50)+(50)(50)(50)+(50)(50)(50)(50)+


Dodając kolejno monety (10), (25), i na końcu (50) do możliwych rozmian, uzyskujemy odpowiednio:


C=B×([0]+(10)+(10)(10)+(10)(10)(10)+(10)(10)(10)(10)+)D=C×([0]+(25)+(25)(25)+(25)(25)(25)+(25)(25)(25)(25)+)E=D×([0]+(50)+(50)(50)+(50)(50)(50)+(50)(50)(50)(50)+)=[0]+(1)+(5)+(10)+(25)+(50)+(1)(1)+(1)(5)+(1)(10)+


Grupując teraz składniki sumy E w podsumy o tych samych wartościach dostajemy wyrażenie:


E=((1))+((1)(1))+((1)(1)(1))+((1)(1)(1)(1))+((1)(1)(1)(1)(1)+(5))+((1)(1)(1)(1)(1)(1)+(5)(1))+      (1)


Zliczając zaś tylko składniki w podsumie odpowiadającej wartości n centów, otrzymujemy liczbę sposobów, na które można rozmienić n centów przy użyciu monet (1), (5), (10), (25), oraz (50). Pomysłem pochodzącym od Pólya, było zastąpienie monety (1) przez zmienną x, monety (5) przez xxxxx=x5 i analogicznie (10) przez x10, (25) przez x25, oraz (50) przez x50. Uzyskujemy w ten sposób nieskończony szereg zmiennej x:


E(x)=(1+x+x2+x3)(1+x5+x10+x15)(1+x10+x20+x30)(1+x25+x50+x75)(1+x50+x100+x150)=1+x+x2+x3+x4+2x5+2x6+2x7+2x8+2x9+4x10+


Godne zauważenia jest, że liczba różnych możliwych sposobów rozmiany n centów (równa liczbie grup monet w odpowiednim nawiasie we wzorze (1)) jest równa współczynnikowi stojącemu przy jednomianie xn.

Funkcja tworząca G(x) dla ciągu liczb rzeczywistych (lub zespolonych) (g0,g1,g2,g3,) to szereg funkcyjny zmiennej rzeczywistej (lub zespolonej) x postaci


G(x)=n=0gnxn=g0+g1x+g2x2+g3x3+g4x4+


Na oznaczenie współczynnika n-tego wyrazu szeregu G(x) używać będziemy oznaczenia xnG(x)=gn.

Uwaga Jak traktowac funkcje tworzące

Na funkcje tworzące można spojrzeć dwoiście. Pierwszym sposobem jest potraktowanie G(x) jako szeregu liczb rzeczywistych (lub ogólniej zespolonych). Oczywistym pytaniem jest tu kwestia zbieżności szeregu G(x)=n=0gnxn. Z wykładu Analiza Matematyczna wiemy, że szereg G(x) jest zbieżny, jeśli istnieje stała M0 ograniczająca wszystkie skończone początkowe sumy, tzn.


|g0|+|g1x|+|g2x2|++|gnxn|M


zachodzi dla dowolnego n0. Ponadto jeśli dla pewnej liczby x0 szereg G(x0)=g0+g1x0+g2x02+ jest zbieżny, to i także szereg G(x1)=g0+g1x1+g2x12+ jest zbieżny dla dowolnego x1 spełniającego |x1||x0|. Możemy więc określić promień zbieżności szeregu jako taką liczbę r*{} =0,+, że jeśli |x|<r, to G(x) jest zbieżny.

Szereg G(x)=g0+g1x+g2x2+ można więc potraktować jako funkcję


G:(r,r),


o wartościach G(x)=limn(g0+g1x+g2x2++gnxn). Oczywiście G(0)=g0, więc dla x=0 szereg G(x) jest zbieżny.

Drugim podejściem, bardziej użytecznym w praktycznych obliczeniach i przekształceniach jest spojrzenie na szereg G(x)=g0+g1x+g2x2+ jako formę zapisu ciągu (g0,g1,g2,), 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 G(x)=g0+g1x+g2x2+ jest funkcją tworzącą ciągu (g0,g1,g2,g3,), oraz w jakiś sposób będziemy w stanie poznać postać zwartą funkcji G(x), 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 r>0. Ponadto będziemy pomijać problem zbieżności oraz wartość r 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.

Obserwacja 7.1

Dla dwu funkcji tworzących F(x)=f0+f1x+f2x2+ oraz G(x)=g0+g1x+g2x2+ mamy:


F(x)=Gxf0=g0, f1=g1, f2=g2, αF(x)+βGx=n=0(αfn+βgn)xn=(αf0+βg0)+(αf1+βg1)x+(αf2+βg2)x2+F(x)G(x)=n=0(k=0nfkgnk)xn=f0g0+(f0g1+f1g0)x+(f0g2+f1g1+f2g0)x2+(f0g3+f1g2+f2g1+f3g0)x3+


Wyrażenie F(x)G(x) nazywać będziemy splotem szeregów F(x) oraz G(x).

Twierdzenie 7.2

Funkcja tworząca postaci


G(x)=g0+g1x+g2x2+g3x3+


ma odwrotną względem mnożenia (splotu), tzn. istnieje funkcja tworząca U(x) taka, że U(x)G(x)=1, wtedy i tylko wtedy, gdy g00.

Następne własności są bardzo pomocne w dokonywanych przekształceniach funkcji tworzących.

Obserwacja 7.3

Dla dwu funkcji tworzących F(x)=f0+f1x+f2x2+ oraz G(x)=g0+g1x+g2x2+ mamy:


xmG(x)=0++0xm1+g0xm+g1xm+1+g2xm+2+      (2)

G(x)i=0m1gixixm=gm+gm+1x+gm+2x2+gm+3x3+gm+4x4+      (3)

G(αx)=g0+g1αx+g2α2x2+g3α3x3+g4α4x4+      (4)

G(x)=g1+2g2x+3g3x2+4g4x3+5g5x4+      (5)

G(x)dx=0+g0x+12g1x2+13g2x3+14g3x4+      (6)

G(x)1x=g0+(g0+g1)x+(g0+g1+g2)x2+      (7)


Funkcje tworzące w zliczaniu

Widzieliśmy już, że dla n


(1+x)m=(m0)x0+(m1)x+(m2)x2++(mm1)xm1+(mm)xm=n=0m(mn)xn


Przyjrzyjmy się teraz rozwinięciu w szereg funkcji (1+x)y, gdzie y 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 (yn), gdzie y oraz n jest oznaczeniem na


(yn)=yn_n!=y(y1)(y(n1))12(n1)n


Uwaga

Oczywiście dla y spełniającego dodatkowo yn, uogólniony symbol dwumianowy (yn) jest liczbą n-elementowych podzbiorów zbioru y-elementowego.

Twierdzenie 7.4

Dla liczby rzeczywistej y oraz liczby naturalnej n zachodzi


(1+x)y=n=0(yn)xn


Wniosek 7.5

Dla liczby naturalnej m zachodzi


1(1x)m+1=n=0(m+nn)xn


Dowód

Dowód zostawiony jest jako ćwiczenie 3.

Przykład

Policzmy sumę


k=0nk2=1+4+9++n2


Zacznijmy od znalezienia zwartej postaci funkcji tworzącej

G(x)=n=0n2xn. Korzystając z Wniosku 7.5 otrzymujemy:


11x=n=0(nn)xn=n=0xn,      (8)

1(1x)2=n=0(n+1n)xn=n=0nxn+n=0xn      (9)


Po przekształceniu równości (9) uzyskuje się


n=0nxn=1(1x)211x      (10)


Powołując się ponownie na Wniosek 7.5 otrzymujemy


1(1x)3=n=0(n+2n)xn=12n=0n2xn+32n=0nxn+n=0xn,


co w połączeniu z równościami (9) oraz (10) daje zwartą postać funkcji tworzącej G(x) dla ciągu 1,4,9,,n2,:


G(x)=n=0n2xn=2(1x)33(1x)2+11x


Naszym zadaniem było jednakże policzenie funkcji tworzącej H(x) dla ciągu 1,1+4,1+4+9,,1+4+9++n2,, tzn. ciągu sum początkowych wyrazów ciągu 1,4,9,,n2,. Aby uzyskać H(x) wystarczy więc skorzystać ze wzoru (7) i podzielić G(x) przez 1x. Tak więc poszukiwanym rozwiązaniem są współczynniki funkcji tworzącej


H(x)=G(x)1x=2(1x)43(1x)3+1(1x)2


Korzystając po raz kolejny z Wniosku 7.5 otrzymujemy


H(x)=2n=0(n+3n)xn3n=0(n+2n)xn+n=0(n+1n)xn=n=0(13n3+12n2+16n)xn.


W konsekwencji zachodzi równość


k=1nk2=xnH(x)=2n3+3n+n6


Przykład

Wracamy do przykładu z monetami. Występowały tam funkcje tworzące postaci


Ak(x)=1+xk+x2k+x3k+,


dla k=1,5,10,25 i 50. Z równości (7) wiemy, że


1+xk+x2k+x3k+,=11xk


tak więc:


A(x)=A1(x)=11x,B(x)=A(x)A5(x)=A(x)1x5,C(x)=B(x)A10(x)=B(x)1x10,D(x)=C(x)A25(x)=C(x)1x25,E(x)=D(x)A50(x)=D(x)1x50,


skąd natychmiast:


A(x)=1+xA(x),B(x)=A(x)+x5B(x),C(x)=B(x)+x10C(x),C(x)=D(x)+x25C(x),D(x)=E(x)+x50D(x).


Równości te dają zależności między współczynnikami:


an=1,bn=an+bn5,cn=bn+cn10,dn=cn+dn25,en=dn+en50


Wykorzystując te zależności rekurencyjne możemy wypełnić następującą tabelę:


n05101520253035404550556065707580859095100HLINE TBDan111111111111111111111bn123456789101112131415161718192021cn12469121610253036424956647281100121dn11349121242en150292


Pół dolara można rozmienić na 50 sposobów. Z kolei rozmieniać jednego dolara można na aż 292 sposoby. Do problemu tego wrócimy jeszcze w następnym wykładzie.

Funkcje tworzące w rozwiązywaniu zależności rekurencyjnych

Przykład

Rozważmy ciąg Fibonacci'ego, tzn. ciąg (f0,f1,f2,f3,) zdefiniowany w następujący sposób:


f0=0,f1=1,fn=fn1+fn2dla n2.


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 fn przekładają się natychmiast na następujące równanie, jakie musi spełniać funkcja tworząca F(x) dla ciągu Fibonacci'ego


F(x)=n=0fnxn=x+n=2(fn1+fn2)xn=x+xF(x)+x2F(x)


Przekształcając powyższe równanie otrzymujemy:


F(x)=x1xx2      (11)


Celem, który chcemy osiągnąć to wykorzystanie funkcji x1xx2 do przedstawienia współczynników fn w postaci zwartej. Pierwszym krokiem będzie rozłożenie ułamka w równaniu (11) na sumę ułamków o mianownikach będących funkcjami liniowymi


F(x)=x1xx2=x(1z0x)(1z1x)=15(1(1z0x)1(1z1x)),


gdzie z0=1+52 jest złotą liczbą oraz z1=152 liczbą do niej sprzężoną. Korzystając z równania (7) otrzymujemy teraz


F(x)=15(n=0z0nxnn=0z1nxn)=15n=0(z0nz1n)xn


Tak więc dostajemy szybko znaną nam już postać zwartą fn=15(z0nz1n).

Podczas rozwiązywania przykładu związanego z liczbami Fibonacci'ego natrafiliśmy na problem polegający na przedstawieniu w postaci szeregu wyrażenia x1xx2. Przyjrzymy się dokładniej tego typu wyrażeniom.

Stopień wielomianu degP(x)=n, jeśli P(x)=p0+p1x++pnxn.

Funkcja wymierna R(x) to funkcja postaci P(x)Q(x), gdzie P(x) oraz Q(x)0 są wielomianami skończonego stopnia.

Obserwacja 7.6

Niech A(x) oraz B(x) będą wielomianami degA(x)degB(x). Wtedy istnieją wielomiany Q(x) oraz R(x) takie, że


A(x)=Q(x)B(x)+R(x),


gdzie degR(x)<degA(x)=degQ(x)+degB(x).

Przykład

Niech


A(x)=3x5+5x4+2x3+x2+2orazB(x)=x3+2x21.


Wtedy wielomiany


Q(x)=3x2x+3orazR(x)=x+2


spełniają


A(x)=3x5+5x4+2x3+x2+2=(3x2x+3)(x3+2x21)+x+2=Q(x)B(x)+R(x).


Ponadto degA(x)=5=2+3=degQ(x)+degB(x).

Wniosek 7.7

Niech P(x) oraz Q(x) będą wielomianami takimi, że degP(x)degQ(x). Wtedy funkcję wymierną R(x)=P(x)/Q(x), można przedstawić w postaci


R(x)=P(x)Q(x)=A(x)+B(x)Q(x),


dla pewnych wielomianów A(x) oraz B(x)

spełniających degB(x)<degQ(x).

Będziemy więc skupiali się jedynie nad takimi funkcjami wymiernymi R(x)=P(x)/Q(x) dla których degP(x)<degQ(x).

Twierdzenie 7.8

Niech P(x) oraz Q(x) będą wielomianami takimi, że

  • degP(x)<degQ(x),
  • Q(x)=S(x)T(x), gdzie oba wielomiany S(x),T(x) są stopnia co najmniej 2,
  • q00.

Wtedy istnieją wielomiany A(x) oraz B(x) takie, że degA(x)<degS(x) i degB(x)<degT(x) oraz


P(x)Q(x)=A(x)S(x)+B(x)T(x)


Uwaga

Twierdzenie 7.8 pozwala na rozbijanie skomplikowanych funkcji wymiernych na sumę prostszych.

Wniosek [Metoda rozwijania funkcji wymiernej w szereg]

Rozważmy funkcję wymierną w postaci


R(x)=P(x)Q(x),


gdzie degP(x)<degQ(x), oraz q00. Załóżmy ponadto, że wielomian Q(x) rozkłada się na następujący iloczyn czynników liniowych


Q(x)=q0(1ρ1x)m1(1ρ2x)m2(1ρkx)mk


Warto wspomnieć, że dalecy nie każdy wielomian ma taki rozkład. Na przykład 1+x2 jest nierozkładalny i nieliniowy. Wykorzystując parokrotnie Twierdzenie 7.8 otrzymujemy wielomiany P1(x),,Pk(x) takie, że


R(x)=P(x)Q(x)=P1(x)(1ρ1x)m1+P2(x)(1ρ2x)m2++Pk(x)(1ρkx)mk,


gdzie degPi(x)<mi. Na mocy Obserwacji 7.6 możemy sprowadzić wielomian Pi(x) do


Pi(x)=Pi1(x)(1ρix)+γmi=Pi2(x)(1ρix)2+γmi1(1ρix)+γmi=γ1(1ρix)mi1++γmi1(1ρix)+γmi,


gdzie midegPi(x)>degPi1(x)>degPi2(x)>. W konsekwencji otrzymamy


R(x)=i=1k(γi,11ρix+γi,2(1ρix)2++γi,mi(1ρix)mi)


Mnożąc teraz obie strony przez


Q(x)/q0=(1ρ1x)m1(1ρ2x)m2(1ρkx)mk


i porównując współczynniki przy odpowiadających potęgach xi uzyskujemy pewien układ równań, rozwiązanie którego da nam poszukiwane współczynniki γi,j. Z drugiej strony, z Wniosku 7.5 wynika, że


1(1ρx)m+1=n=1(m+nm)ρnxn


i w konsekwencji:


[xn]R(x)=i=1k(γi,1+γi,2(n+11)++γi,mi(n+mi1mi1))ρin      (12)


Przykład

Opisaną wyżej metodę ogólną zilustrujemy na przykładzie funkcji


R(x)=x21xx2+x3


Wielomian 1xx2+x3 ma jeden podwójny pierwiastek x=1 oraz jeden pojedynczy x=1. Poznana metoda rozwijania funkcji wymiernej w szereg daje więc


R(x)=x2(1x)2(1+x)=α1x+β(1x)2+γ1+x


Mnożąc obie strony przez (1x)2(1+x) otrzymujemy:


x2=α(1x2)+β(1+x)+γ(12x+x2)


Dwa wielomiany są równe, gdy współczynniki przy odpowiadających potęgach są sobie równe. Wartości α,β,γ można więc wyliczyć z układu równań


{α+ β+ γ=0α 2γ=0 β+ γ=1.


Rozwiązaniem powyższego układu są wartości α=14, β=12, γ=14. W konsekwencji otrzymujemy szereg


R(x)=n=0(14+12(n+1)14(1)n)xn=x2+x3+2x4+2x5+3x6+3x7+4x8+.


Jeżeli mianownik Q(x) funkcji wymiernej R(x)=P(x)Q(x) posiada jedynie pierwiastki jednokrotne, to następne twierdzenie znacznie przyspiesza rozkład R(x) na sumę.

Twierdzenie 7.9

Jeśli R(x)=P(x)/Q(x), gdzie Q(x)=q0(1ρ1x)(1ρ1x) i liczby ρ1,,ρl są parami różne, to w przypadku gdy P(x) jest wielomianem stopnia mniejszego niż l, zachodzi


xnR(x)=a1ρ1n++alρln,dla ak=ρkP(1/ρk)Q(1/ρk)


Przykład

Mianownik Q(x) funkcji wymiernej


R(x)=P(x)Q(x)=2x15x2x2+24x3


ma trzy różne pierwiastki i można R(x) przedstawić jako


R(x)=2x(1+2x)(13x)(14x)


Na mocy Twierdzenia 7.9 otrzymujemy więc, że


xnR(x)=215(2)n653n+434n


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


{r0=c0,rk1=ck1,rn=a1rn1+a2rn2++akrnkdla nk,


gdzie c0,,ck1,a1,,ak są liczbami rzeczywistymi (niezależnymi od parametru rekurencyjnego n).

Rozważmy najpierw przypadek, gdy k=2, tzn. równanie postaci


{r0=c0,r1=c1,rn=a1rn1+a2rn2dla n2.      (13)


Przykładem takiego równania była zależność opisująca ciąg Fibonacci'ego. Zastosowanie ostatniej równości z (13) do funkcji tworzącej ciągu (r0,r1,r2,) daje:


R(x)=r0+r1x+r2x2+r3x3++rnxn+=c0+c1x+(a1r1+a2r0)x2++(a1rn1+a2rn2)xn+=c0+(c1a1c0)x+a1xR(x)+a2x2R(x),


tak więc


R(x)=c0+(c1a1c0)x1a1xa2x2


Dla funkcji A(x)=1a1xa2x2=(1ρ1x)(1ρ2x) mogą zajść trzy przypadki:

  • ρ1ρ2 są różnymi liczbami rzeczywistymi. Wtedy
rn=αρ1n+βρ2n,


gdzie α oraz β są liczbami rzeczywistymi.

  • ρ1=ρ2. Wtedy
rn=(αn+β)ρ1n,


gdzie α oraz β są liczbami rzeczywistymi.

  • Wartości ρ1 oraz ρ2 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


rn=αρ1n+βρ2n


gdzie α oraz β 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.

Wracamy teraz do ogólnego, jednorodnego liniowego równania rekurencyjnego. Analogicznie do przypadku, gdy k=2, otrzymujemy że


R(x)=P(x)1a1xa2x2akxk,


gdzie P(x) jest wielomianem co najwyżej stopnia k1, zależnym od wartości c0,,ck1,a1,,ak. Korzystając z ogólnej metody rozwijania funkcji wymiernej w szereg, możemy odzyskać wyrazy ciągu rn, jako współczynniki [xn]R(x) zgodnie z równaniem (12).


Przykład

Równanie rekurencyjne ma następującą postać


{r0=0,r1=0,r2=1,rn=rn1+rn2rn3dla n3.


Ostatnia zależność prowadzi do funkcji tworzącej R(x) spełniającej


R(x)=x2+xR(x)+x2R(x)x3R(x)


Po dokonaniu prostego wyliczenia dostajemy:


R(x)=x21xx2+x3


W przykładzie omawianym przy okazji metody rozwijania funkcji wymiernej w szereg, wyliczyliśmy współczynniki [xn]R(x), a zatem mamy:


rn=14+12(n+1)14(1)ndla dowolnego n=0,1,2,3,