\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}

\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\begin{center}
\vskip 1cm{\LARGE\bf 
Tilings, Continued Fractions, Derangements, \\
\vskip .1in
Scramblings, and $e$
}
\vskip 1cm
\large
Barry Balof and Helen Jenne\\
Department of Mathematics\\
Whitman College\\
Walla Walla, WA 99362\\
USA\\
\href{mailto:balofba@whitman.edu}{\tt balofba@whitman.edu} \\
\href{mailto:jennehk@whitman.edu}{\tt jennehk@whitman.edu} \\
\end{center}

\vskip .2 in

\begin{abstract}
In a recent book,
Benjamin and Quinn ask about the combinatorial implications of Euler's
continued fraction
$$e = [2, (1,1),(1,2), (2,3), (3,4) ,\dots ].$$ 
In this paper, we explore those implications through two special types of permutations, namely, derangements and scramblings.  
\end{abstract}

\section{Introduction}

We will present a combinatorial interpretation for the following continued fraction expansion of $e$.  This strikingly simple continued fraction was first presented by Euler in a paper published after his death \cite{Euler}.  
\begin{equation}
e = 2 + \cfrac{1}{1+\cfrac{1}{2+\cfrac{2}{3+\cfrac{3}{4+\cfrac{4}{5+ \ddots}}}}}
\label{CFe}
\end{equation}

We will use the following notation to abbreviate continued fractions:

$$[a_0, (b_1, a_1), (b_2, a_2), \dots, (b_n. a_n)] := a_0+\cfrac{b_1}{a_1+\cfrac{b_2}{a_2+\cfrac{b_3}{\ddots+\cfrac{b_n}{a_n}}}}.$$

Our interpretation will involve interpreting the convergents of the continued fraction in terms of permutations.  Such interpretations have appeared previously in the literature.  Flajolet \cite{Fl} relates permutations, continued fractions, and special lattice paths.  Shin and Zeng \cite{SZ} use a statistical approach and $q$-analogues of secant and tangent numbers.  Our interpretation is motivated by Benjamin and Quinn's \cite{BQ} tiling approach to combinatorial proofs. 

