# Greetings from The On-Line Encyclopedia of Integer Sequences! http://oeis.org/
Search: id:a001835
Showing 1-1 of 1
%I A001835 M2894 N1160 #308 Jan 05 2025 19:51:32
%S A001835 1,1,3,11,41,153,571,2131,7953,29681,110771,413403,1542841,5757961,
%T A001835 21489003,80198051,299303201,1117014753,4168755811,15558008491,
%U A001835 58063278153,216695104121,808717138331,3018173449203,11263976658481
%N A001835 a(n) = 4*a(n-1) - a(n-2), with a(0) = 1, a(1) = 1.
%C A001835 See A079935 for another version.
%C A001835 Number of ways of packing a 3 X 2*(n-1) rectangle with dominoes. - David Singmaster.
%C A001835 Equivalently, number of perfect matchings of the P_3 X P_{2(n-1)} lattice graph. - _Emeric Deutsch_, Dec 28 2004
%C A001835 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
%C A001835 Terms are the solutions to: 3*x^2 - 2 is a square. - _Benoit Cloitre_, Apr 07 2002
%C A001835 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
%C A001835 a(n) = L(n-1,4), where L is defined as in A108299; see also A001834 for L(n,-4). - _Reinhard Zumkeller_, Jun 01 2005
%C A001835 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
%C A001835 Number of 01-avoiding 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
%C A001835 sqrt(3) = 2/2 + 2/3 + 2/(3*11) + 2/(11*41) + 2/(41*153) + 2/(153*571) + ... - _Gary W. Adamson_, Dec 18 2007
%C A001835 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
%C A001835 From _Gary W. Adamson_, Jun 21 2009: (Start)
%C A001835 A001835 and A001353 = bisection of denominators of continued fraction [1, 2, 1, 2, 1, 2, ...]; i.e., bisection of A002530.
%C A001835 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.
%C A001835 Also, the product of the eigenvalues of such matrices: a(n) = Product_{k=1..(n-1)/2)} (4 + 2*cos(2*k*Pi/n).
%C A001835 (End)
%C A001835 Let M = a triangle with the even-indexed 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->oo} M^n, the left-shifted vector considered as a sequence. - _Gary W. Adamson_, Jul 27 2010
%C A001835 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
%C A001835 For n >= 2, a(n) equals the permanent of the (2*n-2) X (2*n-2) 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
%C A001835 Primes in the sequence are apparently those in A096147. - _R. J. Mathar_, May 09 2013
%C A001835 Except for the first term, positive values of x (or y) satisfying x^2 - 4xy + y^2 + 2 = 0. - _Colin Barker_, Feb 04 2014
%C A001835 Except for the first term, positive values of x (or y) satisfying x^2 - 14xy + y^2 + 32 = 0. - _Colin Barker_, Feb 10 2014
%C A001835 The (1,1) element of A^n where A = (1, 1, 1; 1, 2, 1; 1, 1, 2). - _David Neil McGrath_, Jul 23 2014
%C A001835 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
%C A001835 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
%C A001835 a(n)/A001353(n) is the resistance of an n-ladder graph whose edges are replaced by one-ohm resistors. The resistance in ohms is measured at two nodes at one end of the ladder. It approaches sqrt(3) - 1 for n -> oo. See A342568, A357113, and A357115 for related information. - _Hugo Pfoertner_, Sep 17 2022
%C A001835 a(n) is the number of ways to tile a 1 X (n-1) strip with three types of tiles: small isosceles right triangles (with small side length 1), 1 X 1 squares formed by joining two of those right triangles along the hypotenuse, and large isosceles right triangles (with large side length 2) formed by joining two of those right triangles along a short leg. As an example, here is one of the a(6)=571 ways to tile a 1 X 5 strip with these kinds of tiles:
%C A001835 ______________
%C A001835 | / \ |\ /| |
%C A001835 |/___\|_\_/_|__|. - _Greg Dresden_ and Arjun Datta, Jun 30 2023
%C A001835 From _Klaus Purath_, May 11 2024: (Start)
%C A001835 For any two consecutive terms (a(n), a(n+1)) = (x,y): x^2 - 4xy + y^2 = -2 = A028872(-1). In general, the following applies to all sequences (t) satisfying t(i) = 4t(i-1) - t(i-2) with t(0) = 1 and two consecutive terms (x,y): x^2 - 4xy + y^2 = A028872(t(1)-2). This includes and interprets the Feb 04 2014 comments here and on A001075 by _Colin Barker_ and the Dec 12 2012 comment on A001353 by _Max Alekseyev_. By analogy to this, for three consecutive terms (x,y,z) y^2 - xz = A028872(t(1)-2). This includes and interprets the Jul 10 2021 comment on A001353 by _Bernd Mulansky_.
%C A001835 If (t) is a sequence satisfying t(k) = 3t(k-1) + 3t(k-2) - t(k-3) or t(k) = 4t(k-1) - t(k-2) without regard to initial values and including this sequence itself, then a(n) = (t(k+2n+1) + t(k))/(t(k+n+1) + t(k+n)) always applies, as long as t(k+n+1) + t(k+n) != 0 for integer k and n >= 1. (End)
%C A001835 Binomial transform of 1, 0, 2, 4, 12, … (A028860 without the initial -1) and reverse binomial transform of 1, 2, 6, 24, 108, … (A094433 without the initial 1). - _Klaus Purath_, Sep 09 2024
%D A001835 R. C. Alperin, A family of nonlinear recurrences and their linear solutions, Fib. Q., 57:4 (2019), 318-321.
%D A001835 Julio R. Bastida, 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. 163-166, Congress. Numer., XXIII-XXIV, Utilitas Math., Winnipeg, Man., 1979. MR0561042 (81e:10009).
%D A001835 L. Euler, (E388) Vollstaendige Anleitung zur Algebra, Zweiter Theil, reprinted in: Opera Omnia. Teubner, Leipzig, 1911, Series (1), Vol. 1, p. 375.
%D A001835 F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Ars Combin. 49 (1998), 129-154.
%D A001835 R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 329.
%D A001835 Serge Lang, Introduction to Diophantine Approximations, Addison-Wesley, New York, 1966.
%D A001835 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A001835 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D A001835 R. P. Stanley, Enumerative Combinatorics I, p. 292.
%H A001835 T. D. Noe, Table of n, a(n) for n = 0..200
%H A001835 Mudit Aggarwal and Samrith Ram, Generating functions for straight polyomino tilings of narrow rectangles, arXiv:2206.04437 [math.CO], 2022.
%H A001835 Krassimir T. Atanassov and Anthony G. Shannon, On intercalated Fibonacci sequences, Notes on Number Theory and Discrete Mathematics (2020) Vol. 26, No. 3, 218-223.
%H A001835 Steve Butler, Paul Horn, and Eric Tressler, Intersecting Domino Tilings, Fibonacci Quart. 48 (2010), no. 2, 114-120.
%H A001835 Niccolò Castronuovo, On the number of fixed points of the map gamma, arXiv:2102.02739 [math.NT], 2021. Mentions this sequence.
%H A001835 A. Consilvio et al., Tilings, ordered partitions, and weird languages, MAA FOCUS, June/July 2012, 16-17.
%H A001835 J. B. Cosgrave and K. Dilcher, A role for generalized Fermat numbers, Math. Comp., to appear 2016; (See paper #10).
%H A001835 J. B. Cosgrave and K. Dilcher, A role for generalized Fermat numbers, Math. Comp. 86 (2017), 899-933.
%H A001835 L. Euler, Vollstaendige Anleitung zur Algebra, Zweiter Teil.
%H A001835 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), 129-154.
%H A001835 F. Faase, Counting Hamiltonian cycles in product graphs.
%H A001835 F. Faase, Results from the counting program.
%H A001835 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. 76-114. See Section 13.
%H A001835 Darren B. Glass, Critical groups of graphs with dihedral actions. II, Eur. J. Comb. 61, 25-46 (2017).
%H A001835 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 three-dimensional rectangular and torus lattices, J. Math. Physics 26 (1985) 157-167 (Table V).
%H A001835 INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 409.
%H A001835 Tanya Khovanova, Recursive Sequences,
%H A001835 Clark Kimberling, Best lower and upper approximates to irrational numbers, Elemente der Mathematik, 52 (1997) 122-126.
%H A001835 David Klarner and Jordan Pollack, Domino tilings of rectangles with fixed width, Disc. Math. 32 (1980) 45-52.
%H A001835 R. J. Mathar, Paving Rectangular Regions with Rectangular Tiles: Tatami and Non-Tatami Tilings, arXiv:1311.6135 [math.CO], 2013, Table 2.
%H A001835 R. J. Mathar, Tilings of rectangular regions by rectangular tiles: Counts derived from transfer matrices, arXiv:1406.7788 (2014), eq. (4).
%H A001835 Valcho Milchev and Tsvetelina Karamfilova, Domino tiling in grid - new dependence, arXiv:1707.09741 [math.HO], 2017.
%H A001835 Yong Hao Ng, A partition in three classes of the set of all prime numbers?, Math StackExchange.
%H A001835 J.-C. Novelli and J.-Y. Thibon, Hopf Algebras of m-permutations,(m+1)-ary trees, and m-parking functions, arXiv preprint arXiv:1403.5962 [math.CO], 2014.
%H A001835 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.
%H A001835 Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992.
%H A001835 Jaime Rangel-Mondragon, Polyominoes and Related Families, The Mathematica Journal, 9:3 (2005), 609-640.
%H A001835 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 N-numbers, not their A-numbers.
%H A001835 David Singmaster, Letter to N. J. A. Sloane, Oct 3 1982.
%H A001835 Anitha Srinivasan, The Markoff-Fibonacci Numbers, Fibonacci Quart. 58 (2020), no. 5, 222-228.
%H A001835 Thotsaporn "Aek" Thanatipanonda, Statistics of Domino Tilings on a Rectangular Board, Fibonacci Quart. 57 (2019), no. 5, 145-153. See p. 151.
%H A001835 Herman Tulleken, Polyominoes 2.2: How they fit together, (2019).
%H A001835 F. V. Waugh and M. W. Maxfield, Side-and-diagonal numbers, Math. Mag., 40 (1967), 74-83.
%H A001835 Index entries for sequences related to dominoes.
%H A001835 Index entries for sequences related to Chebyshev polynomials.
%H A001835 Index entries for linear recurrences with constant coefficients, signature (4,-1).
%F A001835 G.f.: (1 - 3*x)/(1 - 4*x + x^2). - _Simon Plouffe_ in his 1992 dissertation
%F A001835 a(1-n) = a(n).
%F A001835 a(n) = ((3 + sqrt(3))^(2*n - 1) + (3 - sqrt(3))^(2*n - 1))/6^n. - _Dean Hickerson_, Dec 01 2002
%F A001835 a(n) = (8 + a(n-1)*a(n-2))/a(n-3). - _Michael Somos_, Aug 01 2001
%F A001835 a(n+1) = Sum_{k=0..n} 2^k * binomial(n + k, n - k), n >= 0. - _Len Smiley_, Dec 09 2001
%F A001835 Limit_{n->oo} a(n)/a(n-1) = 2 + sqrt(3). - _Gregory V. Richardson_, Oct 10 2002
%F A001835 a(n) = 2*A061278(n-1) + 1 for n > 0. - Bruce Corrigan (scentman(AT)myfamily.com), Nov 04 2002
%F A001835 Let q(n, x) = Sum_{i=0..n} x^(n-i)*binomial(2*n - i, i); then q(n, 2) = a(n+1). - _Benoit Cloitre_, Nov 10 2002
%F A001835 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
%F A001835 a(n) = S(n-1, 4) - S(n-2, 4) = T(2*n-1, sqrt(3/2))/sqrt(3/2) = S(2*(n-1), 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.
%F A001835 a(n+1) = sqrt((A001834(n)^2 + 2)/3), n >= 0 (see Cloitre comment).
%F A001835 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
%F A001835 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). - _Sarah-Marie Belcastro_, Jul 04 2009
%F A001835 If p[1] = 3, p[i] = 2, (i > 1), and if A is Hessenberg matrix of order n defined by: A[i,j] = p[j-i+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
%F A001835 a(n) = (a(n-1)^2 + 2)/a(n-2). - _Irene Sermon_, Oct 28 2013
%F A001835 a(n) = A001353(n+1) - 3*A001353(n). - _R. J. Mathar_, Oct 30 2015
%F A001835 a(n) = a(n-1) + 2*A001353(n-1). - _Kevin Long_, May 04 2018
%F A001835 From _Franck Maminirina Ramaharo_, Nov 11 2018: (Start)
%F A001835 a(n) = (-1)^n*(A125905(n) + 3*A125905(n-1)), n > 0.
%F A001835 E.g.f.: exp^(2*x)*(3*cosh(sqrt(3)*x) - sqrt(3)*sinh(sqrt(3)*x))/3. (End)
%F A001835 From _Peter Bala_, Feb 12 2024: (Start)
%F A001835 For n in Z, a(n) = A001353(n) + A001353(1-n).
%F A001835 For n, j, k in Z, a(n)*a(n+j+k) - a(n+j)*a(n+k) = 2*A001353(j)*A001353(k). The case j = 1, k = 2 is given above. (End)
%p A001835 f:=n->((3+sqrt(3))^(2*n-1)+(3-sqrt(3))^(2*n-1))/6^n; [seq(simplify(expand(f(n))),n=0..20)]; # _N. J. A. Sloane_, Nov 10 2009
%t A001835 CoefficientList[Series[(1-3x)/(1-4x+x^2), {x, 0, 24}], x] (* _Jean-François Alcover_, Jul 25 2011, after g.f. *)
%t A001835 LinearRecurrence[{4,-1},{1,1},30] (* _Harvey P. Dale_, Jun 08 2013 *)
%t A001835 Table[Round@Fibonacci[2n-1, Sqrt[2]], {n, 0, 20}] (* _Vladimir Reshetnikov_, Sep 15 2016 *)
%t A001835 Table[(3*ChebyshevT[n, 2] - ChebyshevU[n, 2])/2, {n, 0, 20}] (* _G. C. Greubel_, Dec 23 2019 *)
%o A001835 (PARI) {a(n) = real( (2 + quadgen(12))^n * (1 - 1 / quadgen(12)) )} /* _Michael Somos_, Sep 19 2008 */
%o A001835 (PARI) {a(n) = subst( (polchebyshev(n) + polchebyshev(n-1)) / 3, x, 2)} /* _Michael Somos_, Sep 19 2008 */
%o A001835 (Sage) [lucas_number1(n,4,1)-lucas_number1(n-1,4,1) for n in range(25)] # _Zerinvary Lajos_, Apr 29 2009
%o A001835 (Sage) [(3*chebyshev_T(n,2) - chebyshev_U(n,2))/2 for n in (0..20)] # _G. C. Greubel_, Dec 23 2019
%o A001835 (Haskell)
%o A001835 a001835 n = a001835_list !! n
%o A001835 a001835_list =
%o A001835 1 : 1 : zipWith (-) (map (4 *) $ tail a001835_list) a001835_list
%o A001835 -- _Reinhard Zumkeller_, Aug 14 2011
%o A001835 (Magma) [n le 2 select 1 else 4*Self(n-1)-Self(n-2): n in [1..25]]; // _Vincenzo Librandi_, Sep 16 2016
%o A001835 (GAP) a:=[1,1];; for n in [3..20] do a[n]:=4*a[n-1]-a[n-2]; od; a; # _G. C. Greubel_, Dec 23 2019
%Y A001835 Row 3 of array A099390.
%Y A001835 Essentially the same as A079935.
%Y A001835 First differences of A001353.
%Y A001835 Partial sums of A052530.
%Y A001835 Pairwise sums of A006253.
%Y A001835 Bisection of A002530, A005246 and A048788.
%Y A001835 First column of array A103997.
%Y A001835 Cf. A001519, A003699, A082841, A101265, A125077, A001353, A001542, A096147 (subsequence of primes).
%K A001835 nonn,easy,nice
%O A001835 0,3
%A A001835 _N. J. A. Sloane_
# Content is available under The OEIS End-User License Agreement: http://oeis.org/LICENSE