Lista-4

by Jerry Sky

2020-12-20

Do rozwiązań dołączone są pliki o rozszerzeniu .wls — są to pliki zawierające skrypty napisane w WolframScript i realizują praktyczną część danego zadania.

Uruchomienie na Linuxie (z zainstalowanym Wolfram Mathematica i WolframScript): ./ex-‹numer zadania›.wls.

Zadanie 1.

Ile jest permutacji zbioru 3030-elementowego, składających się z cykli długości co najwyżej 55?

Podobne zadanie do zadania 2. z listy 4. z ćwiczeń — tym razem jednak ograniczamy długość cykli: P′′=SET⁡(CYC⁡≤5(Z)) \mathcal{P}'' = \operatorname{SET}(\operatorname{CYC}_{\le5}(\mathcal{Z})) wówczas mamy EGF: P′′(z)=exp⁡(∑n=15znn) P''(z) = \exp\left( \sum_{n=1}^5 \frac{z^n}{n} \right)

Wynik: 30!⋅[z30]P′′(z)=19054894203999260640645120000=1.905489420399926064064512⋅102830! \cdot [z^{30}] P''(z) = 19054894203999260640645120000 = 1.905489420399926064064512 \cdot 10^{28}.

Kod programu znajduje się w pliku ex-1.wls.

Zadanie 2.

Ile jest permutacji zbioru 3030-elementowego, składających się z co najwyżej 55 cykli?

Implementacja zadania 2. z listy 4. z ćwiczeń.

P′(z)=∑n=05(ln⁡11−z)nn! P'(z) = \sum_{n=0}^5 \frac{\left( \ln \frac{1}{1-z} \right)^n}{n!}

Wynik: 30!⋅[z30]P′(z)=222444420953341570876847086387200=2.224444209533415708768470863872⋅103230! \cdot [z^{30}] P'(z) = 222444420953341570876847086387200 = 2.224444209533415708768470863872 \cdot 10^{32}

Kod programu znajduje się w pliku ex-2.wls.

Zadanie 3.

Opisując odpowiednie BGF znaleźć wariancję liczby liter aa w losowym słowie nad alfabetem {a,b,c}\{a,b,c\} długości nn.

Mówimy tutaj o BGF, czyli o funkcjach generujących dwóch zmiennych: A(z,u)=∑n,kan,kznuk. A(z,u) = \sum_{n,k} a_{n,k} z^n u^k.

Żeby móc określić taką funkcję, musimy oczywiście określić an,ka_{n,k}.
Idea: mówimy tutaj o ciągach (sekwencjach) liter {a,b,c}\{a,b,c\}. Chcemy w jakiś sposób oznaczyć litery aa jako specjalne, jako że chcemy policzyć w pewnym sensie, jaka jest szansa na natrafienie na tę literkę.
Takich słów jest (nk)⋅1k⋅2n−k\binom{n}{k} \cdot 1^k \cdot 2^{n-k} bo za każdym razem wybieramy kk liter aa oraz n−kn-k liter bb lub cc — co za tym idzie an,k=(nk)⋅2n−ka_{n,k} = \binom{n}{k} \cdot 2^{n-k}.

Wówczas A(z,u)=∑n,k(nk)⋅zn⋅2n−k⋅uk, A(z,u) = \sum_{n,k} \binom{n}{k} \cdot z^n \cdot 2^{n-k} \cdot u^k, a po przekształceniu: A(z,u)=∑n≥0zn∑k≥0(nk)uk2n−k A(z,u) = \sum_{n\ge0} z^n \sum_{k\ge0} \binom{n}{k}u^k 2^{n-k} a ze znanej równości ∑k=0n(nk)akbn−k=(a+b)n\sum_{k=0}^n \binom{n}{k} a^k b^{n-k} = (a+b)^n mamy: A(z,u)=∑n≥0zn(u+2)n. A(z,u) = \sum_{n\ge0}z^n (u + 2)^n.

Oczywiście niniejsza funkcja generująca idzie w parze z klasą kombinatoryczną A=({a,b,c},∣⋅∣,χ)\mathcal{A} = (\{a,b,c\}, |\cdot|, \chi) gdzie ∣⋅∣|\cdot| to po prostu funkcja długości słowa, a χ\chi to funkcja określająca liczbę literek aa w danym słowie — czyli oznaczamy literkę aa jako specjalną.