\section{Proof of Euler's formula}

To prove Euler's continued fraction expansion of $e$, we consider the $n$th-order convergent of the continued fraction expansion of $e$:
\begin{equation}
[2, (1,1), (1,2), (2,3), (3,4), \ldots, (n-1, n)]
\label{e}
\end{equation}
We let $P_{n}$ denote the numerator and $Q_{n}$ denote the denominator of this continued fraction.  We note that the sequence of numerators ($ 2,3,8, 30, 144, 840 \dots$) appears as \seqnum{A001048} and the sequence of denominators ($1,1,3, 11, 53, 309\dots$) appears as \seqnum{A000255} in the OEIS \cite{OEIS}.  



We prove that $\lim_{n \to \infty} \frac{P_{n}}{Q_{n}} = e$, by establishing closed form formulas for these sequences.  We first need to introduce several well-known results. 

The following is a well-known fact about finite continued fractions \cite{LW}.   We adopt Lorentzen and Waadeland's notation for writing a pair of recurrences ($p_n$ and $q_n$) with the same coefficients.  

\begin{lemma}
Let $[a_0, (b_1, a_1), (b_2, a_2), \dots, (b_n. a_n)] = \frac{p_{n}}{q_{n}}$. Then
$${p_{n} \choose q_{n}} = a_{n} {p_{n-1} \choose q_{n-1}} + b_{n}{p_{n-2} \choose q_{n-2}}$$
with ${p_{-1} \choose q_{-1} } = {1 \choose 0}$ and ${p_{0} \choose q_{0} } = {a_{0} \choose 1}$. 
\end{lemma}

Recall that that a {\em derangement} of the set $\{1, 2, \dots, n \}$ is a permutation $\pi\in S_n$ such that $\pi(i) \neq i$ for all $i\in \{1, 2, \dots, n\}$. Let $d_{n}$ be the number of derangements of $\{1, 2, \ldots, n\}$.
The sequence of derangement numbers, ($1, 0, 1, 2, 9, 44, 265, \dots$)
appears as \seqnum{A000166} in the OEIS \cite{OEIS}.  The following well-known
result follows via an inclusion-exclusion argument; see Brualdi
\cite{Bru}.

\begin{lemma}
We have $d_{n} = n! \sum\limits_{k=0}^{n} \frac{(-1)^{k}}{k!}$. 
\label{lemma2}
\end{lemma}

It follows that $\frac{d_{n}}{n!} \rightarrow \frac{1}{e}$ as $n$ tends to infinity. Additionally, Lemma \ref{lemma2} leads to the recursion $d_{n} = nd_{n-1} + (-1)^{n}=(n-1)(d_{n-1}+d_{n-2})$. 

Using these facts, we obtain closed forms for the numerator and denominator of the continued fraction in equation (\ref{e}).   

\begin{lemma}
If $a_{0} =2, b_{1} =1, a_{n} = n$ for $n \geq 1$ and $b_{n} = n-1$ for $n \geq 2$, then
\begin{center}
$P_{n} = (n+1)! + n!$ and $Q_{n} = d_{n+1} + d_{n}$. 
\end{center}
\label{lemma3}
\end{lemma}
We prove both recursions in Lemma \ref{lemma3} via a quick induction using our identities.  
\begin{itemize} 
\item $P_0=2=1!+0!$; Assume that $P_k=(k+1)!+k!$ for all $k<n$.  Then 
\begin{eqnarray*}
P_n = nP_{n-1}+(n-1)P_{n-2} & = &n(n!+(n-1)!)+(n-1)((n-1)!+(n-2)!) \\
& =& n(n-1)!(n+1)+(n-1)(n-2)!(n-1+1)\\ 
& =& (n+1)! + n!
\end{eqnarray*}

\item $Q_0=1=1+0$;  Assume that $Q_k=d_{k+1}+d_k$ for all $k<n$.  Then
\begin{eqnarray*}
Q_n = nQ_{n-1}+(n-1)Q_{n-2} &=& n(d_n+d_{n-1})+(n-1)(d_{n-1}+d_{n-2}) \\
& = & d_{n+1}+d_{n}
\end{eqnarray*}



\end{itemize}

It follows that 
$$\frac{P_{n}}{Q_{n}} = \frac{(n+1)! + n!}{d_{n+1} + d_{n}} = \frac{1 + 1/(n+1)}{d_{n+1}/(n+1)! + d_{n}/(n+1)!}$$
which tends to $e$ as $n \rightarrow \infty$. 

\section{Combinatorial Interpretations}

The purpose of this section is to present combinatorial explanations for the formulas in Lemma \ref{lemma3}. To do this, we will relate Benjamin and Quinn's combinatorial interpretation of continued fractions to sets of permutations. First, we introduce Benjamin and Quinn's combinatorial interpretation. 

A {\em tiling} of an $n$-board refers to a covering of a $1 \times n$ chessboard using $1 \times 1$ tiles (called squares) and $1 \times 2$ tiles (called dominoes). 

One way to generalize tilings of an $n$-board is by stacking squares and dominoes. In these tilings, called  {\em stackable tilings}, squares may not be stacked on dominoes and any two dominoes either overlap completely or not at all. 

The number of squares and dominoes allowed on the tiles are referred to as {\em height conditions}, which we define more formally below. 

\begin{definition} [Benjamin $\&$ Quinn \cite{BQ}] 
In the context of creating a stackable tiling of an $(n+1)$-board using squares and dominoes  (and counting tiles from $0$ to $n$), we denote a set of {\em height conditions} by a list $$(a_0, (b_1, a_1), (b_2, a_2), \dots, (b_n, a_n)).$$  The height condition $a_{i}$ indicates the number of squares we may stack on the $i$th tile, and the {\em height condition} $b_{i}$ indicates the number of dominoes we may stack on tiles $(i-1, i)$.
\end{definition}

Note that we are using height conditions $b_i$ to denote the number of tiles that can cover tile $i$ and the previous tile $i-1$, and, hence, the absence of a height condition $b_0$. 
     
The numerator and denominator of a finite continued fraction have similar combinatorial interpretations - both count stackable tilings, with similar and natural height conditions. 

\begin{theorem} [Benjamin $\&$ Quinn \cite{BQ}] 

Consider the finite continued fraction $$[a_0,(b_1, a_1), (b_2, a_2), \dots (b_n, a_n)]=\frac{p_n}{q_n}$$ For $n \geq 0$, the numerator, $p_{n}$, counts the number of tilings of an $(n+1)$-board of tiles numbered 0 through $n$ with 
height conditions $$(a_{0}, (b_{1}, a_{1}), (b_{2}, a_{2}), \ldots, (b_{n}, a_{n})).$$ The denominator, $q_{n}$, counts the number of tilings of an $n$-board of tiles numbered 1 through $n$ with height conditions $$(a_{1}, (b_{2}, a_{2}), (b_{3}, a_{3}), \ldots, (b_{n}, a_{n})).$$

\label{TilingThm}
\end{theorem}

A complete proof is presented in \cite{BQ}, and depends on an inductive conditioning of whether the first tile in a tiling is a square or a domino.  Rather than repeat the proof here, we hope to elucidate Theorem \ref{TilingThm} with an example.  




\begin{example} Consider the first few terms of the continued fraction expansion of $e$:
$$2 + \cfrac{1}{1+\cfrac{1}{2+\cfrac{2}{3}}} = \frac{30}{11} \doteq 2.727272$$
We will directly count the stackable tilings for the numerator and denominator.  In the following, we will use $S$ to correspond to a stack of squares, and $D$ to a stack of dominoes.  


There are 30 stackable tilings with height conditions $(2, (1,1), (1,2), (2,3))$ which take on the following forms:  

\begin{itemize}
\item $SSSS$ There are $ 2 \cdot 1 \cdot 2 \cdot 3 = 12$ of these. 
\item $DSS$ There are $1 \cdot 2 \cdot 3 = 6$ of these. 
\item $SSD$ There are $2 \cdot 1 \cdot 2 = 4$ of these. 
\item $SDS$ There are $2 \cdot 1 \cdot 3 = 6$ of these. 
\item $DD$ There are $1 \cdot 2 = 2$ of these.
\end{itemize}

There are 11 stackable tilings with height conditions $(1, (1,2), (2,3))$ which take on the following forms:

\begin{itemize}
\item $SSS$  There are $ 1\cdot 2\cdot 3=6$ of these.
\item $SD$  There are $ 1 \cdot 2=2$ of these.
\item $DS$ There are $ 1 \cdot 3=3$ of these.
\end{itemize}

\end{example}

We look at the formulas in Lemma \ref{lemma3} in turn. 


\subsection{Combinatorial Explanation of $P_n$}

In order to explain $P_n=(n+1)!+n!$ combinatorially, it looks natural to establish a bijection between stackable tilings and a set of permutations, and this indeed leads to an explanation.  

\begin{theorem}
There is a bijection between 
\begin{itemize}
\item Stackable tilings of $(n+1)$-boards with height conditions $$[2, (1,1), (1,2), (2,3), \dots, (n-1, n)]$$
\item Permutations on $n$ and $n+1$ symbols.  
\end{itemize}

\end{theorem}

\begin{proof}
We establish our bijection by giving an explicit algorithm mapping a stackable tiling to a permutation on either $n$ or $n+1$ symbols.  We first note that of the $P_n$ stackable tilings with the given height conditions,
$n!$ of them end with a stack of dominoes, and $(n+1)!$ of them end with a stack of squares.  (A quick induction verifies this).  Thus, we will match a tiling of an $n+1$ board with a permutation on $n$ symbols if the board ends in a stack of dominoes, and with a permutation on $n+1$ symbols if the board ends in a stack of squares.  

First we consider tilings of 2-boards.  In the following, we use $S^i$ and $D^j$ to refer to stacks of $i$ squares and stacks of $j$ dominoes, respectively.  We associate:  

$$ SS \leftrightarrow (1,2)$$
$$ S^2S \leftrightarrow (2,1)$$
$$ D \leftrightarrow (1).$$

For tilings of longer boards, we look to both the last tile of the board and the previous tilings to determine which permutation to assign.  Assume, inductively, that we have assigned permutations to all boards of length less than $n+1$, and that we are now trying to assign a tiling of an $n+1$ board.  

\begin{itemize}
\item Case 1:  {\em The tiling ends with a stack of $i$ dominoes.}  Treat the last stack of dominoes as a stack of squares, so that a tiling of an $(n+1)$-board ending in a stack of $i$ dominoes is assigned the same permutation as the tiling of an $n$-board that is identical in the first $n-1$ tiles but ends in a stack of $i$ squares.
\item Case 2:  {\em The tiling ends with a stack of $i$ squares preceded by a stack of squares.}  Begin with the permutation on $n$ symbols assigned to the $n$-board that ends in a stack of squares.  Insert the symbol $n+1$ in the $i$th position from the right to get the new permutation.  Note that since $1\leq i \leq n$, the symbol $n+1$ may appear in any position but the leftmost.  
\item Case 3:  {\em The tiling ends with a stack of $i$ squares  preceded by a stack of dominoes.}  In this case, the tiling of the $n$ board consisting of the first $n$ tiles corresponds to a permutation on $n-1$ symbols, which we must augment with symbols $n$ and $n+1$.  We begin by inserting $n$ in the $i$th position from the right (and, now, this may be any legal position), and then insert $n+1$ in the leftmost position.  
\end{itemize}

The above process generates all permutations on $n$ symbols and $n+1$ symbols in running through all stackable $(n+1)$-boards with height conditions $[2, (1,1), (1,2), \dots, (n-1, n)]$.  

\end{proof}


We can use our generation rules to determine the permutations corresponding to the stackable tilings of a $3$-board: 

\begin{itemize}
\item $SSS$:  Since there is one square on the last tile, add $3$ to the permutation $(1,2)$ (which corresponds to $SS$) in the first rightmost position, giving {\bf (1,2,3)}.
\item $SSS^2$:  Similar to above, except here we add 3 in the second rightmost position, giving {\bf (1,3,2)}.
\item $S^2SS$:  Starting with $(2,1)$, we insert 3 in the first rightmost position giving {\bf (2,1,3)}.
\item $S^2SS^2$:  As above, we get {\bf (2,3,1)}.
\item $DS$: Since this tiling ends in a square with the penultimate tile a domino, we start with the permutation corresponding to just the domino, (1), add 2 in the rightmost position, giving (1,2), then add 3 on the leftmost position, giving {\bf (3,1,2)}.
\item $DS^2$:  Same as above, but here we add the 2 on the second rightmost position, resulting ultimately in {\bf (3,2,1)}.  
\item $SD$:  Since this tiling ends in a domino, we only need a permutation on 2 symbols.  We convert the domino to a square ($SS$) and look to the previous map, giving {\bf (1,2)}.
\item $S^2D$:  Again, this corresponds to the same permutation as did $S^2S$, namely {\bf (2,1)}.


\end{itemize}


We now compute a permutation associated with a larger tiling.  We first remove each tile working backwards from the right, and look for the appropriate permutation on the smallest board. Then, we build our permutation back up by adding the removed tiles.  We convert dominoes to squares where appropriate.  



\begin{align*}
&\begin{aligned} [ r l c l l ]
SSD^2S^3DS^4S^3 & \in & S_9 \\
SSD^2S^3DS^4 & \in & S_8 \\
SSD^2S^3D & \in & S_6 \\
SSD^2S^3S & \in & S_6 \\
SSD^2S^3 & \in & S_5 \\
SSD^2 & \in & S_3 \\
SSS^2 & \in & S_3 \\
SS & \in & S_2   \\
\end{aligned}
\end{align*}

\begin{align*}
&\begin{aligned} [ r l c l l ]
SS  & \to &  (1,2) \\
SSS^2 & \to & (1,{\bf 3},2) \\
SSD^2 & \to & (1,3,2) \\
SSD^2S^3 & \to & ({\bf 5},1,{\bf 4},3,2) \\
SSD^2S^3S & \to & (5,1,4,3,2,{\bf 6}) \\
SSD^2S^3D & \to & (5,1,4,3,2,6) \\
SSD^2S^3DS^4 & \to & ({\bf 8},5,1,4,{\bf 7},3,2,6) \\
SSD^2S^3DS^4S^3 & \to & (8,5,1,4,7,3,{\bf 9},2,6) \\
\end{aligned}
\end{align*}

Note that the process is reversible up to the fact that each permutation on $k$ symbols will correspond to two tilings, namely, one on a $(k-1)$-board ending in a stack of squares, and the same $k$-board where the final stack has been converted to dominoes.  Hence, we have both that 

\begin{itemize}
\item $(8,5,1,4,7,3,9,2,6) \to SSD^2S^3DS^4S^3$ (an 9-board)\

and 

\item $(8,5,1,4,7,3,9,2,6) \to  SSD^2S^3DS^4D^3 $ (a 10-board)\
\end{itemize}




\subsection{Combinatorial Explanation of $Q_n$}


In order to combinatorially explain $Q_{n} = d_{n} + d_{n-1}$, we will introduce a construction similar to a derangement.  A {\em scrambling} is a permutation $\pi\in S_n$ for which $\pi(i+1) \neq \pi(i)+1$ for all $i\in \{1,2, \dots, n-1\}$.  In the same way that one can think of a derangement as having no `fixed points,' one can think of a scrambling as having no `fixed adjacencies.'  In the following, we will use the second line of the standard two-line notation to express our permutation.  By way of example, the permutation $(2,5,4,1,3)$ is both a derangement and a scrambling (no fixed points, and no fixed left-right adjacencies).  The permutation $(1, 3, 2, 5, 4)$ is a scrambling but not a derangement (as it has the fixed point `1').  The permutation $(3,4,5,2,1)$ is a derangement but not a scrambling, as it fixes the adjacencies 3-4 and 4-5.  We will denote the set of scramblings on $n$ symbols by $s_n$.  For more on the relationship between scramblings and derangements, see Balof, Farmer, and Kawabata \cite{Balof}.  

