A154964 -id:A154964 - cp's OEIS frontend

A126473 Number of strings over a 5 symbol alphabet with adjacent symbols differing by three or less.

1, 5, 23, 107, 497, 2309, 10727, 49835, 231521, 1075589, 4996919, 23214443, 107848529, 501037445, 2327695367, 10813893803, 50238661313, 233396326661, 1084301290583, 5037394142315, 23402480441009, 108722104190981, 505095858086951, 2346549744920747

Offset: 0

R. H. Hardin, Dec 27 2006

[Empirical] a(base,n) = a(base-1,n) + 7^(n-1) for base >= 3n-2; a(base,n) = a(base-1,n) + 7^(n-1)-2 when base = 3n-3.
From Johannes W. Meijer, Aug 01 2010: (Start)
The a(n) represent the number of n-move routes of a fairy chess piece starting in a given side square (m = 2, 4, 6 or 8) on a 3 X 3 chessboard. This fairy chess piece behaves like a king on the eight side and corner squares but on the central square the king goes crazy and turns into a red king, see A179596.
For the side squares the 512 red kings lead to 47 different red king sequences, see the cross-references for some examples.
The sequence above corresponds to four A[5] vectors with the decimal [binary] values 367 [1,0,1,1,0,1,1,1,1], 463 [1,1,1,0,0,1,1,1,1], 487 [1,1,1,1,0,0,1,1,1] and 493 [1,1,1,1,0,1,1,0,1]. These vectors lead for the corner squares to A179596 and for the central square to A179597.
This sequence belongs to a family of sequences with g.f. (1+x)/(1-4*x-k*x^2). Red king sequences that are members of this family are A003947 (k=0), A015448 (k=1), A123347 (k=2), A126473 (k=3; this sequence) and A086347 (k=4). Other members of this family are A000351 (k=5), A001834 (k=-1), A111567 (k=-2), A048473 (k=-3) and A053220 (k=-4)
Inverse binomial transform of A154244. (End)
Equals the INVERT transform of A055099: (1, 4, 14, 50, 178, ...). - Gary W. Adamson, Aug 14 2010
Number of one-sided n-step walks taking steps from {E, W, N, NE, NW}. - Shanzhen Gao, May 10 2011
For n>=1, a(n) equals the numbers of words of length n-1 on alphabet {0,1,2,3,4} containing no subwords 00 and 11. - Milan Janjic, Jan 31 2015

Shanzhen Gao and Keh-Hsun Chen, Tackling Sequences From Prudent Self-Avoiding Walks, FCS'14, The 2014 International Conference on Foundations of Computer Science.
S. Gao and H. Niederhausen, Sequences Arising From Prudent Self-Avoiding Walks, 2010.
Index entries for linear recurrences with constant coefficients, signature (4,3).

Cf. 5 symbol differing by two or less A126392, one or less A057960.
Cf. Red king sequences side squares [numerical value A[5]]: A086347 [495], A179598 [239], A126473 [367], A123347 [335], A179602 [95], A154964 [31], A015448 [327], A152187 [27], A003947 [325], A108981 [11], A007483 [2]. - Johannes W. Meijer, Aug 01 2010
Cf. A055099.

with(LinearAlgebra): nmax:=19; m:=2; A[5]:= [1,0,1,1,0,1,1,1,1]: A:=Matrix([[0,1,0,1,1,0,0,0,0],[1,0,1,1,1,1,0,0,0],[0,1,0,0,1,1,0,0,0],[1,1,0,0,1,0,1,1,0],A[5],[0,1,1,0,1,0,0,1,1],[0,0,0,1,1,0,0,1,0],[0,0,0,1,1,1,1,0,1],[0,0,0,0,1,1,0,1,0]]): 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); # Johannes W. Meijer, Aug 01 2010
# second Maple program:
a:= n-> (M-> M[1,2]+M[2,2])(<<0|1>, <3|4>>^n):
seq(a(n), n=0..24);  # Alois P. Heinz, Jun 28 2021

LinearRecurrence[{4, 3}, {1, 5}, 24] (* Jean-François Alcover, Dec 10 2024 *)

