On Sequences G_{n} Satisfying G_{n} = (d + 2)G_{n−1} − G_{n−2}

Ricky X. F. Chen Center for Combinatorics LPMC Nankai University Tianjin, 300071 P. R. China

             ricky chen@mail.nankai.edu.cn

Louis W. Shapiro^{1} Howard University Washington, DC 20059 USA

                  lshapiro@Howard.edu

Abstract

In this note, we study a class of sequences G_{n} satisfying G_{n} = (d + 2)G_{n−1} − G_{n−2}. Note that the Fibonacci numbers G_{n} = F_{2n}, n > 1 and G_{n} = F_{2n+1}, n > 0 occur when d = 1 with suitable initial conditions. We present a general interpretation for this class of sequences in terms of ordered trees which we count by nodes and outdegrees. Further more, several other related integer sequences are also studied.

1 Introduction

In this note, we study a class of sequences G_{n} satisfying G_{n} = (d + 2)G_{n−1} − G_{n−2}. Note that the Fibonacci numbers G_{n} = F_{2n}, n > 1 and G_{n} = F_{2n+1}, n > 0 occur when d = 1 with suitable initial conditions. We present a general interpretation for this class of sequences in terms of ordered trees which we count by nodes and outdegrees.

1The second author is partially supported by NSF grant HRD 0401697.

A node is a non-root vertex which is not a leaf. A skinny tree is an ordered tree which has at most one node on each level, where the level of a vertex is the number of edges between it and the root. If we also mark a vertex at the bottom level, the skinny tree will be called augmented, and the special vertex will be called a marked leaf. This is a model of a process where at each stage exactly one choice is made. This could be choosing a college, a spouse, a job, and so on or just taking a multiple choice test. This problem gives rise to new interpretations for many integer sequences in Sloane’s Encyclopedia [3], such as sequences \underline{A030267}, \underline{A038731}, and \underline{A000045} (the Fibonacci numbers). We would like to propose this tree representation even though these integer sequences have been interpreted by other combinatorial structures. We will also present some bijections between skinny trees and these other combinatorial structures.

This paper is organized as follows. In Section 2, we consider the sequences G_{n} with G_{0} = 1, G_{1} = 1. We will show that these sequences count the number of skinny trees in which the outdegree of each vertex is multiple of d for all d ≥ 1. We then study the sequences G_{n} when d = 1 and 2 in greater detail. In Section 3, we consider the sequences G_{n} with G_{0} = 1, G_{1} = d. Most of results in this section are in parallel with those in section 2. In the last section, we consider the average height of skinny trees, and other asymptotic results.

2 Sequences with G_{0} = 1, G_{1} = 1

In this section, we first count the number of skinny trees in which the outdegree of each vertex is multiple of d for all d ≥ 1. We will show in a combinatorial way that the sequences G_{n} with G_{0} = 1, G_{1} = 1 actually count this kind of skinny trees. Next, we will study some properties of the sequences G_{n} when d = 1 and 2.

For the sake of convenience, we will abbreviate skinny tree to ST and augmented skinny tree to AST. The set of all skinny trees (augmented skinny trees, resp.) will be denoted as 𝕊𝕋 (𝔸𝕊𝕋, resp.). A skinny tree (augmented skinny tree, resp.) of height one will be called a small ST (small AST, resp.). The Fibonacci sequence F_{n} used here satisfies

\frac{z}{1 − z − z^{2}} = F_{0} + F_{1}z + F_{2}z^{2} + ⋯ = z + z^{2} + 2z^{3} + 3z^{4} + 5z^{5} + · · · .

We also use the fact that

\frac{z}{1 − 3z + z^{2}} = ∑_{n≥0} F_{2n+2}z^{n+1}.

Theorem 1. The generating function for the number of skinny trees in which the outdegree of each vertex is multiple of d is denoted by S_{d} (z) and satisfies the equation