\begin{theorem}
There is a bijection between
\begin{itemize}
\item Scramblings of $\{ 1, 2, \ldots, n+1\}$, and
\item Stackable tilings of a $n$-board with height conditions
\begin{center}
$(1, (1,2), (2,3), \ldots (n-1, n)).$
\end{center}
\end{itemize}

\end{theorem}

\begin{proof}

To establish this bijection, we present an algorithm mapping a stackable tiling of an $n$-board with the above height conditions to a scrambling on $n+1$ symbols.

Because the only tile of a $1$-board with height condition $(1)$ is a single square, and (2,1) is the only scrambling of $\{1,2\}$, the tiling $S$ corresponds to the permutation (2,1).

Given a tiling of an $n$-board, we construct the corresponding scrambling on $n+1$ symbols by adding to the scrambling associated with the tiling of the first $n-1$ or the first $n-2$ tiles, depending on whether or not the $n$-board ends in a stack of squares or a stack of dominoes. Assume that we have assigned scramblings to all boards of length less than $n$. Then
\begin{itemize}

\item Case 1: {\em The tiling ends with a stack of $i$ squares.} Beginning with the scrambling on $n$ symbols assigned to the first $n-1$ tiles of the board, we insert the symbol $n+1$ in the $i$th position, counting from the right, excluding the position that results in the adjacency $(n, n+1)$. Note that since $1 \leq i \leq n$, the symbol $n+1$ may appear in any position except to the right of $n$. Formally, we are defining a set of maps $\sigma_i: s_n \to s_{n+1}$ for $i\leq n$, each of which takes a scrambling on $n$ letters, and appends the symbol $n+1$ in the $i$th legal position from the right. 