a(n)=([0,1; 3,4]^n*[1;5])[1,1] \\ Charles R Greathouse IV, May 10 2016

From Johannes W. Meijer, Aug 01 2010: (Start)
G.f.: (1+x)/(1-4*x-3*x^2).
a(n) = 4*a(n-1) + 3*a(n-2) with a(0) = 1 and a(1) = 5.
a(n) = ((1+3/sqrt(7))/2)*(A)^(-n) + ((1-3/sqrt(7))/2)*(B)^(-n) with A = (-2 + sqrt(7))/3 and B = (-2-sqrt(7))/3.
Lim_{k->oo} a(n+k)/a(k) = (-1)^(n+1)*A000244(n)/(A015530(n)*sqrt(7)-A108851(n))
(End)
a(n) = A015330(n)+A015330(n+1). - R. J. Mathar, May 09 2023

Edited by Johannes W. Meijer, Aug 10 2010

A179597 Eight white kings and one red king on a 3 X 3 chessboard. G.f.: (1 + 5x + 2x^2)/(1 - 2x - 11x^2 - 6*x^3).

Original entry on oeis.org

1, 7, 27, 137, 613, 2895, 13355, 62233, 288741, 1342175, 6233899, 28964169, 134554277, 625117807, 2904117675, 13491856889, 62679715045, 291194561919, 1352817130667, 6284852732713, 29197861274277, 135646005392399

Offset: 0

Johannes W. Meijer, Jul 28 2010, Aug 10 2010

The a(n) represent the number of n-move routes of a fairy chess piece starting in the central square (m = 5) on a 3 X 3 chessboard. This fairy chess piece behaves like a king on the eight side and corner squares but on the central square the king goes crazy and turns into a red king, see A179596.
For the central square the 512 red kings lead to 47 different red king sequences, see the cross-references for some examples.
The sequence above corresponds to four A[5] vectors with decimal [binary] values 367 [1,0,1,1,0,1,1,1,1], 463 [1,1,1,0,0,1,1,1,1], 487 [1,1,1,1,0,0,1,1,1] and 493 [1,1,1,1,0,1,1,0,1]. These vectors lead for the corner squares to A179596 and for the side squares to A126473.
This sequence belongs to a family of sequences with g.f. (1 + (k+2)*x + (2*k-4)*x^2)/(1 - 2*x - (k+8)*x^2 - (2*k)*x^3). Red king sequences that are members of this family are A179607 (k=0), A179605 (k=1), A179601 (k=2), A179597 (k=3; this sequence) and A086348 (k=4). Another member of this family is A179609 (k = -4).

Index entries for linear recurrences with constant coefficients, signature (2,11,6).

Red king sequences central square [numerical value A[5]]: A086348 [495], A179599 [239], A179597 [367], A179601 [335], A179603 [95], A154964 [31], A179605 [327], A179606 [27], A179611 [15], A179607 [325], A015521 [11], A007483 [2], A000012 [16], A000007 [0].

with(LinearAlgebra): nmax:=21; m:=5; A[1]:= [0,1,0,1,1,0,0,0,0]: A[2]:= [1,0,1,1,1,1,0,0,0]: A[3]:= [0,1,0,0,1,1,0,0,0]: A[4]:=[1,1,0,0,1,0,1,1,0]: A[5]:= [1,0,1,1,0,1,1,1,1]: A[6]:= [0,1,1,0,1,0,0,1,1]: A[7]:= [0,0,0,1,1,0,0,1,0]: A[8]:= [0,0,0,1,1,1,1,0,1]: A[9]:= [0,0,0,0,1,1,0,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);

LinearRecurrence[{2,11,6},{1,7,27},30] (* Harvey P. Dale, Mar 01 2015 *)

G.f.: (1 + 5*x + 2*x^2)/(1 - 2*x - 11*x^2 - 6*x^3).
a(n) = 2*a(n-1) + 11*a(n-2) + 6*a(n-3) with a(0) = 1, a(1) = 7 and a(2) = 27.
a(n) = 8*(-1/2)^(-n+1)/9 + ((7+11*sqrt(7))*A^(-n-1) + (7-11*sqrt(7))*B^(-n-1))/126 with A = (-2+sqrt(7))/3 and B = (-2-sqrt(7))/3.
Lim_{k->infinity} a(n+k)/a(k) = (-1)^(n+1)*(A000244(n)/(A015530(n)*sqrt(7) - A108851(n))).

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

