A180142 -id:A180142 - cp's OEIS frontend

A155116 a(n) = 3a(n-1) + 3a(n-2), n>2, a(0)=1, a(1)=2, a(2)=8.

1, 2, 8, 30, 114, 432, 1638, 6210, 23544, 89262, 338418, 1283040, 4864374, 18442242, 69919848, 265086270, 1005018354, 3810313872, 14445996678, 54768931650, 207644784984, 787241149902, 2984657804658, 11315696863680, 42901064005014

Offset: 0

Philippe Deléham, Jan 20 2009

From Johannes W. Meijer, Aug 14 2010: (Start)
A berserker sequence, see A180140 and A180147. For the central square 16 A[5] vectors with decimal values between 3 and 384 lead to this sequence. These vectors lead for the corner squares to A123620 and for the side squares to A180142.
This sequence belongs to a family of sequences with GF(x)=(1-(2*k-1)*x-k*x^2)/(1-3*x+(k-4)*x^2). Berserker sequences that are members of this family are A000007 (k=2), A155116 (k=1; this sequence), A000302 (k=0), 6*A179606 (k=-1; with leading 1 added) and 2*A180141 (k=-2; n>=1 and a(0)=1). Some other members of this family are (-2)*A003688 (k=3; with leading 1 added), (-4)*A003946 (k=4; with leading 1 added), (-6)*A002878 (k=5; with leading 1 added) and (-8)*A033484 (k=6; with leading 1 added).
Inverse binomial transform of A101368 (without the first leading 1).
(End)

G. C. Greubel, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (3,3).

Sequences of the form a(n) = m*(a(n-1) + a(n-2)) with a(0)=1, a(1) = m-1, a(2) = m^2 -1: A155020 (m=2), this sequence (m=3), A155117 (m=4), A155119 (m=5), A155127 (m=6), A155130 (m=7), A155132 (m=8), A155144 (m=9), A155157 (m=10).

m:=3; [1] cat [n le 2 select (m-1)*(m*n-(m-1)) else m*(Self(n-1) + Self(n-2)): n in [1..30]]; // G. C. Greubel, Mar 25 2021

With[{m=3}, LinearRecurrence[{m, m}, {1, m-1, m^2-1}, 30]] (* G. C. Greubel, Mar 25 2021 *)

Vec((1-x-x^2)/(1-3*x-3*x^2)+O(x^99)) \\ Charles R Greathouse IV, Jan 12 2012

m=3; [1]+[-(m-1)*(sqrt(m)*i)^(n-2)*chebyshev_U(n, -sqrt(m)*i/2) for n in (1..30)] # G. C. Greubel, Mar 25 2021

G.f.: (1-x-x^2)/(1-3*x-3*x^2).
a(n) = 2*A125145(n-1), n>=1 .
a(n) = ( (2+4*A)*A^(-n-1) + (2+4*B)*B^(-n-1) )/21 with A=(-3+sqrt(21))/6 and B=(-3-sqrt(21))/6 for n>=1 with a(0)=1. [corrected by Johannes W. Meijer, Aug 12 2010]
Contribution from Johannes W. Meijer, Aug 14 2010: (Start)
a(n) = A123620(n)/2 for n>=1.
(End)
a(n) = (1/3)*[n=0] - 2*(sqrt(3)*i)^(n-2)*ChebyshevU(n, -sqrt(3)*i/2). - G. C. Greubel, Mar 25 2021

A180140 Eight rooks and one berserker on a 3 X 3 chessboard. G.f.: (1+x+x^2)/(1-3x-5x^2).

Original entry on oeis.org

1, 4, 18, 74, 312, 1306, 5478, 22964, 96282, 403666, 1692408, 7095554, 29748702, 124723876, 522915138, 2192364794, 9191670072, 38536834186, 161568852918, 677390729684, 2840016453642, 11907003009346, 49921091296248

Offset: 0

Johannes W. Meijer, Aug 13 2010, Jun 15 2013

