|
| |
|
|
A001835
|
|
a(n) = 4*a(n-1) - a(n-2), a(0)=1, a(1)=1.
(Formerly M2894 N1160)
|
|
44
| |
|
|
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; internal format)
|
|
|
|
OFFSET
| 0,3
|
|
|
COMMENTS
| See A079935 for another version.
Number of ways of packing a 3 X 2(n-1) rectangle with dominoes. - David Singmaster.
Equivalently, number of perfect matchings of the P_3 X P_{2(n-1)} 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: 3x^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(n-1,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 01-avoiding words of length n on alphabet {0,1,2,3} which do not end in 0. (e.g. 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
Contribution 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 [1, 3, 4, 11, 15, 41, 56,...].
A001835 and A001353 = rightmost border and adjacent diagonal of triangle A125077.
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 and a(n) = PRODUCT_(k=1..(n-1)/2)} (4 + 2*Cos 2kPi/n.
(End)
Contribution from Gary W. Adamson, Jul 27 2010: (Start)
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. A001835
starting (1, 3, 11,...) = Lim_{n->inf} M^n, the left-shifted vector
considered as a sequence. (End)
a(n+1) is the number of compositions of n when there are 3 types of 1 and 2 types of other natural numbers. [From Milan R. Janjic (agnus(AT)blic.net), Aug 13 2010]
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. [From John M. Campbell, Jul 08 2011]
|
|
|
REFERENCES
| 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), 129-154.
R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 329.
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).
Clark Kimberling, "Best lower and upper approximates to irrational numbers," Elemente der Mathematik, 52 (1997) 122-126.
Serge Lang, Introduction to Diophantine Approximations, Addison-Wesley, New York, 1966.
Jaime Rangel-Mondragon, Polyominoes and Related Families, The Mathematica Journal, 9:3 (2005), 609-640.
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.
F. V. Waugh and M. W. Maxfield, Side-and-diagonal numbers, Math. Mag., 40 (1967), 74-83.
|
|
|
LINKS
| T. D. Noe, Table of n, a(n) for n=0..200
L. Euler, Vollstaendige Anleitung zur Algebra, Zweiter Teil.
F. Faase, Counting Hamilton cycles in product graphs
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.
F. Faase, Counting Hamilton cycles in product graphs
F. Faase, Results from the counting program
Tanya Khovanova, Recursive Sequences
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 409
S. Plouffe, Approximations de S\'{e}ries G\'{e}n\'{e}ratrices et Quelques Conjectures, Dissertation, Universit\'{e} du Qu\'{e}bec \`{a} Montr\'{e}al, 1992.
S. Plouffe, 1031 Generating Functions and Conjectures, Universit\'{e} du Qu\'{e}bec \`{a} Montr\'{e}al, 1992.
Index entries for sequences related to dominoes
Index entries for sequences related to Chebyshev polynomials.
Index entries for sequences related to linear recurrences with constant coefficients
|
|
|
FORMULA
| a(n) = ((3+sqrt(3))^(2*n-1)+(3-sqrt(3))^(2*n-1))/6^n. - Dean Hickerson (dean.hickerson(AT)yahoo.com), Dec 01 2002
a(n)=(8+a(n-1)a(n-2))/a(n-3) - Michael Somos, Aug 01, 2001
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
Lim. n -> Inf. a(n)/a(n-1) = 2 + Sqrt(3). - Gregory V. Richardson (omomom(AT)hotmail.com), Oct 10 2002
a(n)=2*A061278(n-1)+1 for n>0 - Bruce Corrigan (scentman(AT)myfamily.com), Nov 04 2002
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
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.
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.
a(n+1)=sqrt((A001834(n)^2 + 2)/3), n>=0 (see Cloitre comment).
G.f.: (1-3*x)/(1-4*x+x^2). a(1-n)=a(n).
a(1-n)=a(n). - Michael Somos Aug 07 2006
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
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]
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. [From Milan R. Janjic (agnus(AT)blic.net), Apr 29 2010]
|
|
|
MAPLE
| A001835:=-(-1+3*z)/(1-4*z+z**2); [S. Plouffe in his 1992 dissertation.]
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]
|
|
|
MATHEMATICA
| CoefficientList[Series[(1-3x)/(1-4x+x^2), {x, 0, 24}], x] (* From Jean-François Alcover, Jul 25 2011, after g.f. *)
|
|
|
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(n-1)) / 3, x, 2)} /* Michael Somos Sep 19 2008 */
(Sage) [lucas_number1(n, 4, 1)-lucas_number1(n-1, 4, 1) for n in xrange(0, 25)]# [From Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Apr 29 2009]
(Haskell)
a001835 n = a001835_list !! n
a001835_list =
1 : 1 : zipWith (-) (map (4 *) $ tail a001835_list) a001835_list
-- Reinhard Zumkeller, Aug 14 2011
|
|
|
CROSSREFS
| Cf. A001519 (similar summation)
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. Cf. A003699, A082841.
First column of array A103997.
Cf. A101265.
Cf. A125077 [From Gary W. Adamson, Jun 21 2009]
Cf. A001353, A001542.
Sequence in context: A077831 A032952 * A079935 A113437 A076540 A196472
Adjacent sequences: A001832 A001833 A001834 * A001836 A001837 A001838
|
|
|
KEYWORD
| nonn,easy,nice
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com).
|
|
|
EXTENSIONS
| Chebyshev comments from W. Lang (wolfdieter.lang(AT)physik.uni-karlsruhe.de), Nov 29 2002
|
| |
|
|