A179606 Eight white kings and one red king on a 3 X 3 chessboard. G.f.: (1 + x)/(1 - 3x - 5x^2).

Original entry on oeis.org

1, 4, 17, 71, 298, 1249, 5237, 21956, 92053, 385939, 1618082, 6783941, 28442233, 119246404, 499950377, 2096083151, 8788001338, 36844419769, 154473265997, 647641896836, 2715292020493, 11384085545659, 47728716739442

Offset: 0

Johannes W. Meijer, Jul 28 2010

a(n) represents the number of n-move routes of a fairy chess piece starting in the central square (m = 5) on a 3 X 3 chessboard. This fairy chess piece behaves like a king on the eight side and corner squares but on the central square the king goes crazy and turns into a red king, see A179596.
The sequence above corresponds to 24 red king vectors, i.e., A[5] vectors, with decimal values 27, 30, 51, 54, 57, 60, 90, 114, 120, 147, 150, 153, 156, 177, 180, 210, 216, 240, 282, 306, 312, 402, 408 and 432. These vectors lead for the corner squares to A015523 and for the side squares to A152187.
This sequence belongs to a family of sequences with g.f. (1 + (k-4)*x)/(1 - 3*x - k*x^2). Red king sequences that are members of this family are A007483 (k= 2), A015521 (k=4), A179606 (k=5; this sequence), A154964 (k=6), A179603 (k=7) and A179599 (k=8). We observe that there is no red king sequence for k=3. Other members of this family are A006190 (k=1), A133494 (k=0) and A168616 (k=-2).
Inverse binomial transform of A052918.
The sequence b(n+1) = 6*a(n), n >= 0 with b(0)=1, is a berserker sequence, see A180147. The b(n) sequence corresponds to 16 A[5] vectors with decimal values between 111 and 492. These vectors lead for the corner squares to sequence c(n+1)=4*A179606(n), n >= 0 with c(0)=1, and for the side squares to A180140. - Johannes W. Meijer, Aug 14 2010
Equals the INVERT transform of A063782: (1, 3, 10, 32, 104, ...). Example: a(3) = 71 = (1, 1, 4, 7) dot (32, 10, 3, 1) = (32 + 10 + 12 + 17). - Gary W. Adamson, Aug 14 2010

Indranil Ghosh, Table of n, a(n) for n = 0..1603
Index entries for linear recurrences with constant coefficients, signature (3,5).

Cf. A179597 (central square).

Cf. A072263, A072264, A152187, A197189.

with(LinearAlgebra): nmax:=22; m:=5; A[1]:= [0,1,0,1,1,0,0,0,0]: A[2]:= [1,0,1,1,1,1,0,0,0]: A[3]:= [0,1,0,0,1,1,0,0,0]: A[4]:= [1,1,0,0,1,0,1,1,0]: A[5]:= [0,0,0,1,1,1,0,0,1]: A[6]:= [0,1,1,0,1,0,0,1,1]: A[7]:= [0,0,0,1,1,0,0,1,0]: A[8]:= [0,0,0,1,1,1,1,0,1]: A[9]:= [0,0,0,0,1,1,0,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)/(1-3*x-5*x^2), {x, 0, 22}],x] (* or *) LinearRecurrence[{3,5,0},{1,4},23] (* Indranil Ghosh, Mar 05 2017 *)

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

G.f.: (1+x)/(1 - 3*x - 5*x^2).
a(n) = A015523(n) + A015523(n+1).
a(n) = 3*a(n-1) + 5*a(n-2) with a(0) = 1 and a(1) = 4.
a(n) = ((29 + 7*sqrt(29))*A^(-n-1) + (29-7*sqrt(29))*B^(-n-1))/290 with A = (-3+sqrt(29))/10 and B = (-3-sqrt(29))/10
Limit_{k->oo} a(n+k)/a(k) = (-1)^(n+1)*A000351(n)*A130196(n)/(A015523(n)*sqrt(29) - A072263(n)) for n >= 1.

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

