\relax 
\providecommand\hyper@newdestlabel[2]{}
\providecommand\HyperFirstAtBeginDocument{\AtBeginDocument}
\HyperFirstAtBeginDocument{\ifx\hyper@anchor\@undefined
\global\let\oldcontentsline\contentsline
\gdef\contentsline#1#2#3#4{\oldcontentsline{#1}{#2}{#3}}
\global\let\oldnewlabel\newlabel
\gdef\newlabel#1#2{\newlabelxx{#1}#2}
\gdef\newlabelxx#1#2#3#4#5#6{\oldnewlabel{#1}{{#2}{#3}}}
\AtEndDocument{\ifx\hyper@anchor\@undefined
\let\contentsline\oldcontentsline
\let\newlabel\oldnewlabel
\fi}
\fi}
\global\let\hyper@last\relax 
\gdef\HyperFirstAtBeginDocument#1{#1}
\providecommand*\HyPL@Entry[1]{}
\citation{calkin}
\citation{race}
\citation{wilf}
\citation{oeis}
\citation{race}
\HyPL@Entry{0<</S/D>>}
\@writefile{toc}{\contentsline {section}{\numberline {1}Introduction}{1}{section.1}}
\@writefile{toc}{\contentsline {section}{\numberline {2}Graphs and matrices}{2}{section.2}}
\@writefile{lof}{\contentsline {figure}{\numberline {1}{\ignorespaces A tiling of a $4\times 5$ square and its representation by the $M_{4,3}$ matrix and by a sequence of words of length 3.}}{2}{figure.1}}
\newlabel{fig:Tiling}{{1}{2}{A tiling of a $4\times 5$ square and its representation by the $M_{4,3}$ matrix and by a sequence of words of length 3}{figure.1}{}}
\citation{calkin}
\citation{race}
\@writefile{lof}{\contentsline {figure}{\numberline {2}{\ignorespaces A graph and its corresponding adjacency matrix representing the ways to tile a $4\times n$ rectangle $R$. A path of length $n-1$ in the graph corresponds to a tiling of $R$.}}{3}{figure.2}}
\newlabel{fig:GraphMatrix}{{2}{3}{A graph and its corresponding adjacency matrix representing the ways to tile a $4\times n$ rectangle $R$. A path of length $n-1$ in the graph corresponds to a tiling of $R$}{figure.2}{}}
\newlabel{eq:SizeTn}{{1}{3}{Graphs and matrices}{equation.2.1}{}}
\newlabel{eq:RecDefOfAn}{{2}{3}{Graphs and matrices}{equation.2.2}{}}
\newlabel{eq:RowsInAn}{{3}{3}{Graphs and matrices}{equation.2.3}{}}
\newlabel{eq:NbrOfOnes}{{4}{3}{Graphs and matrices}{equation.2.4}{}}
\citation{calkin}
\citation{race}
\@writefile{lot}{\contentsline {table}{\numberline {1}{\ignorespaces The number of ones in $A_n$ for small values of $n$. The numbers follow the Jacobsthal sequence; see \href  {http://oeis.org/A001045}{\relax $\@@underline {\hbox {A001045}}\mathsurround \z@ $\relax }.}}{4}{table.1}}
\newlabel{table:Ones}{{1}{4}{The number of ones in $A_n$ for small values of $n$. The numbers follow the Jacobsthal sequence; see \seqnum {A001045}}{table.1}{}}
\newlabel{eq:NbrTilingsMatrixMul}{{5}{4}{Graphs and matrices}{equation.2.5}{}}
\newlabel{eq:MatrixScalarProduct}{{6}{4}{Graphs and matrices}{equation.2.6}{}}
\newlabel{eq:IteratedMatrixMul}{{7}{4}{Graphs and matrices}{equation.2.7}{}}
\newlabel{ex:ExampleCalculation}{{2}{4}{}{theorem.2}{}}
\citation{cormen}
\citation{cormen}
\@writefile{toc}{\contentsline {section}{\numberline {3}Generating the adjacency matrix $A_n$}{5}{section.3}}
\@writefile{toc}{\contentsline {subsection}{\numberline {3.1}Binary counters}{5}{subsection.3.1}}
\@writefile{lof}{\contentsline {figure}{\numberline {3}{\ignorespaces  The pseudocode for the function \texttt  {Increment\_P} that increments the vector $p$. A call of the function gives the lexicographically next word of $p$ in $T_n$. It returns true if the next word has been found and false if we have generated all words.}}{6}{figure.3}}
\newlabel{algo:Bincounter}{{3}{6}{The pseudocode for the function \texttt {Increment\_P} that increments the vector $p$. A call of the function gives the lexicographically next word of $p$ in $T_n$. It returns true if the next word has been found and false if we have generated all words}{figure.3}{}}
\@writefile{lof}{\contentsline {figure}{\numberline {4}{\ignorespaces  The function \texttt  {Increment\_P} applied to the vector $p$ of length $n=3$. The function is called 5 times, illustrated in (a)--(e), where all but the last time (e) returns true. The arrows indicate how the function flips the bits in $p$. Starting in (a) with $p$ equal to zero, we flip the last bit and return true. In (b) we see that we have to flip bits closer to the front before finding an allowed word. Similar recursive steps happen in (c) and (e).}}{6}{figure.4}}
\newlabel{fig:IncOfP}{{4}{6}{The function \texttt {Increment\_P} applied to the vector $p$ of length $n=3$. The function is called 5 times, illustrated in (a)--(e), where all but the last time (e) returns true. The arrows indicate how the function flips the bits in $p$. Starting in (a) with $p$ equal to zero, we flip the last bit and return true. In (b) we see that we have to flip bits closer to the front before finding an allowed word. Similar recursive steps happen in (c) and (e)}{figure.4}{}}
\@writefile{lot}{\contentsline {table}{\numberline {2}{\ignorespaces  The number of flips performed by \texttt  {Increment\_P} when stepping through the words of length $n$ without the pattern $\texttt  {11}$.}}{7}{table.2}}
\newlabel{table:FlipsIncrementP}{{2}{7}{The number of flips performed by \texttt {Increment\_P} when stepping through the words of length $n$ without the pattern $\texttt {11}$}{table.2}{}}
\newlabel{prop:NbrFlipsFib}{{3}{7}{}{theorem.3}{}}
\newlabel{eq:NbrFlipsFib}{{8}{7}{}{equation.3.8}{}}
\newlabel{eq:TotalNbrOfFlips}{{9}{7}{Binary counters}{equation.3.9}{}}
\@writefile{toc}{\contentsline {subsection}{\numberline {3.2}Side conditions}{8}{subsection.3.2}}
\@writefile{lof}{\contentsline {figure}{\numberline {5}{\ignorespaces  The pseudocode for the function \texttt  {Increment\_PQ} that increments the vector $q$ with the side condition $p$. It returns true if the next word has been found, and false if we have generated all words.}}{9}{figure.5}}
\newlabel{fig:IncrementWithSideCondition}{{5}{9}{The pseudocode for the function \texttt {Increment\_PQ} that increments the vector $q$ with the side condition $p$. It returns true if the next word has been found, and false if we have generated all words}{figure.5}{}}
\newlabel{eq:sumfpni}{{10}{10}{Side conditions}{equation.3.10}{}}
\@writefile{lot}{\contentsline {table}{\numberline {3}{\ignorespaces  The number of flips performed by \texttt  {Increment\_PQ} when stepping through the allowed words $q$ of length $n$ for all words $p\in T_n$.}}{10}{table.3}}
\newlabel{table:FlipsIncrementPQ}{{3}{10}{The number of flips performed by \texttt {Increment\_PQ} when stepping through the allowed words $q$ of length $n$ for all words $p\in T_n$}{table.3}{}}
\newlabel{eq:RecFlipsPerRow}{{11}{10}{}{equation.3.11}{}}
\@writefile{toc}{\contentsline {section}{\numberline {4}Matrix multiplication}{12}{section.4}}
\@writefile{toc}{\contentsline {subsection}{\numberline {4.1}Counting}{12}{subsection.4.1}}
\newlabel{ex:DefIndex}{{12}{12}{Counting}{equation.4.12}{}}
\@writefile{toc}{\contentsline {subsection}{\numberline {4.2}Detailed count}{12}{subsection.4.2}}
\@writefile{lof}{\contentsline {figure}{\numberline {6}{\ignorespaces  The pseudocode for performing the multiplication $A_n v$. The function $I_n$ is the index function from \textup  {\hbox {\mathsurround \z@ \normalfont  (\ignorespaces \ref  {ex:DefIndex}\unskip \@@italiccorr )}}. Note that no actual multiplication is performed, as all non-zero entries of $A_n$ are 1.}}{13}{figure.6}}
\newlabel{fig:MatrixMul}{{6}{13}{The pseudocode for performing the multiplication $A_n v$. The function $I_n$ is the index function from \eqref {ex:DefIndex}. Note that no actual multiplication is performed, as all non-zero entries of $A_n$ are 1}{figure.6}{}}
\@writefile{lof}{\contentsline {figure}{\numberline {7}{\ignorespaces  The pseudocode for performing the multiplication $A_n v$, where we count of the number of tilings with a specific number of large tiles. }}{14}{figure.7}}
\newlabel{fig:MatrixMulDetail}{{7}{14}{The pseudocode for performing the multiplication $A_n v$, where we count of the number of tilings with a specific number of large tiles}{figure.7}{}}
\citation{oeis}
\@writefile{toc}{\contentsline {section}{\numberline {5}Enumerations}{15}{section.5}}
\@writefile{lot}{\contentsline {table}{\numberline {4}{\ignorespaces The number of tilings of a $n\times n$ square.}}{15}{table.4}}
\newlabel{table:Enumeration}{{4}{15}{The number of tilings of a $n\times n$ square}{table.4}{}}
\bibcite{calkin}{1}
\bibcite{race}{2}
\bibcite{cormen}{3}
\bibcite{oeis}{4}
\bibcite{wilf}{5}
\@writefile{lof}{\contentsline {figure}{\numberline {8}{\ignorespaces The distribution of the number of tilings of a $23\times 23$ square with given number of $2\times 2$ squares. The $y$--axis is drawn in a logarithmic scale.}}{16}{figure.8}}
\newlabel{fig:EnumGraph}{{8}{16}{The distribution of the number of tilings of a $23\times 23$ square with given number of $2\times 2$ squares. The $y$--axis is drawn in a logarithmic scale}{figure.8}{}}
\@writefile{toc}{\contentsline {section}{\numberline {6}Acknowledgment}{16}{section.6}}