|
| |
|
|
A144621
|
|
a(0) = a(1) = 1 and a(n+2) = a(n+1) * (3*a(n+1) - 2*a(n)^2), n>=0.
|
|
2
|
| |
|
|
|
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
|
|
|
|
FORMULA
|
|
|
|
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),
|
|
|
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
|
|
|
|
STATUS
|
approved
|
| |
|
|