a(n) gives the number of n-move routes of a fairy chess piece starting in a given side square (m = 2, 4, 6,  8) on a 3 X 3 chessboard. This fairy chess piece behaves like a rook on the four side and four corner (m = 1, 3, 7, 9) squares but on the center square (m = 5) it goes berserk and turns into a berserker. For this sequence, the berserker can move to three of the side squares and three of the corners from the center.
The berserker is one of the Lewis chessmen which were discovered in 1831 on the Isle of Lewis. They are carved from walrus ivory in Scandinavian style of the 12th century. The pawns look like decorated tombstones. The pieces have all human representations with facial expressions varying from gloom to anger. Some of the rooks show men biting their shield in the manner of berserkers. According to Hooper and Whyld none looks happy.
Let A be the adjacency matrix of the graph G, where V(G) = {v1, v2, v3, v4, v5, v6, v7, v8, v9}. Then the (m, k) entry of A^n is the number of different vm-vk walks of length n in G, see the Chartrand reference. In the adjacency matrix A, see the Maple program, the A[1], A[3], A[7] and A[9] vectors represent the rook moves on the corner squares, the A[2], A[4], A[6] and A[8] vectors represent the rook moves on the side squares and the A[5] vector represents the moves of the berserker. On a 3 X 3 chessboard there are 2^9 = 512 ways a berserker could move from the center square (off the center the berserker behaves like a rook) so there are 512 different berserkers.
For the side squares the 512 berserker vectors lead to 42 different sequences, see the overview of berserker sequences. There are 16 berserker vectors that lead to the sequence given above. Their decimal [binary] values are: 111 [001 101 111] , 207 [011 001 111], 231 [011 100 111], 237 [011 101 101], 303 [100 101 111], 363 [101 101 011], 366 [101 101 110], 399 [110 001 111], 423 [110 100 111], 429 [110 101 101], 459 [111 001 011], 462 [111 001 110], 483 [111 100 011], 486 [111 100 110], 489 [111 101 001] and 492 [111 101 100]. These berserker vectors lead for the corner squares to sequence 4*A179606 (with leading term 1 added) and for the central square to sequence 6*A179606 (with leading term 1 added).
This sequence belongs to a family of sequences with GF(x)=(1+x-k*x^2)/(1-3*x+(k-4)*x^2), see A180142.

Gary Chartrand, Introductory Graph Theory, pp. 217-221, 1984.
David Hooper and Kenneth Whyld, The Oxford Companion to Chess, pp. 131, 225, 1992.

Indranil Ghosh, Table of n, a(n) for n = 0..1603
Dougie MacLean, The Lewis Chessmen: "Marching Mystery"
Johannes W. Meijer, The berserker sequences.
Wikipedia, Lewis Chessmen
Index entries for linear recurrences with constant coefficients, signature (3,5)

Cf. A180141 (corner squares) and A180147 (central square).

Cf. Berserker sequences side squares: 4*A007482 (with leading 1 added), A180144, A003500 (n>=1 and a(0)=1), A180142, A000302, A180140 (this sequence), 2*A001077 (n>=1 and a(0)=1), A180146, 4*A154964 (n>=1 and a(0)=1), 4*A123347 (with leading 1 added).

nmax:=22; m:=2; A[1]:=[0, 1, 1, 1, 0, 0, 1, 0, 0]: A[2]:=[1, 0, 1, 0, 1, 0, 0, 1, 0]: A[3]:= [1, 1, 0, 0, 0, 1, 0, 0, 1]: A[4]:= [1, 0, 0, 0, 1, 1, 1, 0, 0]: A[5]:=[0, 0, 1, 1, 0, 1, 1, 1, 1]: A[6]:=[0, 0, 1, 1, 1, 0, 0, 0, 1]: A[7]:=[1, 0, 0, 1, 0, 0, 0, 1, 1]: A[8]:=[0, 1, 0, 0, 1, 0, 1, 0, 1]: A[9]:=[0, 0, 1, 0, 0, 1, 1, 1, 0]: A:= Matrix([A[1], A[2], A[3], A[4], A[5], A[6], A[7], A[8], A[9]]): for n from 0 to nmax do B(n):=A^n: a(n):= add(B(n)[m, k], k=1..9): od: seq(a(n), n=0..nmax);

