login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual Appeal: Today, Nov 11 2014, is the 4th anniversary of the launch of the new OEIS web site. 70,000 sequences have been added in these four years, all edited by volunteers. Please make a donation (tax deductible in the US) to help keep the OEIS running.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001835 a(n) = 4*a(n-1) - a(n-2), with a(0)=1, a(1)=1.
(Formerly M2894 N1160)
56

%I M2894 N1160

%S 1,1,3,11,41,153,571,2131,7953,29681,110771,413403,1542841,5757961,

%T 21489003,80198051,299303201,1117014753,4168755811,15558008491,

%U 58063278153,216695104121,808717138331,3018173449203,11263976658481

%N a(n) = 4*a(n-1) - a(n-2), with a(0)=1, a(1)=1.

%C See A079935 for another version.

%C Number of ways of packing a 3 X 2(n-1) rectangle with dominoes. - David Singmaster.

%C Equivalently, number of perfect matchings of the P_3 X P_{2(n-1)} lattice graph. - _Emeric Deutsch_, Dec 28 2004

%C 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 Terms are the solutions to: 3x^2-2 is a square. - _Benoit Cloitre_, Apr 07 2002

%C 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 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 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 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 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 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 From _Gary W. Adamson_, Jun 21 2009: (Start)

%C A001835 and A001353 = bisection of denominators of continued fraction [1, 2, 1, 2, 1, 2,...]; i.e. bisection of A002530.

%C a(n) = determinant of an n*n tridiagonal matrix with 1's in the super- and sub-diagonals and (3,4,4,4,...) as the main diagonal.

%C Also, the product of the eigenvalues of such matrices: a(n) = PRODUCT_{k=1..(n-1)/2)} (4 + 2*Cos 2kPi/n).

%C (End)

%C 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->inf} M^n, the left-shifted vector considered as a sequence. - _Gary W. Adamson_, Jul 27 2010