\item Case 2: {\em The tiling ends with a stack of $i$ dominoes.} We begin with the scrambling on $n-1$ symbols assigned to the first $n-2$ tiles of the board. To obtain a scrambling on $n+1$ symbols, we must add two symbols. First, we create the adjacency $(i, i+1)$, renumbering symbols higher than $i$ so that now we have a permutation on $n$ symbols with exactly one adjacency. Next, we break the adjacency by placing the symbol $n+1$ between $i$ and $i+1$. Note that since $1 \leq i \leq n-1$, this process results in any of the $n-1$ substrings $(1, n+1, 2), (2, n+1, 3), \ldots (n-1, n+1, n)$. Formally, we are defining maps $\delta_i:s_{n-1} \to s_{n+1}$, where $\delta_i(\pi)$ replaces symbol $i$ in $\pi$ with the adjacent pair $(i, i+1)$ (and renumbers symbols higher than $i$), then introduces symbol $n+1$ between the symbols $i$ and $i+1$. 

\end{itemize}

Note that when we remove the symbol $n+1$ from a scrambling on $n+1$ symbols the resulting scrambling will either be adjacency-free or will have exactly one adjacency.  Hence, the above process generates all adjacency-free permutations on $n+1$ symbols. 

\end{proof}

We use the above maps to determine the scramblings on 3 symbols corresponding to the stackable tilings of a 2-board: 
\begin{itemize}
\item $SS$: Since there is one square on the last tile, add 3 to the permutation $(2, 1)$ in the first legal position (counting from the right), resulting in $(2,1,3)$. Therefore, $\sigma_1(\sigma_1(1))=\sigma_1(2,1)=(2,1,3).$
\item $SS^{2}$: Now we add 3 to $(2,1)$ in the second legal position. Since placing 3 to the right of 2 would result in an adjacency, we get the permutation $(3, 2, 1)$. Thus we have that $\sigma_2(\sigma_1(1))=\sigma_2(2,1)=(3,2,1).$
\item $D$: We create the adjacency $(1, 2)$ and break it with $3$, resulting in the permutation $(1, 3, 2)$. Therefore, $\delta_{1} (1) = (1, 3, 2)$. 
\end{itemize}

