talk/rhcgraycodesgen.tex

   1 \begin{itemize}
   2 \item Algorithm~\footnote{
   3 A.~J.~van Zanten and I.~N. Suparta.
   4 \newblock Totally balanced and exponentially balanced gray codes.
   5  {\em Discrete Analysis and Operational Research}, 11:81--98, 2004.}:
   6 inductive construction of $n$-bits Gray code given a $n-2$-bit Gray code
   7 \item
   8 \emph{
   9 Let $l$ be an even positive integer. Find
  10 $u_1, u_2, \dots , u_{l-2}, v$ (maybe empty) subsequences of $S_{n-2}$
  11 such that $S_{n-2}$ is the concatenation of
  12 $
  13 s_{i_1}, u_0, s_{i_2}, u_1, s_{i_3}, u_2, . . . , s_{i_l-1}, u_{l-2}, s_{i_l}, v
  14 $
  15 where $i_1 = 1$, $i_2 = 2$, and $u_0 = \emptyset$ (the empty sequence).
  16 }
  17 \item $\leadsto \#_n = \sum_{l'=1}^{2^{n-3}} {2^{n-2}-2 \choose 2l'-2}$ distinct
  18   $u$ subsequences
  19 \begin{tabular}{|l|l|l|l|l|l|l|l|l|l|}
  20 \hline
  21 $n$ & 4&  5 & 6 & 7 & 8  \\
  22 \hline
  23 $\#_n$ &
  24 1& 31 & 8191 & 5.3e8 & 2.3e18 \\
  25 \hline
  26 $\#'_n$ &
  27 1 & 15 & 3003 & 1.4e8 & 4.5e17  \\
  28 \hline
  29 \end{tabular}
  30 \item A first simplification $\leadsto$ $\#'_n$
  31 \end{itemize}
  32