

A001906


F(2n) = bisection of Fibonacci sequence: a(n) = 3*a(n1)  a(n2).
(Formerly M2741 N1101)


422



0, 1, 3, 8, 21, 55, 144, 377, 987, 2584, 6765, 17711, 46368, 121393, 317811, 832040, 2178309, 5702887, 14930352, 39088169, 102334155, 267914296, 701408733, 1836311903, 4807526976, 12586269025, 32951280099, 86267571272, 225851433717, 591286729879, 1548008755920
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

Apart from initial term, same as A088305.
Apart from initial terms, also Pisot sequences E(3,8), P(3,8), T(3,8). See A008776 for definitions of Pisot sequences.
Number of walks of length 2n+1 in the path graph P_4 from one end to the other one. Example: a(2)=3 because in the path ABCD we have ABABCD, ABCBCD and ABCDCD.  Emeric Deutsch, Apr 02 2004
Simplest example of a secondorder recurrence with the sixth term a square.
Number of (s(0), s(1), ..., s(2n)) such that 0 < s(i) < 5 and s(i)  s(i1) = 1 for i = 1,2,...,2n, s(0) = 1, s(2n) = 3.  Lekraj Beedassy, Jun 11 2004
a(n) (for n > 0) is the smallest positive integer that cannot be created by summing at most n values chosen among the previous terms (with repeats allowed).  Andrew Weimholt, Jul 20 2004
All nonnegative integer solutions of Pell equation b(n)^2  5*a(n)^2 = +4 together with b(n) = A005248(n), n >= 0.  Wolfdieter Lang, Aug 31 2004
a(n+1) is a Chebyshev transform of 3^n (A000244), where the sequence with g.f. G(x) is sent to the sequence with g.f. (1/(1+x^2))G(x/(1+x^2)).  Paul Barry, Oct 25 2004
a(n) is the number of distinct products of matrices A, B, C, in (A+B+C)^n where commutator [A,B] = 0 but C does not commute with A or B.  Paul D. Hanna and Max Alekseyev, Feb 01 2006
Number of binary words with exactly k1 strictly increasing runs. Example: a(3)=F(6)=8 because we have 00,10,11,001,010,101,011 and 0101. Column sums of A119900.  Emeric Deutsch, Jul 23 2006
Inverse: With phi = (sqrt(5) + 1)/2, log_phi((sqrt(5) a(n) + sqrt(5 a(n)^2 + 4))/2) = n.  David W. Cantrell (DWCantrell(AT)sigmaxi.net), Feb 19 2007
[1,3,8,21,55,144,...] is the Hankel transform of [1,1,4,17,75,339,1558,...](see A026378).  Philippe Deléham, Apr 13 2007
The Diophantine equation a(n) = m has a solution (for m >= 1) if and only if floor(arcsinh(sqrt(5)*m/2)/log(phi)) <> floor(arccosh(sqrt(5)*m/2)/log(phi)) where phi is the golden ratio. An equivalent condition is A130259(m) = A130260(m).  Hieronymus Fischer, May 25 2007
a(n+1) = AB^(n)(1), n >= 0, with compositions of Wythoff's complementary A(n):=A000201(n) and B(n)=A001950(n) sequences. See the W. Lang link under A135817 for the Wythoff representation of numbers (with A as 1 and B as 0 and the argument 1 omitted). E.g., 1=`1`, 3=`10`, 8=`100`, 21=`1000`, ..., in Wythoff code.
a(n) is also the number of idempotent orderpreserving partial transformations (of an nelement chain) of width n (width(alpha) = max(Im(alpha))). Equivalently, it is the number of idempotent orderpreserving full transformations (of an nelement chain).  Abdullahi Umar, Sep 08 2008
a(n) is the number of ways that a string of 0,1 and 2 of size (n1) can be arranged with no 12pairs.  Udita Katugampola, Sep 24 2008
As a fraction: 1/71 = 0.01408450... or 1/9701 = 0.0001030821....  Mark Dols, May 18 2010
Sum of the products of the elements in the compositions of n (example for n=3: the compositions are 1+1+1, 1+2, 2+1, and 3; a(3) = 1*1*1 + 1*2 + 2*1 + 3 = 8).  Dylon Hamilton, Jun 20 2010, Geoffrey Critzer, Joerg Arndt, Dec 06 2010
a(n) relates to regular polygons with even numbers of edges such that Product_{k=1..(n2)/2} (1 + 4*cos^2 k*Pi/n) = evenindexed Fibonacci numbers with a(n) relating to the 2*ngons. The constants as products = roots to evenindexed rows of triangle A152063. For example: a(5) = 55 satisfies the product formula relating to the 10gon.  Gary W. Adamson, Aug 15 2010
Alternatively, product of roots to x^4  12x^3 + 51x^2  90x + 55, (10th row of triangle A152063) = (4.618...)*(3.618...)*(2.381...)*(1.381...) = 55.  Gary W. Adamson, Aug 15 2010
a(n) is the number of generalized compositions of n when there are i different types of i, (i=1,2,...).  Milan Janjic, Aug 26 2010
a(2) = 3 is the only prime.
Number of nonisomorphic graded posets with 0 and uniform hasse graph of rank n > 0, with exactly 2 elements of each rank level above 0. (Uniform used in the sense of Retakh, Serconek, and Wilson. Graded used in Stanley's sense that every maximal chain has the same length n.)  David Nacin, Feb 13 2012
Pisano period lengths: 1, 3, 4, 3, 10, 12, 8, 6, 12, 30, 5, 12, 14, 24, 20, 12, 18, 12, 9, 30, ...  R. J. Mathar, Aug 10 2012
Solutions (x, y) = (a(n), a(n+1)) satisfying x^2 + y^2 = 3xy + 1.  Michel Lagneau, Feb 01 2014
For n >= 1, a(n) equals the number of 01avoiding words of length n1 on alphabet {0,1,2}.  Milan Janjic, Jan 25 2015
With a(0) = 0, for n > 1, a(n) is the smallest number not already in the sequence such that a(n)^2  a(n1)^2 is a Fibonacci number.  Derek Orr, Jun 08 2015
Let T be the tree generated by these rules: 0 is in T, and if p is in T, then p + 1 is in T and x*p is in T and y*p is in T. The nth generation of T consists of A001906(n) polynomials, for n >= 0.  Clark Kimberling, Nov 24 2015
For n > 0, a(n) = exactly the maximum area of a quadrilateral with sides in order of lengths F(n), F(n), L(n), and L(n) with L(n)=A000032(n).  J. M. Bergot, Jan 20 2016
a(n) = twice the area of a triangle with vertices at (L(n+1), L(n+2)), (F(n+1), F(n+1)), and (L(n+2), L(n+1)), with L(n)=A000032(n).  J. M. Bergot, Apr 20 2016
Except for the initial 0, this is the pINVERT of (1,1,1,1,1,...) for p(S) = 1  S  S^2; see A291000.  Clark Kimberling, Aug 24 2017
a(n+1) is the number of spanning trees of the graph T_n, where T_n is a sequence of n triangles, where adjacent triangles share an edge.  Kevin Long, May 07 2018
a(n) is the number of ways to partition [n] such that each block is a run of consecutive numbers, and each block has a fixed point, e.g., for n=3, 123 with 1 and 3 as fixed points is valid, but 132 is not valid as 1 and 3 do not form a run. Consequently, a(n) also counts the spanning trees of the graph given by taking a path with n vertices and adding another vertex adjacent to all of them.  Kevin Long, May 11 2018
The preceding comment can be paraphrased as follows. a(n) is the row sum of the array A305309 for n >= 1. The array A305309(n, k) gives the sum of the products of the block lengths of the set partition of [n] := {1, 2, ..., n} with A048996(n, k) blocks of consecutive numbers, corresponding to the compositions obtained from the kth partition of n in AbramowitzStegun order. See the comments and examples at A305309.
{a(n)} also gives the infinite sequence of nonnegative numbers k for which k * k*phi < 1/sqrt(5), where the irrational number phi = A001622 (golden section), and x is the absolute value of the difference between x and the nearest integer. See, e.g., the Havil reference, pp. 171172. (End)
This Chebyshev sequence a(n) = S(n1, 3) (see a formula below) is related to the bisection of Fibonacci sequences {F(a,b;n)}_{n>=0} with input F(a,b;0) = a and F(a,b;1) = b, by F(a,b;2*k) = (a+b)*S(k1, 3)  a*S(k2, 3) and F(a,b;2*k+1) = b*S(k, 3) + (ab)*S(k1, 3), for k >= 0, and S(2, 3) = 1. Proof via the o.g.f.s GFeven(a,b,t) = (a  t*(2*ab))/(1  3*t + t^2) and GFodd(a,b,t) = (b + t*(ab))/(1  3*t + t^2). The special case a = 0, b = 1 gives back F(2*k) = S(k1, 3) = a(k).  Wolfdieter Lang, Jun 07 2019
a(n) is the number of tilings of two n X 1 rectangles joined orthogonally at a common endsquare (so to have 2n1 squares in a rightangle V shape) with only 1 X 1 and 2 X 1 tiles. This is a consequence of F(2n) = F(n+1)*F(n) + F(n)*F(n1).  Nathaniel Gregg, Oct 10 2021
These are the denominators of the upper convergents to the golden ratio, tau; they are also the numerators of the lower convergents (viz. 1/1 < 3/2 < 8/5 < 21/13 < ... < tau < ... 13/8 < 5/3 < 2/1).  Clark Kimberling, Jan 02 2022


REFERENCES

Mohammad K. Azarian, The Generating Function for the Fibonacci Sequence, Missouri Journal of Mathematical Sciences, Vol. 2, No. 2, Spring 1990, pp. 7879. Zentralblatt MATH, Zbl 1097.11516.
Mohammad K. Azarian, A Generalization of the Climbing Stairs Problem II, Missouri Journal of Mathematical Sciences, Vol. 16, No. 1, Winter 2004, pp. 1217.
A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, id. 2,5,6,14,33,55.
R. J. Douglas, Tournaments that admit exactly one Hamiltonian cycle, Proc. London Math. Soc., 21 (1970), 716730.
G. Everest, A. van der Poorten, I. Shparlinski and T. Ward, Recurrence Sequences, Amer. Math. Soc., 2003; see esp. p. 255.
A. Gerardin, Reply to Query 4389, L'Intermédiaire des Mathématiciens, 22 (1915), 23.
Julian Havil, The Irrationals, Princeton University Press, Princeton and Oxford, 2012, pp. 171172.
Howie, J. M. Combinatorial and probabilistic results in transformation semigroups. Words, languages and combinatorics, II (Kyoto, 1992), 200206, World Sci. Publ., River Edge, NJ, (1994).
Laradji, A. and Umar, A. Combinatorial results for semigroups of orderpreserving full transformations. Semigroup Forum 72 (2006), 5162.
I. Lukovits, A. Graovac, E. Kalman, G. Kaptay, P. Nagy, S. Nikolic, J. Sytchev and N. Trinajstich, "Nanotubes: Number of Kekulé Structures and Aromaticity", J. Chem. Inf. Comput. Sci, vol. 43 (2003), pp. 609614. See Equation 6 on page 611.
T. Mansour, M. Shattuck, A statistic on ncolor compositions and related sequences, Proc. Indian Acad. Sci. (Math. Sci.) Vol. 124, No. 2, May 2014, pp. 127140.
H. Mathieu, Query 3932, L'Intermédiaire des Mathématiciens, 18 (1911), 222.  N. J. A. Sloane, Mar 08 2022
I. Niven and H. S. Zuckerman, An Introduction to the Theory of Numbers. 2nd ed., Wiley, NY, 1966, p. 101.
Paulo Ribenboim, Primes in Lucas sequences (Chap 4), in 'My Numbers, My Friends', SpringerVerlag 2000 NY, page 27.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
R. Stanley, Enumerative combinatorics, Vol. 1, Cambridge University Press, Cambridge, 1997, pp. 96100.


LINKS

P. J. Cameron, Some sequences of integers, Discrete Math., 75 (1989), 89102; also in "Graph Theory and Combinatorics 1988", ed. B. Bollobas, Annals of Discrete Math., 43 (1989), 89102.
A. Gougenheim, About the linear sequence of integers such that each term is the sum of the two preceding Part 1 Part 2, Fib. Quart., 9 (1971), 277295, 298.
G. Kreweras, Sur les éventails de segments, Cahiers du Bureau Universitaire de Recherche Opérationnelle, Institut de Statistique, Université de Paris, #15 (1970), 341. [Annotated scanned copy]
J. Salas and A. D. Sokal, Transfer Matrices and PartitionFunction Zeros for Antiferromagnetic Potts Models. V. Further Results for the SquareLattice Chromatic Polynomial, J. Stat. Phys. 135 (2009) 279373, arXiv:0711.1738. Mentions this sequence.


FORMULA

G.f.: x / (1  3*x + x^2).  Simon Plouffe in his 1992 dissertation
a(n) = 3*a(n1)  a(n2) = A000045(2*n).
a(n) = a(n).
a(n) = (ap^n  am^n)/(apam), with ap := (3+sqrt(5))/2, am := (3sqrt(5))/2.
Invert transform of natural numbers: a(n) = Sum_{k=1..n} k*a(nk), a(0) = 1.  Vladeta Jovovic, Apr 27 2001
a(n) = S(n1, 3) with S(n, x) = U(n, x/2) Chebyshev's polynomials of the 2nd kind, see A049310.
a(n) = Sum_{k=0..n} binomial(n, k)*F(k).  Benoit Cloitre, Sep 03 2002
Limit_{n>infinity} a(n)/a(n1) = 1 + phi = (3 + sqrt(5))/2. This sequence includes all of the elements of A033888 combined with A033890.
a(0)=0, a(1)=1, a(2)=3, a(n)*a(n2) + 1 = a(n1)^2.  Benoit Cloitre, Dec 06 2002
E.g.f.: (2/sqrt(5))*exp(3*x/2)*sinh(sqrt(5)*x/2).  Paul Barry, Apr 11 2003
Second diagonal of array defined by T(i, 1) = T(1, j) = 1, T(i, j) = Max(T(i1, j) + T(i1, j1); T(i1, j1) + T(i, j1)).  Benoit Cloitre, Aug 05 2003
F(2n+2) = 1, 3, 8, ... is the binomial transform of F(n+2).  Paul Barry, Apr 24 2004
a(n) = Sum_{i=0..n1} binomial(2*n1i, i)*5^(ni1)*(1)^i.  Mario Catalani (mario.catalani(AT)unito.it), Jul 23 2004
a(n) = Sum_{k=0..n} binomial(n+k, nk1) = Sum_{k=0..n} binomial(n+k, 2k+1).
a(n+1) = Sum_{k=0..floor(n/2)} binomial(nk, k)*(1)^k*3^(n2*k).  Paul Barry, Oct 25 2004
a(n) = (n*L(n)  F(n))/5 = Sum_{k=0..n1} (1)^n*L(2*n2*k1).
The ith term of the sequence is the entry (1, 2) in the ith power of the 2 X 2 matrix M = ((1, 1), (1, 2)).  Simone Severini, Oct 15 2005
Computation suggests that this sequence is the Hankel transform of A005807. The Hankel transform of {a(n)} is Det[{{a(1), ..., a(n)}, {a(2), ..., a(n+1)}, ..., {a(n), ..., a(2n1)}}].  John W. Layman, Jul 21 2000
a(n+1) = Sum_{i=0..n} Sum_{j=0..n} binomial(ni, j)*binomial(nj, i).  N. J. A. Sloane, Feb 20 2005
a(n) = (2/sqrt(5))*sinh(2*n*psi), where psi:=log(phi) and phi=(1+sqrt(5))/2.  Hieronymus Fischer, Apr 24 2007
a(n)^2 = Sum_{k=1..n} a(2*k1). This is a property of any sequence S(n) such that S(n) = B*S(n1)  S(n2) with S(0) = 0 and S(1) = 1 including {0,1,2,3,...} where B = 2.  Kenneth J Ramsey, Mar 23 2008
a(n) = 1/sqrt(5)*(phi^(2*n+2)  phi^(2*n2)), where phi = (1+sqrt(5))/2, the golden ratio.  Udita Katugampola (SIU), Sep 24 2008
If p[i] = i and if A is Hessenberg matrix of order n defined by: A[i,j] = p[ji+1], (i<=j), A[i,j] = 1, (i = j+1), and A[i,j] = 0 otherwise. Then, for n >= 1, a(n) = det(A).  Milan Janjic, May 02 2010
If p[i] = Stirling2(i,2) and if A is the Hessenberg matrix of order n defined by: A[i,j] = p[ji+1], (i<=j), A[i,j] = 1, (i = j+1), and A[i,j] = 0 otherwise. Then, for n >= 1, a(n1) = det(A).  Milan Janjic, May 08 2010
a(n) = F(2*n+10) mod F(2*n+5).
a(n) = 1 + a(n1) + Sum_{i=1..n1} a(i), with a(0)=0.  Gary W. Adamson, Feb 19 2011
a(n) is equal to the permanent of the (n1) X (n1) Hessenberg matrix with 3's along the main diagonal, i's along the superdiagonal and the subdiagonal (i is the imaginary unit), and 0's everywhere else.  John M. Campbell, Jun 09 2011
a(n), n > 1 is equal to the determinant of an (nx) X (n1) tridiagonal matrix with 3's in the main diagonal, 1's in the super and subdiagonals, and the rest 0's.  Gary W. Adamson, Jun 27 2011
a(n) = b such that Integral_{x=0..Pi/2} sin(n*x)/(3/2cos(x)) dx = c + b*log(3).  Francesco Daddi, Aug 01 2011
G.f.: A(x) = x/(13*x+x^2) = G(0)/sqrt(5); where G(k)= 1 (a^k)/(1  b*x/(b*x  2*(a^k)/G(k+1))), a = (73*sqrt(5))/2, b = 3+sqrt(5), if x<(3sqrt(5))/2 = 0.3819660...; (continued fraction 3 kind, 3step ).  Sergei N. Gladkovskii, Jun 25 2012
a(n) = 2^n*b(n;1/2) = b(n;1), where b(n;d), n=0,1,...,d, denote the deltaFibonacci numbers defined in comments to A000045 (see also Witula's et al. papers).  Roman Witula, Jul 12 2012
Product_{n>=1} (1 + 1/a(n)) = 1 + sqrt(5).  Peter Bala, Dec 23 2012
Product_{n>=2} (1  1/a(n)) = (1/6)*(1 + sqrt(5)).  Peter Bala, Dec 23 2012
G.f.: x/(12*x) + x^2/(12*x)/(Q(0)x) where Q(k) = 1  x/(x*k+1)/Q(k+1); (continued fraction).  Sergei N. Gladkovskii, Feb 23 2013
G.f.: G(0)/2  1, where G(k) = 1 + 1/( 1  x/(x + (1x)^2/G(k+1) )); (continued fraction).  Sergei N. Gladkovskii, Jul 16 2013
G.f.: x*G(0)/(23*x), where G(k) = 1 + 1/( 1  x*(5*k9)/(x*(5*k4)  6/G(k+1) )); (continued fraction).  Sergei N. Gladkovskii, Jul 17 2013
a(n) = U(n1,3/2) where U(n1,x) is Chebyshev polynomial of the second kind.  Milan Janjic, Jan 25 2015
The o.g.f. A(x) satisfies A(x) + A(x) + 6*A(x)*A(x) = 0. The o.g.f. for A004187 equals A(sqrt(x))*A(sqrt(x)).  Peter Bala, Apr 02 2015
For n > 1, a(n) = (3*F(n+1)^2 + 2*F(n2)*F(n+1)  F(n2)^2)/4.  J. M. Bergot, Feb 16 2016
For n > 3, a(n) = floor(MA)  4 for n even and floor(MA) + 5 for n odd. MA is the maximum area of a quadrilateral with lengths of sides in order L(n), L(n), F(n3), F(n+3), with L(n)=A000032(n). The ratio of the longer diagonal to the shorter approaches 5/3.  J. M. Bergot, Feb 16 2016
a(n+1) = Sum_{j=0..n} Sum_{k=0..j} binomial(nj,k)*binomial(j,k)*2^(jk).  Tony Foster III, Sep 18 2017
a(n) = Sum_{k=0..n1} Sum_{i=0..n1} C(k+i,ki).  Wesley Ivan Hurt, Sep 21 2017
a(n) = H(2*n, 1, 1/2) for n > 0 where H(n, a, b) > hypergeom([a  n/2, b  n/2], [1  n], 4).  Peter Luschny, Sep 03 2019
a(n) = 2/(sqrt(5)*tan(2*arctan(phi^(2*n)))), where phi = A001622 is the golden ratio.  Diego Rattaggi, Nov 21 2021
a(n) = sinh(2*n*arcsinh(1/2))/sqrt(5/4).  Peter Luschny, May 21 2022


EXAMPLE

G.f. = x + 3*x^2 + 8*x^3 + 21*x^4 + 55*x^5 + 144*x^6 + 377*x^7 + 987*x^8 + ...
a(3) = 8 because there are exactly 8 idempotent orderpreserving full transformations on a 3element chain, namely: (1,2,3)>(1,1,1),(1,2,3)>(2,2,2),(1,2,3)>(3,3,3),(1,2,3)>(1,1,3),(1,2,3)>(2,2,3),(1,2,3)>(1,2,2),(1,2,3)>(1,3,3),(1,2,3)>(1,2,3)mappings are coordinatewise.  Abdullahi Umar, Sep 08 2008


MAPLE

with(combstruct): SeqSeqSeqL := [T, {T=Sequence(S, card > 0), S=Sequence(U, card > 1), U=Sequence(Z, card >0)}, unlabeled]: seq(count(SeqSeqSeqL, size=n+1), n=0..28); # Zerinvary Lajos, Apr 04 2009
H := (n, a, b) > hypergeom([a  n/2, b  n/2], [1  n], 4):
a := n > `if`(n = 0, 0, H(2*n, 1, 1/2)):
combinat[fibonacci](2*n) ;
end proc:


MATHEMATICA

f[n_] := Fibonacci[2n]; Array[f, 28, 0] (* or *)
Take[Fibonacci[Range[0, 60]], {1, 1, 2}] (* Harvey P. Dale, May 23 2012 *)
CoefficientList[Series[(x)/(1  3x + x^2), {x, 0, 30}], x] (* Vincenzo Librandi, Sep 10 2014 *)


PROG

(PARI) {a(n) = subst( poltchebi(n+1)*4  poltchebi(n)*6, x, 3/2)/5}; /* Michael Somos, Dec 06 2002 */
(PARI) {a(n) = polchebyshev( n1, 2, 3/2)}; /* Michael Somos Jun 18 2011 */
(Sage) [lucas_number1(n, 3, 1) for n in range(27)] # Zerinvary Lajos, Jun 25 2008
(Sage) [fibonacci(2*n) for n in range(0, 28)] # Zerinvary Lajos, May 15 2009
(MuPAD) numlib::fibonacci(2*n) $ n = 0..35; // Zerinvary Lajos, May 09 2008
(Haskell)
a001906 n = a001906_list !! n
a001906_list =
0 : 1 : zipWith () (map (* 3) $ tail a001906_list) a001906_list
(Python)
def a(n, adict={0:0, 1:1}):
if n in adict:
return adict[n]
adict[n]=3*a(n1)  a(n2)
(Maxima) makelist(fib(2*n), n, 0, 30); /* Martin Ettl, Oct 21 2012 */


CROSSREFS



KEYWORD

nonn,easy,nice,core


AUTHOR



STATUS

approved



