OFFSET
0,3
COMMENTS
a(n) is the number of oriented spanning forests of the regular ternary tree of depth n that are rooted at the boundary (i.e., all oriented paths end either at a leaf or at the root).
For example, the tree
.........|
......../.\
......./\./\
has a(3) = 21 such spanning forests.
There is a remarkable product formula for the n-th term:
a(n) = 3^(2^(n-3)) 7^(2^(n-4)) 15^(2^(n-5)) ... (2^(n-3)-1)^4 (2^(n-2)-1)^2 (2^(n-1)-1) (2^n-1).
It follows that a(n) ~ (1/2)alpha^(2^n) (this is true even without taking logs), where alpha = 3^(1/8) 7^(1/16) 15^(1/32) ... = 1.60460505....
The number of digits of the n-th term is 1, 1, 1, 2, 3, 7, 13, 26, 53, 105, 210, 421, 841,... [From R. J. Mathar, Jan 23 2009]
Conjecture: a(n+1) = determinant of 2^n x 2^n matrix M where M(i,j) = 1 + exponent of 2 in the factorization of i+j-1 = A001511(i+j-1), i,j>0, n>2. - Ralf Stephan, Sep 27 2013
The conjecture above is true. The matrix M(n+1) is equivalent via an even number of row and column interchanges to the matrix T(n+1) defined by: T(0)=1; T(n) = I(2) X T(n-1) + 1(2^n)(1(2^n))^T, where X is the Kronecker product, I(2) is the 2 X 2 identity matrix, 1(k) is a column vector of k 1s and T is matrix transpose. All rows of this matrix have the same sum (n+1) + sum_{j=1..n}j*2^(n-j) = 2^(n+1)-1 hence this is the eigenvalue of the eigenvector 1(2^n). Now det(T(n)) = (det(T(n-1)))(det(T(n-1)+2*1(2^(n-1))(1(2^(n-1)))^T)) = (det(T(n-1))^2)(1+2*(1(2^(n-1)))^T (T(n-1))^{-1} 1(2^(n-1))) = (det(T(n-1))^2)((2-2^(-n))/(1-2^(-n))). Let v(n)=(2-2^(-(n+1)))/(1-2^(-(n+1))) and notice that v(n) = 3-2/(v(n-1)). Then det(T(n)) = (det(T(n-1))^2)(3-2/v(n-1)) = (det(T(n-1))^2)(3-2(det(T(n-2))^2)/(v(n-1)det(T(n-2))^2))= det(T(n-1))(3det(T(n-1))-2det(T(n-2))^2). In the closed-form product formula we see the eigenvalues of T(n). The matrix T(n) is the matrix of times of most recent common ancestors for a 2^n tips, fully balanced binary phylogenetic tree with unit branch lengths. - Krzysztof Bartoszek, Mar 23 2015
LINKS
Michael De Vlieger, Table of n, a(n) for n = 0..12
Ryan Flanagan, Lucas Lacasa, Vincenzo Nicosia, On the spectral properties of Feigenbaum graphs, arXiv:1903.00754 [physics.data-an], 2019.
FORMULA
a(n) = a(n-1)^2 * ((2-2^(-n))/(1-2^(-n))). - Krzysztof Bartoszek, Mar 23 2015
MAPLE
A144621 := proc(n) option remember ; if n <= 1 then 1; elif n = 2 then 3; else procname(n-1)*(3*procname(n-1)-2*procname(n-2)^2) ; fi; end: seq(A144621(n), n=0..12) ; # R. J. Mathar, Jan 23 2009
MATHEMATICA
Prepend[RecurrenceTable[{a[n + 2] == a[n + 1]*(3 a[n + 1] - 2 a[n]^2),
a[1] == 1, a[2] == 3}, a, {n, 8}], 1] (* Michael De Vlieger, Mar 23 2015 *)
CROSSREFS
KEYWORD
nonn
AUTHOR
N. J. A. Sloane, Jan 16 2009, based on email from Lionel Levine (levine(AT)Math.Berkeley.EDU), May 04 2006
EXTENSIONS
One more term from R. J. Mathar, Jan 23 2009
STATUS
approved