×

Properties of Fibonacci trees. (English) Zbl 0765.05038

Combinatorics, graph theory, and computing, Proc. 22nd Southeast Conf., Baton Rouge/LA (USA) 1991, Congr. Numerantium 84, 21-32 (1991).
[For the entire collection see Zbl 0747.00035.]
For \(n\in\mathbb{Z}^ +\) the Fibonacci trees \(T_ 1,T_ 2,T_ 3,\dots,\) are defined recursively as follows: (i) \(T_ 1\) and \(T_ 2\) are trees with only one vertex — the root; and, (ii) If \(n\geq 3\), \(T_ n\) is the rooted binary tree where \(T_{n-1}\) is the left subtree and \(T_{n-2}\) is the right subtree.
In this paper we shall be primarily interested in how the leaves and interval nodes are distributed throughout the levels of a given Fibonacci tree \(T_ n\). For \(n\in\mathbb{Z}^ +\) and \(i\in\mathbb{N}\), we let \(I(n,i)\) denote the number of internal nodes in \(T_ n\) at level \(i\). (The root of \(T_ n\) is at level 0, its children are at level 1, its grandchildren at level 2, and so on.) The number of leaves in \(T_ n\) at level \(i\) is denoted by \(L(n,i)\). Identities involving the numbers \(I(n,i)\) and \(L(n,i)\) are derived as part of our investigation.

MSC:

05C05 Trees

Citations:

Zbl 0747.00035
PDFBibTeX XMLCite

Online Encyclopedia of Integer Sequences:

The path length of the Fibonacci tree of order n.