CoefficientList[Series[(1+x+x^2)/(1-3*x-5*x^2), {x, 0, 22}],x] (* or *) LinearRecurrence[{3,5,0},{1,4,18},23] (* Indranil Ghosh, Mar 05 2017 *)

print(Vec((1 + x + x^2)/(1- 3*x - 5*x^2) + O(x^23))); \\ Indranil Ghosh, Mar 05 2017

G.f.: (1+x+x^2)/(1-3*x-5*x^2).
a(n) = 3*a(n-1) + 5*a(n-2) for n>=3  with a(0)=1, a(1)=4 and a(2)=18.
a(n) = ((22+54*A)*A^(-n-1) + (22+54*B)*B^(-n-1))/145  with A=(-3+sqrt(29))/10 and B=(-3-sqrt(29))/10 for n>=1 with a(0)=1.
5*a(n) = 2*( A015523(n) + 3*A015523(n+1)), n>0 - R. J. Mathar, May 11 2013

A180148 a(n) = 3*a(n-1) + a(n-2) with a(0)=2 and a(1)=5.

Original entry on oeis.org

2, 5, 17, 56, 185, 611, 2018, 6665, 22013, 72704, 240125, 793079, 2619362, 8651165, 28572857, 94369736, 311682065, 1029415931, 3399929858, 11229205505, 37087546373, 122491844624, 404563080245, 1336181085359, 4413106336322, 14575500094325, 48139606619297

Offset: 0

Johannes W. Meijer, Aug 13 2010

Inverse binomial transform of A052961 (without the leading 1).

For n >= 1, also the number of matchings in the n-alkane graph. - Eric W. Weisstein, Jul 14 2021

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Eric Weisstein's World of Mathematics, Alkane Graph
Eric Weisstein's World of Mathematics, Matching
Eric Weisstein's World of Mathematics, Maximum Independent Edge Set
Index entries for linear recurrences with constant coefficients, signature (3,1).

Cf. A003688, A052906.
Appears in A180142.
Cf. A000602 (more information on n-alkanes).

a:= n-> (<<0|1>, <1|3>>^n. <<2, 5>>)[1,1]:
seq(a(n), n=0..27);  # Alois P. Heinz, Jul 14 2021

LinearRecurrence[{3, 1}, {5, 7}, 20] (* Eric W. Weisstein, Jul 14 2021 *)
CoefficientList[Series[(2 - x)/(1 - 3 x - x^2), {x, 0, 20}], x] (* Eric W. Weisstein, Jul 14 2021 *)

a(n)=([0,1;1,3]^n*[2;5])[1,1] \\ Charles R Greathouse IV, Oct 13 2016

G.f.: (2-x)/(1-3*x-x^2).
a(n) = 3*a(n-1) + a(n-2) with a(0)=2 and a(1)=5.
a(n) = ((4+7*A)*A^(-n-1) + (4+7*B)*B^(-n-1))/13 with A = (-3+sqrt(13))/2 and B = (-3-sqrt(13))/2.
Lim_{k->infinity} a(n+k)/a(k) = (-1)^n*2/(A006497(n) - A006190(n)*sqrt(13)).
a(n) = 2 * Sum_{k=0..n-2} A168561(n-2,k)*3^k + 5 * Sum_{k=0..n-1} A168561(n-1,k)*3^k, n>0. - R. J. Mathar, Feb 14 2024
a(n) = 2*A006190(n+1) - A006190(n). - R. J. Mathar, Feb 14 2024

A123620 Expansion of (1 + x + x^2) / (1 - 3x - 3x^2).

Original entry on oeis.org

1, 4, 16, 60, 228, 864, 3276, 12420, 47088, 178524, 676836, 2566080, 9728748, 36884484, 139839696, 530172540, 2010036708, 7620627744, 28891993356, 109537863300, 415289569968, 1574482299804, 5969315609316, 22631393727360, 85802128010028, 325300565212164

