Search: a005386 -id:a005386
|
|
A004253
|
|
a(n) = 5*a(n-1) - a(n-2), with a(1)=1, a(2)=4.
(Formerly M3553)
|
|
+10
38
|
|
|
1, 4, 19, 91, 436, 2089, 10009, 47956, 229771, 1100899, 5274724, 25272721, 121088881, 580171684, 2779769539, 13318676011, 63813610516, 305749376569, 1464933272329, 7018916985076, 33629651653051, 161129341280179
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
Number of domino tilings in K_3 X P_2n (or in S_4 X P_2n).
Number of perfect matchings in graph C_{3} X P_{2n}.
Number of perfect matchings in S_4 X P_2n.
In general, Sum_{k=0..n} binomial(2*n-k, k)*j^(n-k) = (-1)^n * U(2*n, i*sqrt(j)/2), i=sqrt(-1). - Paul Barry, Mar 13 2005
Number of 01-avoiding words of length n on alphabet {0,1,2,3,4} which do not end in 0 (e.g., at n=2, we have 02, 03, 04, 11, 12, 13, 14, 21, 22, 23, 24, 31, 32, 33, 34, 41, 42, 43, 44). - Tanya Khovanova, Jan 10 2007
(sqrt(21)+5)/2 = 4.7912878... = exp(arccosh(5/2)) = 4 + 3/4 + 3/(4*19) + 3/(19*91) + 3/(91*436) + ... - Gary W. Adamson, Dec 18 2007
a(n+1) is the number of compositions of n when there are 4 types of 1 and 3 types of other natural numbers. - Milan Janjic, Aug 13 2010
For n >= 2, a(n) equals the permanent of the (2n-2) X (2n-2) tridiagonal matrix with sqrt(3)'s along the main diagonal, and 1's along the superdiagonal and the subdiagonal. - John M. Campbell, Jul 08 2011
Values of x (or y) in the solutions to x^2 - 5xy + y^2 + 3 = 0. - Colin Barker, Feb 04 2014
All positive solutions of the Diophantine equation x^2 + y^2 - 5*x*y = -3 (see the preceding comment) are given by [x(n) = S(n, 5) - S(n-1, 5), y(n) = x(n-1)], for n =-oo..+oo, with the Chebyshev S-polynomials (A049310), with S(-1, 0) = 0, and S(-|n|, x) = - S(|n|-2, x), for |n| >= 2.
This binary indefinite quadratic form has discriminant D = +21. There is only this family representing -3 properly with x and y positive, and there are no improper solutions.
See the formula for a(n) = x(n-1), for n >= 1, in terms of S-polynomials below.
This comment is inspired by a paper by Robert K. Moniot (private communication). See his Oct 04 2020 comment in A027941 related to the case of x^2 + y^2 - 3*x*y = -1 (special Markov solutions). (End)
All proper and improper solutions of the generalized Pell equation X^2 - 21*Y^2 = +4 are given, up to a combined sign change in X and Y, in terms of x(n) = a(n+1) from the preceding comment by X(n) = x(n) + x(n-1) = S(n-1, 5) - S(n-2, 5) and Y(n) = (x(n) - x(n-1))/3 = S(n-1, 5), for all integer numbers n. For positive integers X(n) = A003501(n) and Y(n) = A004254(n). X(-n) = X(n) and Y(-n) = - Y(n), for n >= 1.
The two conjugated proper families of solutions are given by [X(3*n+1), Y(3*n+1)] and [X(3*n+2), Y(3*n+2)], and the one improper family by [X(3*n), Y(3*n)], for all integer n. This follows from the mentioned paper by Robert K. Moniot. (End)
Equivalent definition: a(n) = ceiling(a(n-1)^2 / a(n-2)), with a(1)=1, a(2)=4, a(3)=19. The problem for USA Olympiad (see Andreescu and Gelca reference) asks to prove that a(n)-1 is always a multiple of 3. - Bernard Schott, Apr 13 2022
|
|
REFERENCES
|
Titu Andreescu and Rǎzvan Gelca, Putnam and Beyond, New York, Springer, 2007, problem 311, pp. 104 and 466-467 (proposed for the USA Mathematical Olympiad by G. Heuer).
F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Ars Combin. 49 (1998), 129-154.
F. A. Haight, On a generalization of Pythagoras' theorem, pp. 73-77 of J. C. Butcher, editor, A Spectrum of Mathematics. Auckland University Press, 1971.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
LINKS
|
|
|
FORMULA
|
G.f.: x*(1 - x) / (1 - 5*x + x^2). Simon Plouffe in his 1992 dissertation.[offset 0]
a(n) ~ (1/2 + 1/14*sqrt(21))*(1/2*(5 + sqrt(21)))^n. - Joe Keane (jgk(AT)jgk.org), May 16 2002[offset 0]
Let q(n, x) = Sum_{i=0..n} x^(n-i)*binomial(2*n-i, i), then q(n, 3)=a(n). - Benoit Cloitre, Nov 10 2002 [offset 0]
For n>0, a(n)*a(n+3) = 15 + a(n+1)*a(n+2). - Ralf Stephan, May 29 2004
a(n) = Sum_{k=0..n} binomial(n+k, 2k)*3^k. - Paul Barry, Jul 26 2004[offset 0]
a(n) = (-1)^n*U(2n, i*sqrt(3)/2), U(n, x) Chebyshev polynomial of second kind, i=sqrt(-1). - Paul Barry, Mar 13 2005[offset 0]
a(n) = ((sqrt(21)-3)*((5+sqrt(21))/2)^n + (sqrt(21)+3)*((5-sqrt(21))/2)^n)/2/sqrt(21). - Seiichi Kirikami, Sep 06 2011
a(n) = S(n-1, 5) - S(n-2, 5) = (-1)^n*S(2*n, i*sqrt(3)), n >= 1, with the Chebyshev S polynomials (A049310), and S(n-1, 5) = A004254(n), for n >= 0. See a Paul Barry formula (offset corrected). - Wolfdieter Lang, Oct 15 2020
a(n) = a(1-n).
For n, j, k in Z, a(n)*a(n+j+k) - a(n+j)*a(n+k) = 3*A004254(j)*A004254(k). The case j = 1, k = 2 is given above.
a(n)^2 + a(n+1)^2 - 5*a(n)*a(n+1) = - 3.
|
|
MAPLE
|
a[0]:=1: a[1]:=1: for n from 2 to 26 do a[n]:=5*a[n-1]-a[n-2] od: seq(a[n], n=1..22); # Zerinvary Lajos, Jul 26 2006
|
|
MATHEMATICA
|
|
|
PROG
|
(Sage) [lucas_number1(n, 5, 1)-lucas_number1(n-1, 5, 1) for n in range(1, 23)] # Zerinvary Lajos, Nov 10 2009
(Magma) [ n eq 1 select 1 else n eq 2 select 4 else 5*Self(n-1)-Self(n-2): n in [1..30] ]; // Vincenzo Librandi, Aug 19 2011
(GAP) a:=[1, 4];; for n in [3..30] do a[n]:=5*a[n-1]-a[n-2]; od; a; # G. C. Greubel, Oct 23 2019
|
|
CROSSREFS
|
Cf. similar sequences listed in A238379.
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|
|
A092936
|
|
Area of n-th triple of hexagons around a triangle.
|
|
+10
11
|
|
|
1, 9, 100, 1089, 11881, 129600, 1413721, 15421329, 168220900, 1835008569, 20016873361, 218350598400, 2381839709041, 25981886201049, 283418908502500, 3091626107326449, 33724468272088441, 367877524885646400
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
This is the unsigned member r=-9 of the family of Chebyshev sequences S_r(n) defined in A092184: ((-1)^(n+1))*a(n) = S_{-9}(n), n>=0.
a(n+1) is the number of tilings of an n-board (a board with dimensions n X 1) using (1/2,1/2)-fences, red half-squares (1/2 X 1 pieces, always placed so that the shorter sides are horizontal), green half-squares, and blue half-squares. A (w,g)-fence is a tile composed of two w X 1 pieces separated by a gap of width g. a(n+1) also equals the number of tilings of an n-board using (1/4,3/4)-fences, red (1/4,1/4)-fences, green (1/4,1/4)-fences, and blue (1/4,1/4)-fences. - Michael A. Allen, Dec 30 2022
|
|
LINKS
|
|
|
FORMULA
|
a(n) = 10*(a(n-1)+a(n-2)) - a(n-3).
G.f.: (1-x)*x/(1-10*x-10*x^2+x^3).
a(n) = ((3-sqrt(13))^n-(3+sqrt(13))^n)^2/(13*4^n).
a(n) = 2*(T(n, 11/2)-(-1)^n)/13 with twice the Chebyshev polynomials of the first kind evaluated at x=11/2: 2*T(n, 11/2)=A057076(n)=((11+3*sqrt(13))^n + (11-3*sqrt(13))^n)/2^n. - Wolfdieter Lang, Oct 18 2004
a(n+1) = 11*a(n) - a(n-1) + 2*(-1)^n.
a(n+1) = (1 + (-1)^n)/2 + 9*Sum_{k=1..n} ( k*a(n+1-k) ). (End)
|
|
EXAMPLE
|
a(5) = 10*(1089+100)-9 = 11881. From A006190, a(5) = (3*33+10)^2 = 11881.
|
|
MAPLE
|
|
|
MATHEMATICA
|
CoefficientList[Series[(1-x)*x/(1-10*x-10*x^2+x^3), {x, 0, 20}], x]
(CoefficientList[Series[x/(1-3*x-x^2), {x, 0, 20}], x])^2
Table[Round[((3+Sqrt[13])^n)^2/(13*4^n)], {n, 0, 20}]
LinearRecurrence[{10, 10, -1}, {1, 9, 100}, 18] (* Georg Fischer, Feb 22 2019 *)
|
|
PROG
|
(GAP) a:=[1, 9, 100];; for n in [4..18] do a[n]:=10*(a[n-1]+a[n-2])-a[n-3]; od; a; # Muniru A Asiru, Feb 20 2018
|
|
CROSSREFS
|
|
|
KEYWORD
|
easy,nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|
|
A003769
|
|
Number of perfect matchings (or domino tilings) in K_4 X P_n.
|
|
+10
4
|
|
|
3, 16, 75, 361, 1728, 8281, 39675, 190096, 910803, 4363921, 20908800, 100180081, 479991603, 2299777936, 11018898075, 52794712441, 252954664128, 1211978608201, 5806938376875, 27822713276176, 133306628004003, 638710426743841, 3060245505715200
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,1
|
|
REFERENCES
|
F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Ars Combin. 49 (1998), 129-154.
|
|
LINKS
|
|
|
FORMULA
|
a(n) = 4a(n-1) + 4a(n-2) - a(n-3), n>3.
G.f.: x*(3+4*x-x^2)/((1+x)*(1-5*x+x^2)). - R. J. Mathar, Dec 16 2008
a(n) = 2^(-1-n)*((-1)^n*2^(2+n) + (5-sqrt(21))^(1+n) + (5+sqrt(21))^(1+n)) / 7. - Colin Barker, Dec 16 2017
|
|
PROG
|
(PARI) Vec(x*(3 + 4*x - x^2) / ((1 + x)*(1 - 5*x + x^2)) + O(x^40)) \\ Colin Barker, Dec 16 2017
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|
|
A099025
|
|
Expansion of 1 / ((1+x) * (1-5*x+x^2)).
|
|
+10
4
|
|
|
1, 4, 20, 95, 456, 2184, 10465, 50140, 240236, 1151039, 5514960, 26423760, 126603841, 606595444, 2906373380, 13925271455, 66719983896, 319674648024, 1531653256225, 7338591633100, 35161304909276, 168467932913279, 807178359657120, 3867423865372320
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
REFERENCES
|
R. C. Alperin, A nonlinear recurrence and its relations to Chebyshev polynomials, Fib. Q., 58:2 (2020), 140-142.
|
|
LINKS
|
|
|
FORMULA
|
G.f.: 1 / ((1 + x) * (1 - 5*x + x^2)).
a(n) = (2^(-n)*(3*(-2)^n+(9-2*sqrt(21))*(5-sqrt(21))^n+(5+sqrt(21))^n*(9+2*sqrt(21))))/21. - Colin Barker, Nov 02 2016
|
|
EXAMPLE
|
1 + 4*x + 20*x^2 + 95*x^3 + 456*x^4 + 2184*x^5 + 10465*x^6 + ...
|
|
MATHEMATICA
|
CoefficientList[Series[1/((1+x)*(1-5*x+x^2)), {x, 0, 50}], x] (* or *) LinearRecurrence[{4, 4, -1}, {1, 4, 20}, 30] (* G. C. Greubel, Dec 31 2017 *)
|
|
PROG
|
(PARI) {a(n) = (3 * (-1)^n + 38 * subst( poltchebi(n), x, 5/2) - 8 * subst( poltchebi(n-1), x, 5/2)) / 21} /* Michael Somos, Jan 25 2013 */
(Magma) I:=[1, 4, 20]; [n le 3 select I[n] else 4*Self(n-1) + 4*Self(n-2) - Self(n-3): n in [1..30]]; // G. C. Greubel, Dec 31 2017
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|
|
A340561
|
|
Square array T(n,k), n >= 1, k >= 1, read by antidiagonals, where T(n,k) = sqrt( Product_{a=1..n-1} Product_{b=1..k-1} (4*sin(a*Pi/n)^2 + 4*cos(b*Pi/k)^2) ).
|
|
+10
2
|
|
|
1, 1, 1, 1, 2, 1, 1, 5, 3, 1, 1, 12, 16, 4, 1, 1, 29, 75, 45, 5, 1, 1, 70, 361, 384, 121, 6, 1, 1, 169, 1728, 3509, 1805, 320, 7, 1, 1, 408, 8281, 31500, 30976, 8100, 841, 8, 1, 1, 985, 39675, 284089, 508805, 261725, 35287, 2205, 9, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,5
|
|
LINKS
|
|
|
EXAMPLE
|
Square array begins:
1, 1, 1, 1, 1, 1, ...
1, 2, 5, 12, 29, 70, ...
1, 3, 16, 75, 361, 1728, ...
1, 4, 45, 384, 3509, 31500, ...
1, 5, 121, 1805, 30976, 508805, ...
1, 6, 320, 8100, 261725, 7741440, ...
|
|
PROG
|
(PARI) default(realprecision, 120);
{T(n, k) = round(sqrt(prod(a=1, n-1, prod(b=1, k-1, 4*sin(a*Pi/n)^2+4*cos(b*Pi/k)^2))))}
|
|
CROSSREFS
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|
|
A094083
|
|
Numerators of ratio of sides of n-th triple of rectangles of unit area sum around a triangle.
|
|
+10
1
|
|
|
1, 1, 1, 4, 9, 64, 25, 256, 1225, 16384, 3969, 65536, 53361, 1048576, 184041, 4194304, 41409225, 1073741824, 147744025, 4294967296, 2133423721, 68719476736, 7775536041, 274877906944, 457028729521, 17592186044416, 1690195005625
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,4
|
|
COMMENTS
|
Page 13 of the link shows the type of configuration. When n is odd, the numerators 1,1,9,25,1225,3969,.. are A038534 and (A001790)^2, and the denominators 1,4,64,256,16384,65536,.. are A056982, A038533/2, and (A046161)^2. When n is even, the numerators 1,4,64,256,16384,65536,.. are A056982, A038533/2, and (A046161)^2, and the denominators 3,27,675,3675,297675,1440747,.. are 3*(A001803)^2. The limit of a(n+1)/a(n) as n(odd) tends to infinity = Pi^2/12, A072691. The limit of a(n+2)/a(n) as n tends to infinity = 1. a(n), for large odd n, tends to 2/(Pi*n). a(n), for large even n, tends to Pi/(6*n). The expansion of 2*x*EllipticK(x)/Pi gives the odd fractions. The expansion of 1/3*x*HypergeometricPFQ({1,1,1},{3/2,3/2},x) gives the even fractions.
|
|
LINKS
|
|
|
FORMULA
|
a(n)=a(n-2)*((n-2)/(n-1))^2, a(1)=1, a(2)=1/3. a(n)=((n/2-1)!)^2/(Pi*((n/2-1/2)!)^2) for n odd. a(n)=(2^(1-n)*(n-2)!!^2)/((n-1)/2)!^2 for n odd. a(n)=Pi*((n/2-1)!)^2/(12*((n/2-1/2)!)^2) for n even. a(n)=(2^(n-2)*((n-2)/2)!^2)/(3*(n-1)!!^2) for n even.
|
|
EXAMPLE
|
a(5) = a(5-2)*((5-2)/(5-1))^2 = 1/4*(3/4)^2 = 9/64
|
|
MATHEMATICA
|
a[n_]:=If[OddQ[n], ((n/2-1)!)^2/(Pi*((n/2-1/2)!)^2), Pi*((n/2-1)!)^2/(12*((n/2-1/2)!)^2)] a[n_]:=If[OddQ[n], (2^(1-n)*(n-2)!!^2)/((n-1)/2)!^2, (2^(n-2)*((n-2)/2)!^2)/(3*(n-1)!!^2)] a[n_]:=((12+Pi^2+E^(I*n*Pi)*(Pi^2-12))*((n/2-1)!)^2)/(24*Pi*((n/2-1/2)!)^2) (CoefficientList[Series[(I*x*(6+Sqrt[3]*Pi)-2*x*Sqrt[3]*Log[x+Sqrt[x^2-1]])/(6*Sqrt[x^2-1]), {x, 0, 20}], x])^2
|
|
CROSSREFS
|
|
|
KEYWORD
|
easy,frac,nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|
|
|
|
1, 3, 4, 27, 64, 675, 256, 3675, 16384, 297675, 65536, 1440747, 1048576, 27054027, 4194304, 124227675, 1073741824, 35901798075, 4294967296, 160006779075, 68719476736, 2822519582883, 274877906944, 12339775697067, 17592186044416
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
LINKS
|
|
|
CROSSREFS
|
|
|
KEYWORD
|
easy,frac,nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
Search completed in 0.011 seconds
|