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.
last update: 27.9.2007, webmaster: Petr Ambrož