Offset: 0

N. J. A. Sloane, Nov 20 2006

From Johannes W. Meijer, Aug 14 2010: (Start)
A berserker sequence, see A180141. For the corner squares 16 A[5] vectors with decimal values between 3 and 384 lead to this sequence. These vectors lead for the side squares to A180142 and for the central square to A155116.
This sequence belongs to a family of sequences with GF(x) = (1+x+k*x^2)/(1-3*x+(k-4)*x^2). Berserker sequences that are members of this family are 4*A055099(n) (k=2; with leading 1 added), A123620 (k=1; this sequence), A000302 (k=0), 4*A179606 (k=-1; with leading 1 added) and A180141 (k=-2). Some other members of this family are 4*A003688 (k=3; with leading 1 added), 4*A003946 (k=4; with leading 1 added), 4*A002878 (k=5; with leading 1 added) and 4*A033484 (k=6; with leading 1 added).
(End)
a(n) is the number of length n sequences on an alphabet of 4 letters that do not contain more than 2 consecutive equal letters. For example, a(3)=60 because we count all 4^3=64 words except: aaa, bbb, ccc, ddd. - Geoffrey Critzer, Mar 12 2014

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
A. Burstein and T. Mansour, Words restricted by 3-letter generalized multipermutation patterns, arXiv:math/0112281 [math.CO], 2001.
A. Burstein and T. Mansour, Words restricted by 3-letter generalized multipermutation patterns, Annals. Combin., 7 (2003), 1-14.
Martin Burtscher, Igor Szczyrba, Rafał Szczyrba, Analytic Representations of the n-anacci Constants and Generalizations Thereof, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.5.
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 205
Index entries for linear recurrences with constant coefficients, signature (3,3).

Column 4 in A265584.

[1] cat [Round(((2^(1-n)*(-(3-Sqrt(21))^(1+n) + (3+Sqrt(21))^(1+n))))/(3*Sqrt(21))): n in [1..50]]; // G. C. Greubel, Oct 26 2017

nn=25;CoefficientList[Series[(1-z^(m+1))/(1-r z +(r-1)z^(m+1))/.{r->4,m->2},{z,0,nn}],z] (* Geoffrey Critzer, Mar 12 2014 *)
CoefficientList[Series[(1 + x + x^2)/(1 - 3 x - 3 x^2), {x, 0, 40}], x] (* Vincenzo Librandi, Mar 14 2014 *)
LinearRecurrence[{3,3},{1,4,16},30] (* Harvey P. Dale, Jul 14 2023 *)

my(x='x+O('x^50)); Vec((1+x+x^2)/(1-3*x-3*x^2)) \\ G. C. Greubel, Oct 16 2017

a(0)=1, a(1)=4, a(2)=16, a(n)=3*a(n-1)+3*a(n-2) for n>2. - Philippe Deléham, Sep 18 2009

a(n) = ((2^(1-n)*(-(3-sqrt(21))^(1+n) + (3+sqrt(21))^(1+n)))) / (3*sqrt(21)) for n>0. - Colin Barker, Oct 17 2017

cp's OEIS Frontend

A155116 a(n) = 3*a(n-1) + 3*a(n-2), n>2, a(0)=1, a(1)=2, a(2)=8.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Sage

Formula

A180140 Eight rooks and one berserker on a 3 X 3 chessboard. G.f.: (1+x+x^2)/(1-3*x-5*x^2).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A180148 a(n) = 3*a(n-1) + a(n-2) with a(0)=2 and a(1)=5.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A123620 Expansion of (1 + x + x^2) / (1 - 3*x - 3*x^2).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

A155116 a(n) = 3a(n-1) + 3a(n-2), n>2, a(0)=1, a(1)=2, a(2)=8.

A180140 Eight rooks and one berserker on a 3 X 3 chessboard. G.f.: (1+x+x^2)/(1-3x-5x^2).

A123620 Expansion of (1 + x + x^2) / (1 - 3x - 3x^2).