Combinatorical and Algebraic Structures Seminar

Session details

Date: 13.11.2007
Speaker: Karel Klouda, FJFI, České vysoké učení technické
Title: Sdružená distribuce součtu číslic pro ``greedy'' a ``lazy'' Fibonacciho reprezentace
Abstract: Pro každé přirozené číslo $n$ existuje alespoň jedna reprezentace pomocí součtů Fibonacciho čísel $F_2, F_3, \ldots$ tvaru $n = \sum_{k \geq 2} \epsilon_k(n) F_k$, kde $\epsilon_k(n) \in \{0,1\}, k \geq 2$. Takových reprezentací může existovat více, my se budeme zajímat pouze o tu, která je lexikograficky největší, tj. \emph{greedy} reprezentace získaná hladovým algoritmem, a o tu, která je lexikograficky nejmenší, tzv. \emph{lazy} reprezentace. Ukážeme, že funkce součtu číslic, $s_g(n) = \sum_{k \geq 2} \epsilon^g_k(n)$ pro greedy a $s_l(n) = \sum_{k \geq 2} \epsilon^l_k(n)$ pro lazy reprezentaci, mohou být nahlíženy jako dvourozměrná náhodná veličina která je asymptoticky normální s kovariantní maticí $\left(% \begin{array}{cc} 1 & C \\ C & 1 \\ \end{array}% \right)$, kde $C = 9 - 5\alpha \thickapprox 0.90983, \alpha = \frac{1 + \sqrt{5}}{2}$.

Return to index.