Original entry on oeis.org

1, 4, 16, 72, 312, 1368, 5976, 26136, 114264, 499608, 2184408, 9550872, 41759064, 182582424, 798301656, 3490399512, 15261008472, 66725422488, 291742318296, 1275579489816, 5577192379224, 24385054076568, 106618316505048

Offset: 0

Johannes W. Meijer, Aug 13 2010

The a(n) represent the number of n-move routes of a fairy chess piece starting in a given corner square (m = 1, 3, 7 or 9) on a 3 X 3 chessboard. This fairy chess piece behaves like a rook on the eight side and corner squares but on the central square the rook goes berserk and turns into a berserker, see A180140.
On a 3 X 3 chessboard there are 2^9 = 512 ways to go berserk on the central square (we assume here that a berserker might behave like a rook). The berserker is represented by the A[5] vector in the fifth row of the adjacency matrix A, see the Maple program. For the corner squares the 512 berserkers lead to 42 berserker sequences, see the cross-references for some examples.
The sequence above corresponds to just one A[5] vectors with decimal value 495. This vector leads for the side squares to 4*A154964 (for n >= 1 with a(0) = 1) and for the central square to 2*A180141 (for n >= 1 with a(0)=1).
This sequence belongs to a family of sequences with g.f. (1 + x + k*x^2)/(1 - 3*x + (k-4)*x^2), see A123620.

Index entries for linear recurrences with constant coefficients, signature (3, 6).

Cf. A180140 (side squares) and A180147 (central square).

Cf. Berserker sequences corner squares [numerical value A[5]]: 4*A055099 [0, with leading 1 added], A180143 [16], 4*A001353 [17, n>=1 and a(0)=1], A123620 [3], 2*A018916 [19, with leading 1 added], A000302 [15], 4*A179606 [111, with leading 1 added], A089979 [343], 4*A001076 [95, n>=1 and a(0)=1], A180145 [191], A180141 [495, this sequence], 4*A090017 [383, n>=1 and a(0)=1].

with(LinearAlgebra): nmax:=22; m:=1; A[5]:= [1,1,1,1,0,1,1,1,1]: A:= Matrix([[0,1,1,1,0,0,1,0,0], [1,0,1,0,1,0,0,1,0], [1,1,0,0,0,1,0,0,1], [1,0,0,0,1,1,1,0,0], A[5], [0,0,1,1,1,0,0,0,1], [1,0,0,1,0,0,0,1,1], [0,1,0,0,1,0,1,0,1], [0,0,1,0,0,1,1,1,0]]): 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);

LinearRecurrence[{3, 6}, {1, 4, 16}, 23] (* Jean-François Alcover, Jan 18 2025 *)

G.f.: (1 + x - 2*x^2)/(1 - 3*x - 6*x^2).
a(n) = 4*a(n-1) - 2*a(n-3) with a(0)=2, a(1)=8 and a(2)=31.
a(n) = 3*a(n-1) + 6*a(n-2) for n >= 3 with a(0)=1, a(1)=4 and a(2)=16.
a(n) = (6+2*A)*A^(-n-1)/33 + (6+2*B)*B^(-n-1)/33 with A=(-3-sqrt(33))/12 and B=(-3+sqrt(33))/12 for n >= 1 with a(0)=1.

A152187 a(n) = 3a(n-1) + 5a(n-2), with a(0)=1, a(1)=5.

Original entry on oeis.org

1, 5, 20, 85, 355, 1490, 6245, 26185, 109780, 460265, 1929695, 8090410, 33919705, 142211165, 596232020, 2499751885, 10480415755, 43940006690, 184222098845, 772366329985, 3238209484180, 13576460102465, 56920427728295

Offset: 0

Philippe Deléham, Nov 28 2008