Next we compute permutations associated with longer tilings. 

\begin{example}
The scrambling corresponding to the tiling $SS^2SS^3S^5$ can be constructed using our maps as follows:  

\begin{align*}
&\begin{aligned} [l l l ]
SS^2SS^3S^5 & \to  \sigma_5\sigma_3\sigma_1\sigma_2\sigma_1(1) & = \sigma_5\sigma_3\sigma_1\sigma_2(2,1)\\
& & =\sigma_5\sigma_3\sigma(3,2,1)\\ 
& &  =\sigma_5\sigma_3(3,2,1,4)\\
& & =\sigma_5(3,5,2,1,4)\\
& & =(6,3,5,2,1,4).
\end{aligned}
\end{align*}

\end{example}


\begin{example}
Consider the tiling $S S D S^{4} D^{2}$. We see that the corresponding scrambling in $s_{8}$ is

\begin{align*}
&\begin{aligned}
SSDS^4D^2  & \to  \delta_2\sigma_4\delta_1\sigma_1\sigma_1(1) & = &&\delta_2\sigma_4\delta_1\sigma_1(2,1)\\
& & =& &\delta_2\sigma_4\delta_1(2,1,3)\\ 
& &  =& &\delta_2\sigma_4(3,{\bf 1,5,2},4)\\
& & = &&\delta_2(3,6,1,5,2,4)\\
& & = &&(4,7,1,6,{\bf 2,8,3},5)
\end{aligned}
\end{align*}

