

A001835


a(n) = 4*a(n1)  a(n2), with a(0) = 1, a(1) = 1.
(Formerly M2894 N1160)


71



1, 1, 3, 11, 41, 153, 571, 2131, 7953, 29681, 110771, 413403, 1542841, 5757961, 21489003, 80198051, 299303201, 1117014753, 4168755811, 15558008491, 58063278153, 216695104121, 808717138331, 3018173449203, 11263976658481
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

See A079935 for another version.
Number of ways of packing a 3 X 2*(n1) rectangle with dominoes.  David Singmaster.
Equivalently, number of perfect matchings of the P_3 X P_{2(n1)} lattice graph.  Emeric Deutsch, Dec 28 2004
The terms of this sequence are the positive square roots of the indices of the octagonal numbers (A046184)  Nicholas S. Horne (nairon(AT)loa.com), Dec 13 1999
Terms are the solutions to: 3*x^2  2 is a square.  Benoit Cloitre, Apr 07 2002
Gives solutions x>0 of the equation floor(x*r*floor(x/r)) == floor(x/r*floor(x*r)) where r = 1 + sqrt(3).  Benoit Cloitre, Feb 19 2004
a(n) = L(n1,4), where L is defined as in A108299; see also A001834 for L(n,4).  Reinhard Zumkeller, Jun 01 2005
Values x + y, where (x, y) solves for x^2  3*y^2 = 1, i.e., a(n) = A001075(n) + A001353(n).  Lekraj Beedassy, Jul 21 2006
Number of 01avoiding words of length n on alphabet {0,1,2,3} which do not end in 0. (E.g., for n = 2 we have 02, 03, 11, 12, 13, 21, 22, 23, 31, 32, 33.)  Tanya Khovanova, Jan 10 2007
sqrt(3) = 2/2 + 2/3 + 2/(3*11) + 2/(11*41) + 2/(41*153) + 2/(153*571) + ...  Gary W. Adamson, Dec 18 2007
The lower principal convergents to 3^(1/2), beginning with 1/1, 5/3, 19/11, 71/41, comprise a strictly increasing sequence; numerators = A001834, denominators = A001835.  Clark Kimberling, Aug 27 2008
From Gary W. Adamson, Jun 21 2009: (Start)
A001835 and A001353 = bisection of denominators of continued fraction [1, 2, 1, 2, 1, 2, ...]; i.e., bisection of A002530.
a(n) = determinant of an n*n tridiagonal matrix with 1's in the super and subdiagonals and (3, 4, 4, 4, ...) as the main diagonal.
Also, the product of the eigenvalues of such matrices: a(n) = Product_{k=1..(n1)/2)} (4 + 2*cos(2*k*Pi/n).
(End)
Let M = a triangle with the evenindexed Fibonacci numbers (1, 3, 8, 21, ...) in every column, and the leftmost column shifted up one row. a(n) starting (1, 3, 11, ...) = lim_{n>infinity} M^n, the leftshifted vector considered as a sequence.  Gary W. Adamson, Jul 27 2010
a(n+1) is the number of compositions of n when there are 3 types of 1 and 2 types of other natural numbers.  Milan Janjic, Aug 13 2010
For n >= 2, a(n) equals the permanent of the (2*n2) X (2*n2) tridiagonal matrix with sqrt(2)'s along the main diagonal, and 1's along the superdiagonal and the subdiagonal.  John M. Campbell, Jul 08 2011
Primes in the sequence are apparently those in A096147.  R. J. Mathar, May 09 2013
Except for the first term, positive values of x (or y) satisfying x^2  4xy + y^2 + 2 = 0.  Colin Barker, Feb 04 2014
Except for the first term, positive values of x (or y) satisfying x^2  14xy + y^2 + 32 = 0.  Colin Barker, Feb 10 2014
The (1,1) element of A^n where A = (1, 1, 1; 1, 2, 1; 1, 1, 2).  David Neil McGrath, Jul 23 2014
Yong Hao Ng has shown that for any n, a(n) is coprime with any member of A001834 and with any member of A001075.  René Gy, Feb 25 2018
a(n+1) is the number of spanning trees of the graph T_n, where T_n is a 2 X n grid with an additional vertex v adjacent to (1,1) and (2,1).  Kevin Long, May 04 2018
a(n)/A001353(n) is the resistance of an nladder graph whose edges are replaced by oneohm resistors. The resistance in ohms is measured at two nodes at one end of the ladder. It approaches sqrt(3)  1 for n > infinity. See A342568, A357113, and A357115 for related information.  Hugo Pfoertner, Sep 17 2022


REFERENCES

R. C. Alperin, A family of nonlinear recurrences and their linear solutions, Fib. Q., 57:4 (2019), 318321.
Bastida, Julio R. Quadratic properties of a linearly recurrent sequence. Proceedings of the Tenth Southeastern Conference on Combinatorics, Graph Theory and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1979), pp. 163166, Congress. Numer., XXIIIXXIV, Utilitas Math., Winnipeg, Man., 1979. MR0561042 (81e:10009)
L. Euler, (E388) Vollstaendige Anleitung zur Algebra, Zweiter Theil, reprinted in: Opera Omnia. Teubner, Leipzig, 1911, Series (1), Vol. 1, p. 375.
F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Ars Combin. 49 (1998), 129154.
R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. AddisonWesley, Reading, MA, 1990, p. 329.
Serge Lang, Introduction to Diophantine Approximations, AddisonWesley, New York, 1966.
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. P. Stanley, Enumerative Combinatorics I, p. 292.


