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

 

Logo

Invitation: celebrating 50 years of OEIS, 250000 sequences, and Sloane's 75th, there will be a conference at DIMACS, Rutgers, Oct 9-10 2014.

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/Rea#recLCC">Index entries for sequences related to linear recurrences with constant coefficients</a>

%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 August 27 17:21 EDT 2014. Contains 246147 sequences.