\end{example}

Finally, we give an example of how to reverse this algorithm. 

\begin{example}
Given the permutation (6,2,5,3,1,4), we start by observing that 6 is in the the fifth legal position from the right. Thus, our tiling ends in a stack of five squares.  

Now we remove 6 from the permutation to get (2,5,3,1,4). We see that 5 is breaking up the adjacency $2-3$ which indicates that there is a stack of two dominoes on the third and fourth tiles. 

We remove 5 from the permutation, collapse the adjacency 2-3, and renumber to get the permutation (2,1,3).   The element 3 is in the rightmost position, so there is a single square on the second tile.  Removing 3 gives the permutation (2,1), which also corresponds to a single square. In summary,
\begin{center}
\begin{tabular}{ c c c c c c c c c }
(6,2,5,3,1,3) & $\rightarrow$ & (2,5,3,1,4) & $\rightarrow$ & (2,1,3) & $\rightarrow$ & (2,1)  \\
$S^5$ & $\rightarrow$ & $D^2S^5$ & $\rightarrow$ & $SD^2S^5$ & $\rightarrow$ & $SSD^2S^5$ \\ 
\end{tabular}
\end{center}
$\hfill \square$
\end{example}

We have combinatorially shown that there are $Q_{n} = |s_{n+1}|$ stackable tilings with height conditions $(1, (1,2), (2,3), \dots, (n-1, n))$.  It remains to count the number of scramblings in terms of the number of derangements. The following result is well-known, see Chapter 6 in Brualdi \cite{Bru}; a bijective proof using permutation statistics is given by Clarke, Han, and Zeng \cite{CHZ}.