Żeby obliczyć wariancję, musimy uzyskać wartość oczekiwaną oraz drugi moment zmiennej losowej χ\chi.

Mamy: E⁡(χ)=[zn]dduA(z,u)∣u=1[zn]A(z,1)E⁡(χ2)=[zn]d2du2A(z,u)∣u=1[zn]A(z,1)+[zn]dduA(z,u)∣u=1[zn]A(z,1) \begin{aligned} \operatorname{E}(\chi) &= \frac{[z^n]\frac{d}{du} A(z,u) \big|_{u=1}}{[z^n]A(z,1)}\\ \operatorname{E}(\chi^2) &= \frac{[z^n]\frac{d^2}{du^2} A(z,u) \big|_{u=1}}{[z^n] A(z,1)} + \frac{[z^n]\frac{d}{du} A(z,u) \big|_{u=1}}{[z^n]A(z,1)} \end{aligned} co daje nam: Var⁡(χ)=E⁡(χ2)−(E⁡(χ))2 \operatorname{Var}(\chi) = \operatorname{E}(\chi^2) - \big(\operatorname{E}(\chi)\big)^2

Pozostaje policzyć A(z,1)A(z,1): A(z,1)=∑n≥0zn(u+2)n=∑n≥0zn3n⏟super!. A(z,1) = \sum_{n\ge0} z^n (u + 2)^n = \sum_{n\ge0} z^n \underbrace{3^n}_{\text{super!}}.

Wyniki:

Kod programu znajduje się w pliku ex-3.wls.

Zadanie 4.

Podać wariancję liczby cykli długości 33 w permutacji o 3030 elementach.

Tak jak w zadaniu poprzednim oznaczamy wszystkie cykle długości 33 jako specjalne.

Wówczas mamy klasę C=SET⁡(CYC⁡≠3(Z)+CYC⁡=3(Z)⏟oznaczone przy pomocy χ ) \mathcal{C} = \operatorname{SET}\left( \operatorname{CYC}_{\neq3}(\mathcal{Z}) + \underbrace{\operatorname{CYC}_{=3}(\mathcal{Z})}_{\text{oznaczone przy pomocy }\chi\,} \right) z funkcją generującą C(z,u)=exp⁡(∑n≥1(znn)−z33+uz33) C(z,u) = \exp\left( \sum_{n\ge1}\left( \frac{z^n}{n} \right) - \frac{z^3}{3} + \frac{uz^3}{3} \right) gdzie właśnie to uu odznacza nam te cykle długości 33, czyli nasza funkcja χ\chi dla cykli długości 33 zwraca 11, kiedy dla pozostałych 00.

Tak jak w poprzednim zadaniu potrzebujemy jeszcze C(z,1)C(z,1): C(z,1)=exp⁡(∑n≥1(znn)−z33+1⋅z33)=exp⁡(∑n≥1(znn))=exp⁡(ln⁡11−z)==11−z=∑n≥0zn C(z,1) = \exp\left( \sum_{n\ge1}\left( \frac{z^n}{n} \right) - \frac{z^3}{3} + \frac{1 \cdot z^3}{3} \right) = \exp\left( \sum_{n\ge1} \left( \frac{z^n}{n} \right) \right) = \exp\left( \ln\frac{1}{1-z} \right) =\\ = \frac{1}{1-z} = \sum_{n\ge0} z^n

Znowu, liczymy tak jak w poprzednim zadaniu wariancję: Var⁡(χ)=E⁡(χ2)−(E⁡(χ))2. \operatorname{Var}(\chi) = \operatorname{E}(\chi^2) - \big(\operatorname{E}(\chi)\big)^2.

Wyniki: E⁡(χ)={0n≤213n>2Var⁡(χ)={0n≤229n∈[3;5]13n>5 \begin{aligned} \operatorname{E}(\chi) &= \begin{cases} 0 & n \le 2\\ \frac{1}{3} & n > 2 \end{cases} \\[20pt] \operatorname{Var}(\chi) &= \begin{cases} 0 & n \le 2\\ \frac{2}{9} & n \in [3; 5]\\ \frac{1}{3} & n > 5\\ \end{cases} \end{aligned} czyli dla n=30n = 30 wariancja przyjmuje wartość 13\frac{1}{3}.

Kod programu znajduje się w pliku ex-4.wls.