Tilings, Continued Fractions, Derangements, Scramblings, and e

Barry Balof and Helen Jenne Department of Mathematics Whitman College Walla Walla, WA 99362 USA

                  balofba@whitman.edu
                  jennehk@whitman.edu

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), …].

In this paper, we explore those implications through two special types of permutations, namely, derangements and scramblings.

1 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 [5].

e = 2 + \frac{1}{1 + \frac{1}{2 + \frac{2}{3 + \frac{3}{4 + \frac{4}{5 + ...}}}}}  (1)

We will use the following notation to abbreviate continued fractions:

[a_{0}, (b_{1}, a_{1}), (b_{2}, a_{2}), …, (b_{n}.a_{n})] := a_{0} + \frac{b_{1}}{a_{1} + \frac{b_{2}}{a_{2} + \frac{b_{3}}{... + \frac{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 [6] relates permutations, continued fractions, and special lattice paths. Shin and Zeng [9] use a statistical approach and q-analogues of secant and tangent numbers. Our interpretation is motivated by Benjamin and Quinn’s [2] tiling approach to combinatorial proofs.

2 Proof of Euler’s formula

To prove Euler’s continued fraction expansion of e, we consider the nth-order convergent of the continued fraction expansion of e:

[2, (1, 1), (1, 2), (2, 3), (3, 4), …, (n − 1, n)]  (2)

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 …) appears as \underline{A001048} and the sequence of denominators (1, 1, 3, 11, 53, 309 …) appears as \underline{A000255} in the OEIS [8].

We prove that lim_{n→∞} \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 [7]. We adopt Lorentzen and Waadeland’s notation for writing a pair of recurrences (p_{n} and q_{n}) with the same coefficients.

Lemma 1. Let [a_{0}, (b_{1}, a_{1}), (b_{2}, a_{2}), …, (b_{n}.a_{n})] = \frac{p_{n}}{q_{n}}. Then

\binom{p_{n}}{q_{n}} = a_{n}\binom{p_{n−1}}{q_{n−1}} + b_{n}\binom{p_{n−2}}{q_{n−2}}

with \binom{p_{−1}}{q_{−1}} = \binom{1}{0} and \binom{p_{0}}{q_{0}} = \binom{a_{0}}{1}.

Recall that that a derangement of the set {1, 2, …, n} is a permutation π ∈ S_{n} such that π(i) ≠ i for all i ∈ {1, 2, …, n}. Let d_{n} be the number of derangements of {1, 2, …, n}. The sequence of derangement numbers, (1, 0, 1, 2, 9, 44, 265, …) appears as \underline{A000166} in the OEIS [8]. The following well-known result follows via an inclusion-exclusion argument; see Brualdi [3].

Lemma 2. We have d_{n} = n! ∑_{k=0}^{n} \frac{(−1)^{k}}{k!} .

It follows that \frac{d_{n}}{n!} → \frac{1}{e} as n tends to infinity. Additionally, Lemma 2 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 (2).

Lemma 3. If a_{0} = 2, b_{1} = 1, a_{n} = n for n ≥ 1 and b_{n} = n − 1 for n ≥ 2, then

P_{n} = (n + 1)! + n! and Q_{n} = d_{n+1} + d_{n}.

We prove both recursions in Lemma 3 via a quick induction using our identities.

• P_{0} = 2 = 1! + 0!; Assume that P_{k} = (k + 1)! + k! for all k < n. Then

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!

• Q_{0} = 1 = 1 + 0; Assume that Q_{k} = d_{k+1} + d_{k} for all k < n. Then

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}

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 → ∞.

3 Combinatorial Interpretations

The purpose of this section is to present combinatorial explanations for the formulas in Lemma 3. 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 tiling of an n-board refers to a covering of a 1 × n chessboard using 1 × 1 tiles (called squares) and 1 × 2 tiles (called dominoes).

One way to generalize tilings of an n-board is by stacking squares and dominoes. In these tilings, called 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 height conditions, which we define more formally below.

Definition 4 (Benjamin & Quinn [2]). 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 height conditions by a list

(a_{0}, (b_{1}, a_{1}), (b_{2}, a_{2}), …, (b_{n}, a_{n})).

The height condition a_{i} indicates the number of squares we may stack on the ith tile, and the height condition b_{i} indicates the number of dominoes we may stack on tiles (i − 1, i).

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.

Theorem 5 (Benjamin & Quinn [2]). Consider the finite continued fraction

[a_{0}, (b_{1}, a_{1}), (b_{2}, a_{2}), … (b_{n}, a_{n})] = \frac{p_{n}}{q_{n}}

For n ≥ 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}), …, (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}), …, (b_{n}, a_{n})).