\begin{lemma}
$$|s_{n+1}|=d_{n+1}+d_{n}$$
\end{lemma}

This concludes our combinatorial explanation of the formula $Q_{n} = d_{n+1}+d_{n}$. 

\section{Conclusion}

We have presented a combinatorial interpretation of the continued fraction representation of $e$ given in equation (\ref{CFe}).

There are several other continued fraction representations for $e$, namely the representation
$$e=[2, (1,1), (1,1), (1,2), (1,1), (1,1), (1,4), (1,1), (1,1), (1,6), \dots]$$
and the representation

$$e=[1, (2,1), (1,6), (1,10), (1,14), (1,18), \dots]$$

There may be interpretations similar to ours that give rise to other combinatorial explanations for $e$.  

\section{Acknowledgements}

We would like to thank the editor and the anonymous referee for their
numerous helpful suggestions and, in particular, for guidance in
restructuring the paper from an earlier form.

\begin{thebibliography}{9}

\bibitem{Balof}
B. Balof, E. Farmer, and J. Kawabata, The link between scrambling
numbers and derangements, Rose-Hulman Technical Report MS TR (1997),
97--02.

\bibitem{BQ}
A. T. Benjamin and J. J. Quinn, {\em Proofs that Really Count:  The Art
of Combinatorial Proof,} Mathematical Association of America, 2003.

\bibitem{Bru}
R. A. Brualdi, {\em Introductory Combinatorics,}  5th ed., Prentice
Hall, 2009.

\bibitem{CHZ}
R. J. Clarke, G. N. Han, and J. Zeng, A combinatorial interpretation of
the Seidel generation of $q$-derangement numbers, {\em Ann. Comb.} {\bf
1} (1997), 313--327.

\bibitem{Euler}
L. Euler, Observationes circa fractiones continuas, {\em Opera Omnia}:
Series 1 {\bf 16}, Springer, 1933, pp.\ 139--161.

\bibitem{Fl}
P. Flajolet, Combinatorial aspects of continued fractions, {\em
Discrete Math.} {\bf 32} (1980), 125--161.

\bibitem{LW} 
L. Lorentzen, H. Waadeland,  {\em Continued Fractions with Applications,} Stud. Comput. Math. {\bf 3} North-Holland, 1992. 
 
 \bibitem{OEIS}
N. J. A. Sloane, The Online Encyclopedia of Integer Sequences,
\url{http://oeis.org}.

\bibitem{SZ}
H. Shin and J. Zeng,
The $q$-tangent and $q$-secant numbers via continued fractions,
{\it European J. Combin.} {\bf 33} (2010), 1689--1705.

\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}:
Primary 05A05; Secondary 05A15, 05B45.

\noindent \emph{Keywords: } 
chessboard tiling, continued fraction, linear recurrence, derangement,
permutation combinatorics.  

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A000166},
\seqnum{A000255}, and
\seqnum{A001048}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received October 3 2013;
revised versions received  December 2 2013; January 6 2014.
Published in {\it Journal of Integer Sequences}, January 6 2014.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}