LINKS

T. D. Noe, Table of n, a(n) for n = 0..200
Mudit Aggarwal and Samrith Ram, Generating functions for straight polyomino tilings of narrow rectangles, arXiv:2206.04437 [math.CO], 2022.
Krassimir T. Atanassov and Anthony G. Shannon, On intercalated Fibonacci sequences, Notes on Number Theory and Discrete Mathematics (2020) Vol. 26, No. 3, 218223.
Steve Butler, Paul Horn, and Eric Tressler, Intersecting Domino Tilings, Fibonacci Quart. 48 (2010), no. 2, 114120.
Niccolò Castronuovo, On the number of fixed points of the map gamma, arXiv:2102.02739 [math.NT], 2021. Mentions this sequence.
A. Consilvio et al., Tilings, ordered partitions, and weird languages, MAA FOCUS, June/July 2012, 1617.
J. B. Cosgrave and K. Dilcher, A role for generalized Fermat numbers, Math. Comp., to appear 2016; (See paper #10).
J. B. Cosgrave and K. Dilcher, A role for generalized Fermat numbers, Math. Comp. 86 (2017), 899933.
L. Euler, Vollstaendige Anleitung zur Algebra, Zweiter Teil.
F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Preliminary version of paper that appeared in Ars Combin. 49 (1998), 129154.
F. Faase, Counting Hamiltonian cycles in product graphs
F. Faase, Results from the counting program
Alex Fink, Richard K. Guy, and Mark Krusemeyer, Partitions with parts occurring at most thrice, Contributions to Discrete Mathematics, Vol 3, No 2 (2008), pp. 76114. See Section 13.
H. Hosoya and A. Motoyama, An effective algorithm for obtaining polynomials for dimer statistics. Application of operator technique on the topological index to two and threedimensional rectangular and torus lattices, J. Math. Physics 26 (1985) 157167 (Table V).
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 409
Tanya Khovanova, Recursive Sequences
Clark Kimberling, Best lower and upper approximates to irrational numbers, Elemente der Mathematik, 52 (1997) 122126.
David Klarner and Jordan Pollack, Domino tilings of rectangles with fixed width, Disc. Math. 32 (1980) 4552.
R. J. Mathar, Paving Rectangular Regions with Rectangular Tiles: Tatami and NonTatami Tilings, arXiv:1311.6135 [math.CO], 2013, Table 2.
R. J. Mathar, Tilings of rectangular regions by rectangular tiles: Counts derived from transfer matrices, arXiv:1406.7788 (2014), eq. (4).
Valcho Milchev and Tsvetelina Karamfilova, Domino tiling in grid  new dependence, arXiv:1707.09741 [math.HO], 2017.
Yong Hao Ng, A partition in three classes of the set of all prime numbers?, Math StackExchange.
J.C. Novelli and J.Y. Thibon, Hopf Algebras of mpermutations,(m+1)ary trees, and mparking functions, arXiv preprint arXiv:1403.5962 [math.CO], 2014.
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
Jaime RangelMondragon, Polyominoes and Related Families, The Mathematica Journal, 9:3 (2005), 609640.
John Riordan, Letter to N. J. A. Sloane, Sep 26 1980 with notes on the 1973 Handbook of Integer Sequences. Note that the sequences are identified by their Nnumbers, not their Anumbers.
David Singmaster, Letter to N. J. A. Sloane, Oct 3 1982.
Anitha Srinivasan, The MarkoffFibonacci Numbers, Fibonacci Quart. 58 (2020), no. 5, 222228.
Thotsaporn ”Aek” Thanatipanonda, Statistics of Domino Tilings on a Rectangular Board, Fibonacci Quart. 57 (2019), no. 5, 145153. See p. 151.
Herman Tulleken, Polyominoes 2.2: How they fit together, (2019).
F. V. Waugh and M. W. Maxfield, Sideanddiagonal numbers, Math. Mag., 40 (1967), 7483.
Index entries for sequences related to dominoes
Index entries for sequences related to Chebyshev polynomials.
Index entries for linear recurrences with constant coefficients, signature (4,1).


FORMULA

G.f.: (1  3*x)/(1  4*x + x^2).  Simon Plouffe in his 1992 dissertation
a(1n) = a(n).
a(n) = ((3 + sqrt(3))^(2*n  1) + (3  sqrt(3))^(2*n  1))/6^n.  Dean Hickerson, Dec 01 2002
a(n) = (8 + a(n1)*a(n2))/a(n3).  Michael Somos, Aug 01, 2001
a(n+1) = Sum_{k=0..n} (2^k * binomial(n + k, n  k), n >= 0.  Len Smiley, Dec 09 2001
Limit_{n>infinity} a(n)/a(n1) = 2 + sqrt(3).  Gregory V. Richardson, Oct 10 2002
a(n) = 2*A061278(n1) + 1 for n > 0.  Bruce Corrigan (scentman(AT)myfamily.com), Nov 04 2002
Let q(n, x) = Sum_{i=0..n} x^(ni)*binomial(2*n  i, i); then q(n, 2) = a(n+1).  Benoit Cloitre, Nov 10 2002
a(n+1) = Sum_{k=0..n} ((1)^k)*((2*n+1)/(2*n + 1  k))*binomial(2*n + 1  k, k)*6^(n  k) (from standard T(n,x)/x, n >= 1, Chebyshev sum formula). The Smiley and Cloitre sum representation is that of the S(2*n, i*sqrt(2))*(1)^n Chebyshev polynomial.  Wolfdieter Lang, Nov 29 2002
a(n) = S(n1, 4)  S(n2, 4) = T(2*n1, sqrt(3/2))/sqrt(3/2) = S(2*(n1), i*sqrt(2))*(1)^(n  1), with S(n, x) := U(n, x/2), resp. T(n, x), Chebyshev's polynomials of the second, resp. first, kind. See A049310 and A053120. S(1, x) = 0, S(2, x) = 1, S(n, 4) = A001353(n+1), T(1, x) = x.
a(n+1) = sqrt((A001834(n)^2 + 2)/3), n >= 0 (see Cloitre comment).
Sequence satisfies 2 = f(a(n), a(n+1)) where f(u, v) = u^2 + v^2  4*u*v.  Michael Somos, Sep 19 2008
a(n) = (1/6)*(3*(2  sqrt(3))^n + sqrt(3)*(2  sqrt(3))^n + 3*(2 + sqrt(3))^n  sqrt(3)*(2 + sqrt(3))^n) (Mathematica's solution to the recurrence relation).  SarahMarie Belcastro, Jul 04 2009
If p[1] = 3, p[i] = 2, (i > 1), 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+1) = det A.  Milan Janjic, Apr 29 2010
a(n) = (a(n1)^2 + 2)/a(n2).  Irene Sermon, Oct 28 2013
a(n) = A001353(n+1)  3*A001353(n).  R. J. Mathar, Oct 30 2015
a(n) = a(n1) + 2*A001353(n1).  Kevin Long, May 04 2018
From Franck Maminirina Ramaharo, Nov 11 2018: (Start)
a(n) = (1)^n*(A125905(n) + 3*A125905(n1)), n > 0.
E.g.f.: exp^(2*x)*(3*cosh(sqrt(3)*x)  sqrt(3)*sinh(sqrt(3)*x))/3. (End)


MAPLE

f:=n>((3+sqrt(3))^(2*n1)+(3sqrt(3))^(2*n1))/6^n; [seq(simplify(expand(f(n))), n=0..20)]; # N. J. A. Sloane, Nov 10 2009


MATHEMATICA

CoefficientList[Series[(13x)/(14x+x^2), {x, 0, 24}], x] (* JeanFrançois Alcover, Jul 25 2011, after g.f. *)
LinearRecurrence[{4, 1}, {1, 1}, 30] (* Harvey P. Dale, Jun 08 2013 *)
Table[Round@Fibonacci[2n1, Sqrt[2]], {n, 0, 20}] (* Vladimir Reshetnikov, Sep 15 2016 *)
Table[(3*ChebyshevT[n, 2]  ChebyshevU[n, 2])/2, {n, 0, 20}] (* G. C. Greubel, Dec 23 2019 *)


PROG

(PARI) {a(n) = real( (2 + quadgen(12))^n * (1  1 / quadgen(12)) )} /* Michael Somos, Sep 19 2008 */
(PARI) {a(n) = subst( (polchebyshev(n) + polchebyshev(n1)) / 3, x, 2)} /* Michael Somos, Sep 19 2008 */
(Sage) [lucas_number1(n, 4, 1)lucas_number1(n1, 4, 1) for n in range(25)] # Zerinvary Lajos, Apr 29 2009
(Sage) [(3*chebyshev_T(n, 2)  chebyshev_U(n, 2))/2 for n in (0..20)] # G. C. Greubel, Dec 23 2019
(Haskell)
a001835 n = a001835_list !! n
a001835_list =
1 : 1 : zipWith () (map (4 *) $ tail a001835_list) a001835_list
 Reinhard Zumkeller, Aug 14 2011
(Magma) [n le 2 select 1 else 4*Self(n1)Self(n2): n in [1..25]]; // Vincenzo Librandi, Sep 16 2016
(GAP) a:=[1, 1];; for n in [3..20] do a[n]:=4*a[n1]a[n2]; od; a; # G. C. Greubel, Dec 23 2019


CROSSREFS

Row 3 of array A099390.
Essentially the same as A079935.
First differences of A001353.
Partial sums of A052530.
Pairwise sums of A006253.
Bisection of A002530, A005246 and A048788.
First column of array A103997.
Cf. A001519, A003699, A082841, A101265, A125077, A001353, A001542, A096147 (subsequence of primes).
Sequence in context: A335793 A077831 A032952 * A079935 A281593 A113437
Adjacent sequences: A001832 A001833 A001834 * A001836 A001837 A001838


KEYWORD

nonn,easy,nice


AUTHOR

N. J. A. Sloane


STATUS

approved