A complete proof is presented in [2], 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 5 with an example.

Example 6. Consider the first few terms of the continued fraction expansion of e:

2 + \frac{1}{1 + \frac{1}{2 + \frac{2}{3}}} = \frac{30}{11} ≐ 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:

• SSSS There are 2 · 1 · 2 · 3 = 12 of these.

• DSS There are 1 · 2 · 3 = 6 of these.

• SSD There are 2 · 1 · 2 = 4 of these.

• SDS There are 2 · 1 · 3 = 6 of these.

• DD There are 1 · 2 = 2 of these.

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

• SSS There are 1 · 2 · 3 = 6 of these.

• SD There are 1 · 2 = 2 of these.

• DS There are 1 · 3 = 3 of these.

We look at the formulas in Lemma 3 in turn.

3.1 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.

Theorem 7. There is a bijection between

• Stackable tilings of (n + 1)-boards with height conditions

[2, (1, 1), (1, 2), (2, 3), …, (n − 1, n)]

• Permutations on n and n + 1 symbols.

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 ↔ (1, 2)
S^{2}S ↔ (2, 1)
D ↔ (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.

• Case 1: 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.

• Case 2: 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 ith position from the right to get the new permutation. Note that since 1 ≤ i ≤ n, the symbol n + 1 may appear in any position but the leftmost.

• Case 3: 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 ith position from the right (and, now, this may be any legal position), and then insert n + 1 in the leftmost position.

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), …, (n − 1, n)].

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

• 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 (1,2,3).

• SSS^{2}: Similar to above, except here we add 3 in the second rightmost position, giving (1,3,2).

• S^{2}SS: Starting with (2, 1), we insert 3 in the first rightmost position giving (2,1,3).

• S^{2}SS^{2}: As above, we get (2,3,1).

• 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 (3,1,2).

• DS^{2}: Same as above, but here we add the 2 on the second rightmost position, resulting ultimately in (3,2,1).

• 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 (1,2).

• S^{2}D: Again, this corresponds to the same permutation as did S^{2}S, namely (2,1).

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{aligned}SSD^{2}S^{3}DS^{4}S^{3} & ∈ & S_{9} \\ SSD^{2}S^{3}DS^{4} & ∈ & S_{8} \\ SSD^{2}S^{3}D & ∈ & S_{6} \\ SSD^{2}S^{3}S & ∈ & S_{6} \\ SSD^{2}S^{3} & ∈ & S_{5} \\ SSD^{2} & ∈ & S_{3} \\ SSS^{2} & ∈ & S_{3} \\ SS & ∈ & S_{2} \end{aligned}

\begin{aligned}SS & → & (1, 2) \\ SSS^{2} & → & (1, 3, 2) \\ SSD^{2} & → & (1, 3, 2) \\ SSD^{2}S^{3} & → & (5, 1, 4, 3, 2) \\ SSD^{2}S^{3}S & → & (5, 1, 4, 3, 2, 6) \\ SSD^{2}S^{3}D & → & (5, 1, 4, 3, 2, 6) \\ SSD^{2}S^{3}DS^{4} & → & (8, 5, 1, 4, 7, 3, 2, 6) \\ SSD^{2}S^{3}DS^{4}S^{3} & → & (8, 5, 1, 4, 7, 3, 9, 2, 6) \end{aligned}

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

• (8, 5, 1, 4, 7, 3, 9, 2, 6) → SSD^{2}S^{3}DS^{4}S^{3} (an 9-board)

and

• (8, 5, 1, 4, 7, 3, 9, 2, 6) → SSD^{2}S^{3}DS^{4}D^{3} (a 10-board)