S_{d}(z) = ∑_{T ∈𝕊𝕋} z^{#edges of T} = \frac{1 − (d + 1)z^{d}}{1 − (d + 2)z^{d} + z^{2d}} .

Proof. Consider the outdegree of the root. If the root has no children, then its contribution is 1; If the root has outdegree k ≥ d and d|k but no grandchildren, its contribution to the generating function is z^{k}, otherwise its contribution is kz^{k}(S_{d}(z) − 1). Hence

S_{d}(z) = 1 + ∑_{k≥d,d|k} z^{k} + ∑_{k≥d,d|k} kz^{k}(S_{d}(z) − 1).

Solving for S_{d}(z) we obtain

S_{d}(z) = \frac{1 − (d + 1)z^{d}}{1 − (d + 2)z^{d} + z^{2d}} .

Let

S_{d}(z) = \frac{1 − (d + 1)z^{d}}{1 − (d + 2)z^{d} + z^{2d}} = ∑_{n≥0} S_{d,n}z^{nd}.

From the theory of rational generating functions [2], we can obtain the following theorem. However, we will give a combinatorial proof.

Theorem 2. The sequences S_{d,n} satisfy S_{d,n} = (d + 2)S_{d,n−1} − S_{d,n−2} and S_{d,0} = 1, S_{d,1} = 1.

Proof. We count the number of skinny trees in which the outdegree of each vertex is multiple of d ≥ 1 (denoted by ST d) with dn edges. First note that there are just dS_{d,n−1} ST d’s with dn edges when the degree of the root is d.

For the ST d’s with dn edges where the degree of the root is larger than d, we can construct these trees by adding d leaves to the root of ST d’s with dn − d edges. These d leaves can be added to the root on the left or the right of the existing tree. We get a total number of 2S_{d,n−1} trees this way but we have over counted a bit. The trees that are counted twice are those which could have resulted from either type of addition of edges and there are S_{d,n−2} such trees. Hence the exact number of ST d’s with dn edges is (d + 2)S_{d,n−1} − S_{d,n−2}. So,

S_{d,n} = (d + 2)S_{d,n−1} − S_{d,n−2}, for n ≥ 2.

The initial conditions S_{d,0} = 1, S_{d,1} = 1 are obvious. This completes the proof.

Note Theorem 2 implies G_{n} = S_{d,n} for G_{n} satisfying G_{0} = 1, G_{1} = 1. From Theorem 1, we obtain the following corollary.

Corollary 3. The number of ST ’s with n edges is F_{2n−1} for n ≥ 1.

Proof. Taking d = 1, we have

∑_{n≥0} S_{1,n}z^{n} = \frac{1 − 2z}{1 − 3z + z^{2}} = 1 + \frac{z − z^{2}}{1 − 3z + z^{2}} .

For n ≥ 1, the coefficient of z^{n} is F_{2n} − F_{2n−2} = F_{2n−1}. This completes the proof.

Proposition 4. The number of ST ’s with n + 1 edges and k (k ≥ 0) nodes is \binom{n+k}{2k}.

Proof. We can build any ST with k nodes and n+1 edges as follows. Start with a path with k + 1 edges. We then have n + 1 − (k + 1) = n − k edges left to distribute. At each level other than the bottom, the remaining edges go either to the left or the right of the path. At the bottom level, we just attach the edges. This is equivalent to putting n − k balls into 2k + 1 boxes with repetition allowed, thus we have

\binom{(2k + 1) + (n − k) − 1}{n − k} = \binom{n + k}{2k}

possibilities.

Summing over 0 ≤ k ≤ n, we can get the total number of ST ’s with n + 1 edges, which leads to the following famous Fibonacci identity [1].

Corollary 5.

F_{2n+1} = ∑_{k=0}^{n} \binom{n + k}{2k}, for n ≥ 0.

More generally, we have the following proposition.

Proposition 6. The sequences S_{d,n} satisfy

S_{d,n+1} = ∑_{k=0}^{n} \binom{n + k}{2k}d^{k}.

Proof. We can construct a ST d with dn+d edges from a ST with n+1 edges by subdividing each vertex (except the root) into d vertices. If the vertex is a node, it will be subdivided into a new node and d − 1 leaves; Otherwise, d leaves. But note that if the ST has k nodes for each subdivided node one of the newly created vertices becomes the new node while the rest become leaves. If the tree has height k this gives \binom{n+k}{2k}d^{k} possibilities. Summing over 0 ≤ k ≤ n, we will obtain the total number of ST d’s with dn + d edges. Hence

S_{d,n+1} = ∑_{k=0}^{n} \binom{n + k}{2k}d^{k}.

The Fibonacci sequences (F_{2n})_{n≥1} and (F_{2n+1})_{n≥0} have many combinatorial interpretations. For instance in van Lint and Wilson’s book [4], they propose a problem counting the lattice paths on X-Y plane from the origin (0, 0) to the line x + y = n (n ≥ 0) using as possible steps (1, 0) (horizontal step) and (0, p) (vertical step), where p can be any positive integer. It is known that F_{2n+1} is the number of possible such paths. We show this via a bijection with 𝕊𝕋 in Theorem 7. Figure 1. presents an example to illustrate the bijection.

Theorem 7. There is a bijection between ST ’s with n + 1 edges and lattice paths ending on x + y = n using steps (1, 0) and (0, p), where p can be any positive integer.

Proof. Given a ST with n + 1 edges, we construct a lattice path from (0, 0) as follows. Read the edges level by level starting at the top level just below the root. If there are h edges to the left of the node on the present level, these h edges correspond to h consecutive horizontal steps; The remaining v edges on the level correspond to a vertical step (0, v). At the bottom level there are just m edges and no node, these correspond to m − 1 consecutive horizontal steps.

To recover the ST from a lattice path, we read the lattice path from (0, 0) step by step until the last vertical step and start a new level of ST right after each vertical step. If there are h consecutive horizontal steps between the present vertical step and the next vertical step (0, v), then the new starting level consists of h + v edges and the (h + 1)-th edge is the edge leading to the node of the new level. Finally, suppose there are m − 1 horizontal steps after the last vertical step, then the bottom level of the ST has m edges. In this way, we eventually obtain a ST with n + 1 edges.

[figure: x; y; x+y=8]

Figure 1. A ST with 9 edges and its corresponding lattice path.

When d = 2, the first few terms of S_{2}(z) = ∑_{n≥0} S_{2,n}z^{2n} are

S_{2}(z) = 1 + z^{2} + 3z^{4} + 11z^{6} + 41z^{8} + 153z^{10} + 571z^{12} + · · · .

There are many interesting properties of this S_{2,n} sequence (see [4, p.292] and seqnumA001835). For instance, S_{2,n} is the number of ways of packing a 3 × 2(n − 1) rectangle with dominoes (by David Singmaster \underline{A001835}); Or equivalently the number of perfect matchings of the P_{3} × P_{2(n−1)} lattice graph (by Emeric Deutsch \underline{A001835}); also S_{2,n}(n) = S(n − 1, 4) − S(n − 2, 4) where the S(n, x) = U(n, x/2) and the U(n, x) are the Chebyshev polynomials of the second kind (see \underline{A001835}), etc.

Here we present a bijection between ST 2’s with 2n edges and tilings of a 3 × 2(n − 1) board with dominoes, horizontal dominoes and vertical dominoes (for an illustration see Figure 2.). To start, some obvious properties about the tilings of a 3 × 2(n − 1) board with dominoes are mentioned here.

Proposition 8. There are an even number of vertical dominoes in every tiling. From left to right where the vertical dominoes are partitioned into consecutive pairs, the vertical dominoes in a pair are parallel and justified. And the distance between any two consecutive vertical dominoes is even.

Theorem 9. There is a bijection between ST 2’s with 2n edges and tilings of a 3 × 2(n − 1) board with dominoes.

Proof. We will use a standard numbering where the leftmost bottom square is labelled (1, 1) and the rightmost top square is labelled (2n, 3). The whole 3 × 2n board will be denoted by < (1, 1), (2n, 3) >.

Given a ST 2, suppose that level 1 has 2l edges. Number the vertices from 1 to 2l going from left to right. If the node is vertex 2p − 1, we tile squares (2p − 1, 1) and (2p − 1, 2) with a red vertical domino and tile the squares (2l, 1) and (2l, 2) with a green vertical domino. Dually if the node is vertex 2p, we tile the squares (2p − 1, 2) and (2p − 1, 3) with a red vertical domino and tile squares (2l, 2) and (2l, 3) with a green vertical domino. (These rules are guided by Proposition 8.) In other words, if the node number is odd, we put in the pair of vertical dominoes on the bottom. If the node number is even, we put in the pair of vertical dominoes towards the top. We then tile the remainder of the < (1, 1), (2l, 3) >-board completely with horizontal dominoes. In the same manner, each level (except the bottom level) of the ST 2 corresponds to a closed subboard. At the bottom level, tile the remaining subboard of the < (1, 1), (2(n−1), 3) >-board completely with horizontal dominoes. If there is but one pair of vertices on the bottom level, then we add nothing. In each case we obtain a tiling of the 3 × 2(n − 1) board.

To recover the ST 2 from a given tiling, we first color the vertical dominoes alternately with red and green colors. From Proposition 8, the last vertical domino must be a green one. Suppose that the subboard ended with the first green vertical domino yields a < (1, 1), (2l, 3) >-board. If the red vertical domino in this subboard covers squares (2p − 1, 1) and (2p − 1, 2), then level 1 of the ST 2 has 2l edges so that the node is the vertex 2p − 1. If the red vertical domino in this subboard covers squares (2p − 1, 2) and (2p − 1, 3), then the node is the vertex 2p. Treat other levels in the same way. If the right hand end of the board consists of m columns of horizontal dominoes, then the bottom level of the ST 2 has 2(m + 1) vertices. This gives us the corresponding ST 2.

[figure: horizontal; domino; red vertical; domino; green vertical; domino]

Figure 2. An example

Figure 2. shows an example of a ST 2 with 2 × 6 edges and its corresponding tiling of a 3 × 2 · (6 − 1) board.

3 Sequences with G_{0} = 1, G_{1} = d

In this section, we present parallel results for augmented skinny trees. Since almost all of the results have same reasoning as the corresponding one in Section 2, we will only give brief proofs or just comments. Recall that AST denotes augmented skinny tree.

Theorem 10. The generating function for the number of augmented skinny trees in which the outdegree of each vertex is multiple of d is denoted by A_{d}(z) and satisfies the equation

A_{d}(z) = ∑_{T ∈𝔸𝕊𝕋} z^{#edges of T} = \frac{(1 − z^{d})^{2}}{1 − (d + 2)z^{d} + z^{2d}} .

Proof. We proceed as in the proof of Theorem 1 and consider the outdegree of the root. We find that

A_{d}(z) = 1 + ∑_{k≥d,d|k} kz^{k}A_{d}(z) = 1 + A_{d}(z)\frac{dz^{d}}{(1 − z^{d})^{2}} .

Solving for A_{d}(z) will complete the proof.

Let

A_{d} (z) = \frac{(1 − z^{d})^{2}}{1 − (d + 2)z^{d} + z^{2d}} = ∑_{n≥0} A_{d,n}z^{nd}.

With the same kind of argument as in the constructive proof of Theorem 2, we obtain

Theorem 11. The sequences A_{d,n} satisfy A_{d,n} = (d+2)A_{d,n−1}−A_{d,n−2} and A_{d,0} = 1, A_{d,1} = d.

Taking d = 1, we obtain

Corollary 12. The number of AST ’s with n edges is F_{2n} for n ≥ 1.

Stanley has presented a result similar to Corollary 12 which is attributed to Gessel (see [2, p.46]). With the same technique as in the proof of Proposition 4, we obtain

Proposition 13. The number of AST ’s with n edges and k (k ≥ 0) nodes is \binom{n+k}{2k+1}.

Summing over 0 ≤ k ≤ n − 1, we get the total number of AST ’s with n edges. This leads to the following corollary [1].

Corollary 14.

F_{2n} = ∑_{k=0}^{n−1} \binom{n + k}{2k + 1}, for n ≥ 1.

By similar argument as the proof of Proposition 6, now noting that the augmented leaf will be subdivided into d − 1 leaves and a new augmented leaf, we obtain the following proposition.

Proposition 15. The sequences A_{d,n} satisfy

A_{d,n} = ∑_{k=0}^{n−1} \binom{n + k}{2k + 1}d^{k+1}.

When d = 2, the first few terms of A_{2}(z) are

A_{2}(z) = ∑_{n≥0} A_{2,n}z^{2n} = 1 + 2z^{2} + 8z^{4} + 30z^{6} + 112z^{8} + 418z^{10} + · · · .

These integers A_{2,n} are those integer solutions of the Diophantine equation 3 ∗ n^{2} + 4 which are perfect squares (see \underline{A052530}). This reduces to a Pells equation m^{2} − 3n^{2} = 1 and to computing A_{n} via the relation 2(2 + \sqrt{3})^{n} = A_{n} + A_{2,n}. The sequence S_{2,n} of ST 2’s is essentially the sequence A_{n} − A_{2,n}.

In the same way, we can obtain the generating functions for (augmented) skinny trees in which each node and the root have odd outdegree.

Theorem 16. The generating function for the number of ST ’s where each node and the root have odd outdegree is (see \underline{A105309})

\frac{z − z^{3}}{z^{4} − z^{3} − 2z^{2} − z + 1} = z + z^{2} + 2z^{3} + 5z^{4} + 9z^{5} + 20z^{6} + ⋯,

while the generating function for the number of AST ’s where each node and the root have odd outdegree is (see \underline{A119749})

\frac{z + z^{3}}{z^{4} − z^{3} − 2z^{2} − z + 1} = z + z^{2} + 4z^{3} + 7z^{4} + 15z^{5} + 32z^{6} + · · · .

4 Average height of skinny trees

Another question we can ask is what is the average height of AST ’s with n edges (The result for ST ’s is similar). Let

H(z) = ∑_{#edges of T =n} H_{n}z^{n}

denote the total height generating function where H_{n} is the sum of all heights over all AST ’s with n edges.

Proposition 17. The generating function for the total height of AST ’s is (see \underline{A030267})

H(z) = \frac{z(1 − z)^{2}}{(1 − 3z + z^{2})^{2}} = z + 4z^{2} + 14z^{3} + 46z^{4} + 145z^{5} + 444z^{6} + · · · .

Proof. First we observe that the generating function for total height of AST ’s of height k is

k (\frac{z}{(1 − z)^{2}} )^{k} ,

since these trees can be decomposed into k small AST ’s. Set y = \frac{z}{(1−z)^{2}} . Summing over k ≥ 1, we obtain H(z),

H(z) = ∑_{k≥1} ky^{k} = y \frac{d}{dy} (\frac{y}{1 − y} ) = \frac{y}{(1 − y)^{2}} .

So

H(z) = \frac{z(1 − z)^{2}}{(1 − 3z + z^{2})^{2}} .

Theorem 18. The average height of AST ’s with n edges approaches \frac{n}{\sqrt{5}}.

Proof. From Proposition 17, we obtain that the total height of AST ’s with n edges is

H_{n} = \frac{2nF_{2n+1} + (2 − n)F_{2n}}{5} .

Since the average height is \frac{H_{n}}{F_{2n}} and \frac{F_{2n+1}}{F_{2n}} ∼ \frac{1+\sqrt{5}}{2}, we have

\frac{H_{n}}{F_{2n}} ∼ \frac{2n}{5} · \frac{1 + \sqrt{5}}{2} + \frac{2 − n}{5} ∼ \frac{n}{\sqrt{5}}.

It follows that the average height approaches \frac{n}{\sqrt{5}}.

For ST ’s, we find that the generating function for the total height is

h (z) = ∑_{n=0}^{∞} h_{n}z^{n} = \frac{z (1 − z)^{3}}{(1 − 3z + z^{2})^{2}} = z + 3z^{2} + 10z^{3} + 32z^{4} + 99z^{5} + 299z^{6} + · · · .

We have h_{n} = H_{n} − H_{n−1} and h_{n} = ∑_{k=1}^{n} k\binom{n+k−2}{2k−2} (see \underline{A038731}). So the average height for ST ’s approaches the same limit,

\frac{h_{n}}{F_{2n−1}} = \frac{(n + 4)F_{2n−1} + (2n − 1)F_{2n−2}}{5F_{2n−1}} ∼ \frac{n}{\sqrt{5}}.

Remarks. Actually, the sequences G_{n} with other different initial conditions also have analogous interpretation. For instance, the sequences G_{n} with G_{0} = 1, G_{1} = d + 2 count augmented skinny trees ST d’s except that we number the bottom row from 1 to kd and the marked leaf must have a number congruent to 1 modulo d.

5 Acknowledgements

We would like to thank the referee for his detailed comments which helped to improve the presentation of this paper. This work was supported by the 973 Project, the PCSIRT Project of the Ministry of Education, the Ministry of Science and Technology and the National Science Foundation of China.

References

[1] Arthur T. Benjamin, Jennifer Quinn, Proofs that Really Count: The Art of Combinatorial Proof, Mathematical Association of America, 2003.

[2] R. P. Stanley, Enumerative Combinatorics I, Cambridge Univ. Press, Cambridge, 1997.

[3] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, published electronically at http://www.research.att.com/∼njas/sequences/.

[4] J. H. van Lint and R. M. Wilson, A Course in Combinatorics, 2nd edition, Cambridge University Press, 2001.

2000 Mathematics Subject Classification: Primary 05C05; Secondary 11B39, 05A15. Keywords: skinny trees, outdegree, tilings, Fibonacci numbers, lattice paths.

(Concerned with sequences \underline{A000045}, \underline{A001835}, \underline{A030267}, \underline{A038731}, \underline{A052530}, \underline{A105309}, and \underline{A119749}.)

Received May 3 2007; revised version received July 26 2007. Published in Journal of Integer Sequences, August 2 2007.

Return to Journal of Integer Sequences home page.