%C 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 For n>= 2, a(n) equals the permanent of the (2n-2)X(2n-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 Primes in the sequence are apparently those in A096147. - _R. J. Mathar_, May 09 2013

%C 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 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 The (1,1) element of A^n where A=(1,1,1;1,2,1;1,1,2). - _David Neil McGrath_, Jul 23 2014

%D 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. 163--166, Congress. Numer., XXIII-XXIV, Utilitas Math., Winnipeg, Man., 1979. MR0561042 (81e:10009) - From _N. J. A. Sloane_, May 30 2012

%D L. Euler, (E388) Vollstaendige Anleitung zur Algebra, Zweiter Theil, reprinted in: Opera Omnia. Teubner, Leipzig, 1911, Series (1), Vol. 1, p. 375.

%D F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Ars Combin. 49 (1998), 129-154.

%D R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 329.

%D Serge Lang, Introduction to Diophantine Approximations, Addison-Wesley, New York, 1966.

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%D R. P. Stanley, Enumerative Combinatorics I, p. 292.

%H T. D. Noe, <a href="/A001835/b001835.txt">Table of n, a(n) for n = 0..200</a>

%H A. Consilvio et al., <a href="http://www.maa.org/pubs/FOCUSJun-Jul12_tanton.html">Tilings, ordered partitions, and weird languages</a>, MAA FOCUS, June/July 2012, 16-17.

%H L. Euler, <a href="http://www.mathematik.uni-bielefeld.de/~sieben/euler/euler_2.djvu">Vollstaendige Anleitung zur Algebra, Zweiter Teil</a>.

%H F. Faase, <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.37.2790">On the number of specific spanning subgraphs of the graphs G X P_n</a>, Preliminary version of paper that appeared in Ars Combin. 49 (1998), 129-154.

%H F. Faase, <a href="http://www.iwriteiam.nl/counting.html">Counting Hamilton cycles in product graphs</a>

%H F. Faase, <a href="http://www.iwriteiam.nl/Cresults.html">Results from the counting program</a>

%H H. Hosoya and A. Motoyama, <a href="http://dx.doi.org/10.1063/1.526778">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</a>, J. Math. Physics 26 (1985) 157-167 (Table V).

%H INRIA Algorithms Project, <a href="http://algo.inria.fr/ecs/ecs?searchType=1&amp;service=Search&amp;searchTerms=409">Encyclopedia of Combinatorial Structures 409</a>

%H Tanya Khovanova, <a href="http://www.tanyakhovanova.com/RecursiveSequences/RecursiveSequences.html">Recursive Sequences</a>

%H Clark Kimberling, <a href="http://dx.doi.org/10.1007/s000170050020">Best lower and upper approximates to irrational numbers</a>, Elemente der Mathematik, 52 (1997) 122-126.

%H David Klarner, Jordan Pollack, <a href="http://dx.doi.org/10.1016/0012-365X(80)90098-9">Domino tilings of rectangles with fixed width</a>, Disc. Math. 32 (1980) 45-52.

%H R. J. Mathar, <a href="http://arxiv.org/abs/1311.6135">Paving rectangular regions with rectangular tiles,....</a>, arXiv:1311.6135 [math.CO], Table 2.

%H J.-C. Novelli, J.-Y. Thibon, <a href="http://arxiv.org/abs/1403.5962">Hopf Algebras of m-permutations,(m+1)-ary trees, and m-parking functions</a>, arXiv preprint arXiv:1403.5962, 2014

%H Simon Plouffe, <a href="http://www.lacim.uqam.ca/%7Eplouffe/articles/MasterThesis.pdf">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992.

%H Simon Plouffe, <a href="http://www.lacim.uqam.ca/%7Eplouffe/articles/FonctionsGeneratrices.pdf">1031 Generating Functions and Conjectures</a>, Université du Québec à Montréal, 1992.

%H Jaime Rangel-Mondragon, <a href="http://www.mathematica-journal.com/issue/v9i3/polyominoes.html">Polyominoes and Related Families</a>, The Mathematica Journal, 9:3 (2005), 609-640.

%H F. V. Waugh and M. W. Maxfield, <a href="http://www.jstor.org/stable/2688511">Side-and-diagonal numbers</a>, Math. Mag., 40 (1967), 74-83.

%H <a href="/index/Do#domino">Index entries for sequences related to dominoes</a>

%H <a href="/index/Ch#Cheby">Index entries for sequences related to Chebyshev polynomials.</a>

%H <a href="/index/Rec#order_02">Index to sequences with linear recurrences with constant coefficients</a>, signature (4,-1).

%F G.f.: (1-3*x)/(1-4*x+x^2).

%F a(1-n) = a(n).

%F a(n) = ((3+sqrt(3))^(2*n-1)+(3-sqrt(3))^(2*n-1))/6^n. - _Dean Hickerson_, Dec 01 2002

%F a(n) = (8+a(n-1)*a(n-2))/a(n-3). - _Michael Somos_, Aug 01, 2001

%F a(n+1) = sum(2^k * binomial(n+k, n-k), k=0..n), n>=0. - Len Smiley (smiley(AT)math.uaa.alaska.edu), Dec 09 2001

%F Lim. n -> Inf. a(n)/a(n-1) = 2 + Sqrt(3). - _Gregory V. Richardson_, Oct 10 2002

%F a(n)=2*A061278(n-1)+1 for n>0 - Bruce Corrigan (scentman(AT)myfamily.com), Nov 04 2002

%F 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 a(n+1)= sum(((-1)^k)*((2*n+1)/(2*n+1-k))*binomial(2*n+1-k,k)*6^(n-k),k=0..n) (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 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 a(n+1)=sqrt((A001834(n)^2 + 2)/3), n>=0 (see Cloitre comment).

%F 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 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). [From Sarah-Marie Belcastro (smbelcas(AT)toroidalsnark.net), Jul 04 2009]

%F 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 a(n) = (a(n-1)^2 + 2)/a(n-2). - _Irene Sermon_, Oct 28 2013

%p A001835:=-(-1+3*z)/(1-4*z+z**2); [_Simon Plouffe_ in his 1992 dissertation.]

%p 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 CoefficientList[Series[(1-3x)/(1-4x+x^2), {x, 0, 24}], x] (* _Jean-François Alcover_, Jul 25 2011, after g.f. *)

%t LinearRecurrence[{4,-1},{1,1},30] (* _Harvey P. Dale_, Jun 08 2013 *)

%o (PARI) {a(n) = real( (2 + quadgen(12))^n * (1 - 1 / quadgen(12)) )} /* _Michael Somos_, Sep 19 2008 */

%o (PARI) {a(n) = subst( (polchebyshev(n) + polchebyshev(n-1)) / 3, x, 2)} /* _Michael Somos_, Sep 19 2008 */

%o (Sage) [lucas_number1(n,4,1)-lucas_number1(n-1,4,1) for n in xrange(0, 25)] # _Zerinvary Lajos_, Apr 29 2009

%o (Haskell)

%o a001835 n = a001835_list !! n

%o a001835_list =

%o 1 : 1 : zipWith (-) (map (4 *) $ tail a001835_list) a001835_list

%o -- _Reinhard Zumkeller_, Aug 14 2011

%Y Row 3 of array A099390.

%Y Essentially the same as A079935.

%Y First differences of A001353.

%Y Partial sums of A052530.

%Y Pairwise sums of A006253.

%Y Bisection of A002530, A005246 and A048788.

%Y First column of array A103997.

%Y Cf. A001519, A003699, A082841, A101265, A125077, A001353, A001542.

%K nonn,easy,nice

%O 0,3

%A _N. J. A. Sloane_.

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified November 24 15:00 EST 2014. Contains 249899 sequences.