====== Matematyka dyskretna (M) - Lista 8. ======
===== Zadanie 1. =====
$\sum 2^{-k\cdot n} = \sum (2^{-n})^k = \frac 1 {1 - 2^{-n}} = \frac {2^{n}} {2^{n}-1}$
$ S = \sum 2^{-k}$ \\
$ - \sum 2^{-k\cdot 2} - \sum 2^{-k\cdot 3} - \sum 2^{-k\cdot 5} - \sum 2^{-k\cdot 7}$ \\
$ + \sum 2^{-k\cdot 2\cdot 3} + \sum 2^{-k\cdot 2\cdot 5} + \sum 2^{-k\cdot 2\cdot 7} + \sum 2^{-k\cdot 3\cdot 5} + \sum 2^{-k\cdot 3\cdot 7} + \sum 2^{-k\cdot 5\cdot 7}$ \\
$ - \sum 2^{-k\cdot 2 \cdot 3\cdot 5} - \sum 2^{-k\cdot 2 \cdot 3\cdot 7} - \sum 2^{-k\cdot 2 \cdot 5\cdot 7} - \sum 2^{-k\cdot 3 \cdot 5\cdot 7}$ \\
$ + \sum 2^{-k\cdot 2 \cdot 3\cdot 5 \cdot 7}$
$ = 2 - \frac 4 3 - \frac 8 7 - \frac {32} {31} - \frac {128} {127} + \frac {64} {63} + \frac {1024} {1023} + \frac {16384} {16383} + \frac {32768} {32767} + \dots \approx 0.5006$
(gdyby chcieć policzyć to na palcach, można każdy z tych ułamków dla większych n przybliżyć jako 1)
===== Zadanie 2. =====
Przypomnę notację: $\Phi(a_n)$ oznacza funkcję tworzącą $a_n$.
$\Phi(a_n) = A(x) = a_n x^n = a_0 + a_1 x^1 + a_2 x^2 + \dots$
$\displaystyle \Phi(a_{2n}) = a_0 + a_2 x^1 + a_4 x^2 + \dots = a_0 + a_2 x^{2/2} + a_4 x^{4/2} + \dots = \Phi(b_n)(x^{1/2}) = \frac {A(x^{1/2}) + A(-x^{1/2})} 2 $, gdzie $b_n = \cases{a_n & \text{n parzyste} \cr 0 & \text{otherwise}}$.
$\displaystyle \frac {A(x^{1/3}) + A(x^{1/3} \cdot (-1)^{2/3}) + A(x^{1/3} \cdot (-1)(-1)^{1/3})} {3} =$
$\displaystyle \frac {3 a_0 + (1 + (-1)^{2/3} + (-1)^{1/3})a_1 x^{1/3} + (1 + (-1)^{2/3} +(-1)^{1/3} )a_2 x^{2/3} + 3 a_3 x^1 + \dots} 3 = \frac {3a_0 + 3a_3x^1 + \dots} 3 = \Phi(a_{3n})$
---
Troche komentarza do metody szukania "wybiórczych" ciągów. Oczywiście można strzelić i trafić, ale można do tego podejść również bardziej metodycznie. Zwłaszcza, że tutaj mamy równoodległe elementy, a być może nie chcemy, żeby tak było, czy coś tam.
Np. szukamy $\Phi(a_{3n})$, a mamy do dyspozycji $\Phi(a_n) = A(x)$. Dotychczas wpadliśmy na dwa triki -- dla $\Phi(a_{2n})$ oraz $\Phi(a_{3n})$. Obydwa były liniową kombinacją jakiejś aplikacji naszego oryginalnego A(x). Czyli:
$\cases{
a(a_0 + \alpha a_1 x + \alpha^2 a_2 x^2 + \alpha^3 a_3 x^3 + \dots) \cr
+ b(a_0 + \beta a_1 x + \beta^2 a_2 x^2 + \beta^3 a^3 x^3 + \dots) \cr
+ c(a_0 + \gamma a_1 x + \gamma^2 a_2 x^2 + \gamma^3 a^3 x^3 + \dots) \cr
= a_0 + a_3 x^3 + \dots
}$
Gdzie $a,b,c$ to współczynniki kombinacji liniowej, a $\alpha, \beta, \gamma$ to nasze szukane trikowe rzeczy które wstawiamy do A(x)
(x-ami można się zająć później)
To jeszcze nie jest takie fajne, bo mamy nieskończenie wiele termów. Ale możemy zauważyć, że wyrzucamy termy cyklicznie. To znaczy, że $\alpha, \beta, \gamma$ muszą się cyklicznie zachowywać. A dokładniej muszą być takie same przy podniesieniu do co trzecich potęg. Można to osiągnąć przez dodanie warunków:
$\cases{
\alpha^3 = 1 \cr
\beta^3 = 1 \cr
\gamma^3 = 1 \cr
}$
A to nam ogranicza możliwe rozwiązania do pierwiastków trzeciego stopnia liczby 1, czyli po pierwsze mamy skończoną liczbą możliwych rozwiązań (fajnie). Po drugie, możemy się zająć tylko pierwszymi trzema termami:
$\cases{
a(a_0 + \alpha a_1 x + \alpha^2 a_2 x^2) \cr
+ b(a_0 + \beta a_1 x + \beta^2 a_2 x^2) \cr
+ c(a_0 + \gamma a_1 x + \gamma^2 a_2 x^2) \cr
= a_0
}$
Przekształcając:
$\cases{
a + b + c = 1 \cr
a \alpha + b \beta + c \gamma = 0 \cr
a \alpha^2 + b \beta^2 + c \gamma^2 = 0 \cr
}$
Nie wiem jak się rozwiązuje takie układy równań, ale jako że mamy $3^3$ potencjalnych rozwiązań, można w byle Haskellu sprawdzić wszystkie.
Oczywiście nie gwarantuję, że ta metoda jest poprawna ani kompletna. Być może jest jakiś warunek, którego tu brakuje, a który przeoczyłem.
===== Zadanie 3. =====
===== Zadanie 4. =====
$\displaystyle ((1+x)^a)^{(n)} = a^{\underline n} (1+x)^{a-n}$
$\displaystyle (1+x)^a = \sum_{n=0}^{\infty} \frac 1 {n!} ((1+x)^a)^{(n)}(x_0) \cdot (x-x_0)^n = \sum_{n=0}^{\infty} \frac {a^{\underline n}} {n!} (1+x_0)^{a-n} \cdot (x-x_0)^n$.
Dla $x_0 = 0$ mamy więc $\displaystyle (1+x)^a = \sum_{n=0}^{\infty} \frac {a^{\underline n}} {n!} x^n$
===== Zadanie 5. =====
**a)**
$\displaystyle F(x) = \sum_{n=0}^{\infty} a_n x^n = 1 + x + x^2 + \sum_{n=3}^{\infty} (a_{n-1} + a_{n-2} + a_{n-3} + 1) x^n = $\\
$1 + x + x^2 + x(F(x)-2) + x^2(F(x)-1) + x^3F(x) + \frac 1 {1-x} - 1 - x -x^2 = xF(x) -2x + x^2F(x) - x^2 + x^3F(x) + \frac 1 {1-x} $
$\displaystyle (1-x-x^2-x^3)F(x) = -2x-x^2+\frac 1 {1-x} = \frac {-2x + x^2 + x^3 + 1} {1-x}$
A więc $\displaystyle F(x) = \frac {-2x + x^2 + x^3 + 1} {(1-x)(1-x-x^2-x^3)}$.
**b)**
$\displaystyle F(x) = x + \sum_{n=2}^{\infty} (a_{n-1} + a_{n-2} + \frac 1 {n-1})x^n = xF(x) + x^2F(x) + \sum_{n=1}^{\infty} \frac 1 n x^{n+1} = xF(x) + x^2F(x) -\frac{x\log(1-x)}{1-x}$
$\displaystyle (1-x-x^2)F(x) = \frac{-x\log(1-x)}{1-x}$
$\displaystyle F(x) = \frac {-x\log(1-x)} {(1-x)(1-x-x^2)}$
**c)**
$\displaystyle F(x) = 1 + \sum_{n=1}^{\infty} (\sum_{k=0}^{n-1} a_{n-1-k} \frac 1 {k!}) x^n = 1 + \sum_{n=1}^{\infty} \sum_{k=0}^{n-1} a_{n-1-k} \frac 1 {k!} x^n = 1+ \sum_{n=1}^{\infty} \sum_{k=0}^{\infty} a_k \frac 1 {(n-1)!} x^{k+n} = 1 + \sum_{n=1}^{\infty} F(x) \frac 1 {(n-1)!} x^n = 1 + F(x) x e^x$
$\displaystyle F(x) = \frac 1 {1 - xe^x}$
Później sprawdzę, czy zadanie jest zrobione dobrze (teraz jest późno).
===== Zadanie 6. =====
===== Zadanie 7. =====
===== Zadanie 8. =====
===== Zadanie 9. =====
===== Zadanie 10. =====
www.maths.usyd.edu.au/u/kooc/catalan/cat5hand.pdf
===== Zadanie 11. =====
===== Zadanie 12. =====
$\displaystyle P(x) = \prod_{k=1}^{\infty} \frac 1 {1-x^k}$\\
$\displaystyle R(x) = \prod_{k=1}^{\infty} (1+x^k)$
$\displaystyle R(x) P(x^2) = \prod_{k=1}^{\infty} \frac {1+x^k} {1-x^{2k}} = \prod_{k=1}^{\infty} \frac {(1+x^k)} {(1+x^k)(1-x^k)} = P(x)$
===== Zadanie 13. =====
===== Zadanie 14. =====
$\displaystyle {n \brack k} = (n-1) {n-1 \brack k} + {n-1 \brack k-1}$.
Wyobraźmy sobie wszystkie sposoby na jakie można z permutacji $n-1$-elementowych uzyskać permutacje $n$-elementowe mające $k$ rozłącznych cykli. Możemy to zrobić na dwa sposoby:
* wziąć wszystkie $n-1$-elementowe permutacje mające $k-1$ rozłącznych cykli i dodać nasz nowy element jako singleton. Temu odpowiada term ${n-1 \brack k-1}$.
* wziąć wszystkie $n-1$-elementowe permutacje mające już $k$ rozłącznych cykli. Wyglądają one tak: \\ $\underbrace{(a_1 \cdots a_{j_1})(a_{j_1 + 1}) \cdots (a_{j_k + 1} \cdots a_n)}_{k\;\rm razy}$ \\ Do każdej takiej permutacji można wstawić nowy element na $n-1$ sposobów, czemu odpowiada term $(n-1) {n-1 \brack k}$.
Teraz udowodnimy $\displaystyle x^{\underline n} = \sum_{k=0}^{\infty} {n \brack k} x^k$ przez indukcję po $n$.
Dla $n=1$. $\displaystyle x^{\underline 1} = x = 0 + x = {1 \brack 0} + {1 \brack 1}x$. OK.
Dla $n>1$. $\displaystyle \sum_{k=0}^{\infty} {n \brack k} x^k = \sum_{k=1}^{\infty} (n-1) {n-1 \brack k} x^k + \sum_{k=0}^{\infty} {n-1 \brack k-1} x^k = (n-1)x^{\underline {n-1}} + x \cdot x^{\underline {n-1}} = x^{\underline {n-1}} (x+n-1) = x^{\underline n}$. OK.
===== Zadanie 15. =====
$\displaystyle \int_0^{\infty} G_e(zt)e^{-t} \; dt = \int_0^{\infty} (\sum_{n=0}^{\infty} a_n \frac{ z^nt^n} {n!} e^{-t}) \; dt = \sum_{n=0}^{\infty} a_n z^n \frac 1 {n!} (\int_0^{\infty} t^n e^{-t} \; dt) = \sum_{n=0}^{\infty} a_n z^n \frac {\Gamma(n+1)} {n!} = \sum_{n=0}^{\infty} a_n z^n \frac {n!} {n!} = \sum_{n=0}^{\infty} a_n z^n = G(z)$