Unsigned version of A152185.
From Johannes W. Meijer, Aug 01 2010: (Start)
The a(n) represent the number of n-move routes of a fairy chess piece starting in a given side square (m = 2, 4, 6 and 8) on a 3 X 3 chessboard. This fairy chess piece behaves like a king on the eight side and corner squares but on the central square the king goes crazy and turns into a red king, see A179596.
The sequence above corresponds to 24 red king vectors, i.e., A[5] vectors, with decimal values 27, 30, 51, 54, 57, 60, 90, 114, 120, 147, 150, 153, 156, 177, 180, 210, 216, 240, 282, 306, 312, 402, 408 and 432. These vectors lead for the corner squares to A015523 and for the central square to A179606.
This sequence belongs to a family of sequences with g.f. (1+2*x)/(1 - 3*x - k*x^2). Red king sequences that are members of this family are A007483 (k=2), A108981 (k=4), A152187 (k=5; this sequence), A154964 (k=6), A179602 (k=7) and A179598 (k=8). We observe that there is no red king sequence for k=3. Other members of this family are A036563 (k=-2), A054486 (k=-1), A084244 (k=0), A108300 (k=1) and A000351 (k=10).
Inverse binomial transform of A015449 (without the first leading 1).
(End)

Index entries for linear recurrences with constant coefficients, signature (3, 5).

Cf. A015523, A072263, A072264, A179606, A197189.

LinearRecurrence[{3,5},{1,5},40] (* Harvey P. Dale, May 03 2013 *)