3.2 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 scrambling is a permutation π ∈ S_{n} for which π(i + 1) ≠ π(i) + 1 for all i ∈ {1, 2, …, 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 [1].

Theorem 8. There is a bijection between

• Scramblings of {1, 2, …, n + 1}, and

• Stackable tilings of a n-board with height conditions

(1, (1, 2), (2, 3), … (n − 1, n)).

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

• Case 1: 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 ith position, counting from the right, excluding the position that results in the adjacency (n, n + 1). Note that since 1 ≤ i ≤ n, the symbol n + 1 may appear in any position except to the right of n. Formally, we are defining a set of maps σ_{i} : s_{n} → s_{n+1} for i ≤ n, each of which takes a scrambling on n letters, and appends the symbol n + 1 in the ith legal position from the right.

• Case 2: 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 ≤ i ≤ n − 1, this process results in any of the n − 1 substrings (1, n + 1, 2), (2, n + 1, 3), … (n − 1, n + 1, n). Formally, we are defining maps δ_{i} : s_{n−1} → s_{n+1}, where δ_{i}(π) replaces symbol i in π 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.

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.

We use the above maps to determine the scramblings on 3 symbols corresponding to the stackable tilings of a 2-board:

• 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, σ_{1}(σ_{1}(1)) = σ_{1}(2, 1) = (2, 1, 3).

• 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 σ_{2}(σ_{1}(1)) = σ_{2}(2, 1) = (3, 2, 1).

• D: We create the adjacency (1, 2) and break it with 3, resulting in the permutation (1, 3, 2). Therefore, δ_{1}(1) = (1, 3, 2).

Next we compute permutations associated with longer tilings.

Example 9. The scrambling corresponding to the tiling SS^{2}SS^{3}S^{5} can be constructed using our maps as follows:

SS^{2}SS^{3}S^{5} → σ_{5}σ_{3}σ_{1}σ_{2}σ_{1}(1) = σ_{5}σ_{3}σ_{1}σ_{2}(2, 1)
= σ_{5}σ_{3}σ(3, 2, 1)
= σ_{5}σ_{3}(3, 2, 1, 4)
= σ_{5}(3, 5, 2, 1, 4)
= (6, 3, 5, 2, 1, 4).

Example 10. Consider the tiling SSDS^{4}D^{2}. We see that the corresponding scrambling in s_{8} is

SSDS^{4}D^{2} → δ_{2}σ_{4}δ_{1}σ_{1}σ_{1}(1) =  δ_{2}σ_{4}δ_{1}σ_{1}(2, 1)
=  δ_{2}σ_{4}δ_{1}(2, 1, 3)
= δ_{2}σ_{4}(3, 1, 5, 2, 4)
=  δ_{2}(3, 6, 1, 5, 2, 4)
= (4, 7, 1, 6, 2, 8, 3, 5)

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

Example 11. 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{aligned}(6,2,5,3,1,3) & → & (2,5,3,1,4) & → & (2,1,3) & → & (2,1) \\ S^{5} & → & D^{2}S^{5} & → & SD^{2}S^{5} & → & SSD^{2}S^{5} \end{aligned}

□

We have combinatorially shown that there are Q_{n} = |s_{n+1}| stackable tilings with height conditions (1, (1, 2), (2, 3), …, (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 [3]; a bijective proof using permutation statistics is given by Clarke, Han, and Zeng [4].

Lemma 12.

|s_{n+1}| = d_{n+1} + d_{n}

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

4 Conclusion

We have presented a combinatorial interpretation of the continued fraction representation of e given in equation (1).

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), …]

and the representation

e = [1, (2, 1), (1, 6), (1, 10), (1, 14), (1, 18), …]

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

5 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.

References

[1] B. Balof, E. Farmer, and J. Kawabata, The link between scrambling numbers and derangements, Rose-Hulman Technical Report MS TR (1997), 97–02.

[2] A. T. Benjamin and J. J. Quinn, Proofs that Really Count: The Art of Combinatorial Proof, Mathematical Association of America, 2003.

[3] R. A. Brualdi, Introductory Combinatorics, 5th ed., Prentice Hall, 2009.

[4] R. J. Clarke, G. N. Han, and J. Zeng, A combinatorial interpretation of the Seidel generation of q-derangement numbers, Ann. Comb. 1 (1997), 313–327.

[5] L. Euler, Observationes circa fractiones continuas, Opera Omnia: Series 1 16, Springer, 1933, pp. 139–161.

[6] P. Flajolet, Combinatorial aspects of continued fractions, Discrete Math. 32 (1980), 125– 161.

[7] L. Lorentzen, H. Waadeland, Continued Fractions with Applications, Stud. Comput. Math. 3 North-Holland, 1992.

[8] N. J. A. Sloane, The Online Encyclopedia of Integer Sequences, http://oeis.org.

[9] H. Shin and J. Zeng, The q-tangent and q-secant numbers via continued fractions, European J. Combin. 33 (2010), 1689–1705.

2010 Mathematics Subject Classification: Primary 05A05; Secondary 05A15, 05B45. Keywords: chessboard tiling, continued fraction, linear recurrence, derangement, permutation combinatorics.

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

Received October 3 2013; revised versions received December 2 2013; January 6 2014. Published in Journal of Integer Sequences, January 6 2014.

Return to Journal of Integer Sequences home page.