G.f.: (1+2*x)/(1 - 3*x - 5*x^2).
Lim_{k->infinity} a(n+k)/a(k) = (A072263(n) + A015523(n)*sqrt(29))/2. - Johannes W. Meijer, Aug 01 2010
G.f.: G(0)*(1+2*x)/(2-3*x), where G(k) = 1 + 1/(1 - x*(29*k-9)/(x*(29*k+20) - 6/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, Jun 17 2013

A155112 Triangle T(n,k), 0<=k<=n, read by rows given by [0,2,-1/2,-1/2,0,0,0,0,0,0,0,0,...] DELTA [1,0,0,0,0,0,0,0,0,...] where DELTA is the operator defined in A084938.

Original entry on oeis.org

1, 0, 1, 0, 2, 1, 0, 3, 4, 1, 0, 5, 10, 6, 1, 0, 8, 22, 21, 8, 1, 0, 13, 45, 59, 36, 10, 1, 0, 21, 88, 147, 124, 55, 12, 1, 0, 34, 167, 339, 366, 225, 78, 14, 1, 0, 55, 310, 741, 976, 770, 370, 105, 16, 1, 0, 89, 566, 1557, 2422, 2337, 1443, 567, 136, 18, 1, 0, 144, 1020, 3174, 5696, 6505, 4920, 2485, 824, 171, 20, 1

Offset: 0

Philippe Deléham, Jan 20 2009

A Fibonacci convolution triangle; Riordan array (1, x*(1+x)/(1-x-x^2)).

			Triangle begins:
  1;
  0,  1;
  0,  2,  1;
  0,  3,  4,  1;
  0,  5, 10,  6,  1;
  0,  8, 22, 21,  8,  1;
  0, 13, 45, 59, 36, 10, 1;
  ...

Alois P. Heinz, Rows n = 0..140, flattened

Cf. A000007, A155020, A155116, A155117, A155119, A155127, A155130, A155132, A155144, A155157.
Cf. A000012, A155020, A154964, A154968, A154996, A154997, A154999, A155000, A155001, A155017.
Cf. A000045, A154929.
T(2n,n) gives A262910.
Cf. A291385.

T:= func< n,k | n eq 0 select 1 else (&+[ Binomial(n-j,j)*Binomial(n-j,k)*k/(n-j): j in [0..Floor(n/2)]]) >;
[T(n,k): k in [0..n], n in [0..12]]; // G. C. Greubel, Mar 26 2021

# Uses function PMatrix from A357368.
PMatrix(10, n -> combinat:-fibonacci(n+1)); # Peter Luschny, Oct 19 2022

T[n_, k_]:= If[n==0, 1, Sum[Binomial[n-j, j]*Binomial[n-j, k]*k/(n-j), {j, 0, Floor[n/2]}]];
Table[T[n, k], {n,0,12}, {k,0,n}]//Flatten (* G. C. Greubel, Mar 26 2021 *)

def T(n,k): return 1 if n==0 else sum( binomial(n-j,j)*binomial(n-j,k)*k/(n-j) for j in (0..n//2) )
flatten([[T(n,k) for k in [0..n]] for n in [0..12]]) # G. C. Greubel, Mar 26 2021

Recurrence: T(n+2,k+1) = T(n+1,k+1) + T(n+1,k) + T(n,k+1) + T(n,k).
Explicit formula: T(n,k) = Sum_{i=0..floor(n/2)} binomial(n-i, i)*binomial(n-i, k)*k/(n-i), for n > 0.
G.f.: (1-x-x^2)/(1-(1+y)*x-(1+y)*x^2). - Philippe Deléham, Feb 21 2012
Sum_{k=0..n} T(n,k)*x^(n-k) = A000012(n), A155020(n), A154964(n), A154968(n), A154996(n), A154997(n), A154999(n), A155000(n), A155001(n), A155017(n) for x = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, respectively.
Sum_{k=0..n} T(n,k)*x^k = A000007(n), A155020(n), A155116(n), A155117(n), A155119(n), A155127(n), A155130(n), A155132(n), A155144(n), A155157(n) for x = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, respectively. - Philippe Deléham, Feb 21 2012
Sum_{k=0..n} T(n, k)*(m-1)^k = (1/m)*[n=0] - (m-1)*(i*sqrt(m))^(n-2)*ChebyshevU(n, -i*sqrt(m)/2). - G. C. Greubel, Mar 26 2021
Sum_{k=0..n} k * T(n,k) = A291385(n-1) for n>=1. - Alois P. Heinz, Sep 29 2022

Typos in two terms corrected by Alois P. Heinz, Aug 08 2015

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

Original entry on oeis.org

1, 4, 14, 54, 204, 774, 2934, 11124, 42174, 159894, 606204, 2298294, 8713494, 33035364, 125246574, 474845814, 1800277164, 6825368934, 25876938294, 98106921684, 371951579934, 1410175504854, 5346381254364, 20269670277654, 76848154596054, 291353474621124

Offset: 0

Johannes W. Meijer, Aug 13 2010

The a(n) represent the number of n-move routes of a fairy chess piece starting in a given side square (m = 2, 4, 6 or 8) on a 3 X 3 chessboard. This fairy chess piece behaves like a rook on the eight side and corner squares but on the central square the rook goes berserk and turns into a berserker, see A180140.
The sequence above corresponds to 16 A[5] vectors with decimal values between 3 and 384. These vectors lead for the corner squares to A123620 and for the central square to A155116.
This sequence appears among the members of a family of sequences with g.f. (1 + x - k*x^2)/(1 - 3*x + (k-4)*x^2). Berserker sequences that are members of this family are 4*A007482 (k=2; with leading 1 added), A180142 (k=1; this sequence), A000302 (k=0), A180140 (k=-1) and 4*A154964 (k=-2; n>=1 and a(0)=1). Some other members of this family are 2*A180148 (k=3; with leading 1 added), 4*A025192 (k=4; with leading 1 added), 2*A005248 (k=5; with leading 1 added) and A123932 (k=6).

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (3,3).

Cf. A180141 (corner squares), A180140 (side squares), A180147 (central square).

with(LinearAlgebra): nmax:=23; m:=2; A[5]:=[0,0,0,0,0,0,0,1,1]: A:= Matrix([[0,1,1,1,0,0,1,0,0], [1,0,1,0,1,0,0,1,0], [1,1,0,0,0,1,0,0,1], [1,0,0,0,1,1,1,0,0], A[5], [0,0,1,1,1,0,0,0,1], [1,0,0,1,0,0,0,1,1], [0,1,0,0,1,0,1,0,1], [0,0,1,0,0,1,1,1,0]]): 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);
# second Maple program:
a:= n-> ceil((<<0|1>, <3|3>>^n. <<2/3, 4>>)[1,1]):
seq(a(n), n=0..25);  # Alois P. Heinz, Jul 14 2021

LinearRecurrence[{3, 3}, {1, 4, 14}, 26] (* Jean-François Alcover, Jan 18 2025 *)

G.f.: (1 + x - x^2)/(1 - 3*x - 3*x^2).
a(n) = 3*a(n-1) + 3*a(n-2) for n >= 2 with a(0)=1, a(1)=4 and a(2)=14.
a(n) = (6-2*A)*A^(-n-1)/21 + (6-2*B)*B^(-n-1)/21 with A=(-3+sqrt(21))/6 and B=(-3-sqrt(21))/6.
Lim_{k->infinity} a(2*n+k)/a(k) = 2*A000244(n)/(A003501(n) - A004254(n)*sqrt(21)) for n >= 1.
Lim_{k->infinity} a(2*n-1+k)/a(k) = 2*A000244(n)/(A004253(n)*sqrt(21) - 3*A030221(n-1)) for n >= 1.

A375436 Expansion of g.f. A(x) satisfying A(x) = (1 + 2xA(x)) * (1 + 3xA(x)^2).

Original entry on oeis.org

1, 5, 46, 533, 6922, 96338, 1404796, 21184229, 327659314, 5169425894, 82866843652, 1345864066658, 22098946620580, 366245357320196, 6118363978530424, 102921394554326021, 1741855452305095618, 29637960953559091934, 506708801920060974388, 8700147627314354759030, 149957787462657877848556

Offset: 0

Paul D. Hanna, Sep 07 2024

nonn

In general, if G(x) = (1 + p*x*G(x)) * (1 + q*x*G(x)^2) for fixed p and q, then
(C.1) G(x) = exp( Sum_{n>=1} x^n/n * Sum_{k=0..n} C(n,k)^2 * p^(n-k) * q^k * G(x)^k ).
(C.2) G(x) = (1/x) * Series_Reversion( x/(1 + p*x) - q*x^2 ).
(C.3) x = (sqrt((p - q*y)^2 + 4*p*q*y^2) - (p + q*y))/(2*p*q*y^2), where y = G(x).

			G.f. A(x) = 1 + 5*x + 46*x^2 + 533*x^3 + 6922*x^4 + 96338*x^5 + 1404796*x^6 + 21184229*x^7 + 327659314*x^8 + 5169425894*x^9 + 82866843652*x^10 + ...
where A(x) = (1 + 2*x*A(x)) * (1 + 3*x*A(x)^2).
RELATED SERIES.
Let B(x) = A(x/B(x)) and B(x*A(x)) = A(x), then
B(x) = 1 + 5*x + 21*x^2 + 93*x^3 + 405*x^4 + 1773*x^5 + 7749*x^6 + 33885*x^7 + ... + A154964(n+1)*x^n + ...
where B(x) = (1 + 2*x)/(1 - 3*x - 6*x^2).

Paul D. Hanna, Table of n, a(n) for n = 0..400

Cf. A154964, A216314, A215661, A375434, A375435, A375437.

{a(n) = my(A=1+x); for(i=1, n, A=(1 + 2*x*A)*(1 + 3*x*(A+x*O(x^n))^2)); polcoef(A, n)}
for(n=0, 20, print1(a(n), ", "))

{a(n)=polcoef( (1/x)*serreverse( x*(1 - 3*x - 6*x^2)/(1 + 2*x +x*O(x^n))), n)}
for(n=0, 20, print1(a(n), ", "))

{a(n) = my(A=1+x+x*O(x^n)); for(i=1, n, A=exp(sum(m=1, n, sum(j=0, m, binomial(m, j)^2 * 2^(m-j) * 3^j * A^j)*x^m/m))); polcoef(A, n)}
for(n=0, 20, print1(a(n), ", "))

G.f. A(x) = Sum{n>=0} a(n)*x^n satisfies the following formulas.
(1) A(x) = (1 + 2*x*A(x)) * (1 + 3*x*A(x)^2).
(2) A(x) = exp( Sum_{n>=1} x^n/n * Sum_{k=0..n} C(n,k)^2 * 2^(n-k) * 3^k * A(x)^k ).
(3) A(x) = (1/x) * Series_Reversion( x*(1 - 3*x - 6*x^2)/(1 + 2*x) ).
(4) A(x) = Sum_{n>=0} A154964(n+1) * x^n * A(x)^n, where g.f. of A154964 = (1 - 2*x - 4*x^2)/(1 - 3*x - 6*x^2).
(5) x = (sqrt(33*A(x)^2 - 12*A(x) + 4) - (2 + 3*A(x)))/(12*A(x)^2).
a(n) = Sum_{k=0..n} 3^k * 2^(n-k) * binomial(n+k+1,k) * binomial(n+k+1,n-k) / (n+k+1). - Seiichi Manyama, Sep 08 2024

A174673 Triangle read by rows: T(n,m)=A154694(n,m)-A154694(n,0)+1.

Original entry on oeis.org

1, 1, 1, 1, 36, 1, 1, 296, 296, 1, 1, 1932, 4656, 1932, 1, 1, 11696, 54086, 54086, 11696, 1, 1, 69048, 556596, 1042920, 556596, 69048, 1, 1, 405236, 5406866, 16866206, 16866206, 5406866, 405236, 1, 1, 2381700, 51004320, 247754256, 404837664

Offset: 0

Roger L. Bagula, Mar 26 2010

Reduces the values in the triangle A154694 such that each row starts with 1.
Row sums are:
1, 2, 38, 594, 8522, 131566, 2294210, 45356618, 1007118218, 24839902470,
673894929842,...

			{1},
{1, 1},
{1, 36, 1},
{1, 296, 296, 1},
{1, 1932, 4656, 1932, 1},
{1, 11696, 54086, 54086, 11696, 1},
{1, 69048, 556596, 1042920, 556596, 69048, 1},
{1, 405236, 5406866, 16866206, 16866206, 5406866, 405236, 1},
{1, 2381700, 51004320, 247754256, 404837664, 247754256, 51004320, 2381700, 1},
{1, 14050376, 473595806, 3441231326, 8491073726, 8491073726, 3441231326, 473595806, 14050376, 1},
{1, 83216400, 4357421004, 46167420504, 164067684600, 244543444824, 164067684600, 46167420504, 4357421004, 83216400, 1}

A154690, A154692, A154693, A154964

A174673 := proc(n,m)
    A154694(n,m)-A154694(n,0)+1 ;
end proc:
seq(seq( A174673(n,m),m=0..n),n=0..10) ; # R. J. Mathar, Mar 11 2024

Clear[t, p, q, n, m];
p = 2; q = 3;
t[n_, m_] = (p^(n - m)*q^m + p^m*q^( n - m))*Sum[(-1)^j*Binomial[n + 2, j]*(m - j + 1)^(n + 1), {j, 0, m + 1}];
Table[Table[t[n, m] - t[n, 0] + 1, {m, 0, n}], {n, 0, 10}];
Flatten[%]

t(n,m)=A154694(n,m)-A154694(n,0)+1

cp's OEIS Frontend

A126473 Number of strings over a 5 symbol alphabet with adjacent symbols differing by three or less.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A179597 Eight white kings and one red king on a 3 X 3 chessboard. G.f.: (1 + 5*x + 2*x^2)/(1 - 2*x - 11*x^2 - 6*x^3).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

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

A179606 Eight white kings and one red king on a 3 X 3 chessboard. G.f.: (1 + x)/(1 - 3*x - 5*x^2).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A152187 a(n) = 3*a(n-1) + 5*a(n-2), with a(0)=1, a(1)=5.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A155112 Triangle T(n,k), 0<=k<=n, read by rows given by [0,2,-1/2,-1/2,0,0,0,0,0,0,0,0,...] DELTA [1,0,0,0,0,0,0,0,0,...] where DELTA is the operator defined in A084938.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

A179597 Eight white kings and one red king on a 3 X 3 chessboard. G.f.: (1 + 5x + 2x^2)/(1 - 2x - 11x^2 - 6*x^3).

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

A179606 Eight white kings and one red king on a 3 X 3 chessboard. G.f.: (1 + x)/(1 - 3x - 5x^2).

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

A152187 a(n) = 3a(n-1) + 5a(n-2), with a(0)=1, a(1)=5.

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

A375436 Expansion of g.f. A(x) satisfying A(x) = (1 + 2xA(x)) * (1 + 3xA(x)^2).