A086346 -id:A086346 - cp's OEIS frontend

A057087 Scaled Chebyshev U-polynomials evaluated at i. Generalized Fibonacci sequence.

1, 4, 20, 96, 464, 2240, 10816, 52224, 252160, 1217536, 5878784, 28385280, 137056256, 661766144, 3195289600, 15428222976, 74494050304, 359689093120, 1736732573696, 8385686667264, 40489676963840, 195501454524416

Offset: 0

Wolfdieter Lang, Aug 11 2000

a(n) gives the length of the word obtained after n steps with the substitution rule 0->1111, 1->11110, starting from 0. The number of 1's and 0's of this word is 4*a(n-1) and 4*a(n-2), respectively.
Inverse binomial transform of odd Pell bisection A001653. With a leading zero, inverse binomial transform of even Pell bisection A001542, divided by 2. - Paul Barry, May 16 2003
For positive n, a(n) equals the permanent of the n X n tridiagonal matrix with 4's along the main diagonal, and 2's along the superdiagonal and the subdiagonal. - John M. Campbell, Jul 19 2011
Pisano period lengths: 1, 1, 8, 1, 3, 8, 6, 1, 24, 3, 120, 8, 21, 6, 24, 1, 16, 24, 360, 3, ... . - R. J. Mathar, Aug 10 2012
Exponential convolution of Pell numbers (A000129) and companion Pell numbers (A002203), divided by 2 and leading zero dropped. - Vladimir Reshetnikov, Oct 07 2016

Indranil Ghosh, Table of n, a(n) for n = 0..1459
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.
A. F. Horadam, Special properties of the sequence W_n(a,b; p,q), Fib. Quart., 5.5 (1967), 424-434. Case n->n+1, a=0,b=1; p=4, q=4.
Tanya Khovanova, Recursive Sequences.
Wolfdieter Lang, On polynomials related to powers of the generating function of Catalan's numbers, Fib. Quart. 38 (2000) 408-419; Eqs.(39) and (45),rhs, m=4.
Index entries for sequences related to Chebyshev polynomials.
Index entries for linear recurrences with constant coefficients, signature (4,4)

Pairwise sums are in A086347.

Appears in A086346, A086347 and A086348. - Johannes W. Meijer, Aug 01 2010

I:=[1,4]; [n le 2 select I[n] else 4*Self(n-1) + 4*Self(n-2): n in [1..30]]; // G. C. Greubel, Jan 16 2018

A057087 := n -> `if`(n=0, 1, 4^n*hypergeom([1/2-n/2, -n/2], [-n], -1)):
seq(simplify(A057087(n)), n=0..21); # Peter Luschny, Dec 17 2015

Table[Fibonacci[n + 1, 2] 2^n, {n, 0, 20}] (* Vladimir Reshetnikov, Oct 08 2016 *)
LinearRecurrence[{4,4},{1,4},30] (* Harvey P. Dale, Aug 17 2017 *)

a(n)=if(n<0, 0, (2*I)^n*subst(I*poltchebi(n+1)+poltchebi(n),'x,-I)/2) /* Michael Somos, Sep 16 2005 */

Vec(1/(1-4*x-4*x^2) + O(x^100)) \\ Altug Alkan, Dec 17 2015

[lucas_number1(n,4,-4) for n in range(1, 23)] # Zerinvary Lajos, Apr 23 2009

a(n) = 4*(a(n-1) + a(n-2)), a(-1)=0, a(0)=1.
G.f.: 1/(1 - 4*x - 4*x^2).
a(n) = S(n, 2*i)*(-2*i)^n with S(n, x) := U(n, x/2), Chebyshev's polynomials of the 2nd kind, A049310.
a(n) = Sum_{k=0..n} 3^k*A063967(n,k). - Philippe Deléham, Nov 03 2006
a(n) = A000129(n+1)*A000079(n). - R. J. Mathar, Jul 08 2009
From Johannes W. Meijer, Aug 01 2010: (Start)
Limit_{k->oo} a(n+k)/a(k) = A084128(n) + 2*A057087(n-1)*sqrt(2);
Limit_{n->oo} A084128(n)/A057087(n-1) = sqrt(2). (End)
a(n) = 4^n*hypergeom([1/2-n/2, -n/2], [-n], -1) for n>=1. - Peter Luschny, Dec 17 2015

A079291 Squares of Pell numbers.

Original entry on oeis.org

0, 1, 4, 25, 144, 841, 4900, 28561, 166464, 970225, 5654884, 32959081, 192099600, 1119638521, 6525731524, 38034750625, 221682772224, 1292061882721, 7530688524100, 43892069261881, 255821727047184, 1491038293021225

Offset: 0

Ralf Stephan, Feb 08 2003

(-1)^(n+1)*a(n) is the r=-4 member of the r-" of sequences S_r(n), n>=1, defined in A092184 where more information can be found.
Binomial transform of A086346. - Johannes W. Meijer, Aug 01 2010
In general, squaring the terms of a Horadam sequence with signature (c,d) will result in a third-order recurrence with signature (c^2+d, c^2*d+d^2, -d^3). - Gary Detlefs, Nov 11 2021
(Conjectured) For any primitive Pythagorean triple of the form (X, Y, Z=Y+1), it appears that Y or Z will always be (and only be) a square Pell number if X = A001333(n), for n > 1. If n is even, Y is always a square Pell number, and if n is odd, then Z is always a square Pell number. For example: (3, 4, 5), (7, 24, 25), (17, 144, 145), (41, 840, 841), (99, 4900, 4901). - Jules Beauchamp, Feb 02 2022
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, black half-squares (1/2 X 1 pieces, always placed so that the shorter sides are horizontal), and white 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 black (1/4,1/4)-fences, white (1/4,1/4)-fences, and (1/4,3/4)-fences. - Michael A. Allen, Dec 29 2022

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Michael A. Allen and Kenneth Edwards, Fence tiling derived identities involving the metallonacci numbers squared or cubed, Fib. Q. 60:5 (2022) 5-17.
Joerg Arndt, Matters Computational (The Fxtbook), sect. 32.1.5, pp. 626-627
Sergio Falcon, Some series of reciprocal k-Fibonacci numbers, Asian Journal of Mathematics and Computer Research, Vol. 11, No. 3 (2016), pp. 184-191; ResearchGate link.
Toufik Mansour, A note on sum of k-th power of Horadam's sequence, arXiv:math/0302015 [math.CO], 2003.
Toufik Mansour, Squaring the terms of an ell-th order linear recurrence, arXiv:math/0303138 [math.CO], 2003.
Pantelimon Stanica, Generating functions, weighted and non-weighted sums for powers of second-order recurrence sequences, arXiv:math/0010149 [math.CO], 2000.
Index entries for linear recurrences with constant coefficients, signature (5,5,-1).
Index entries for sequences related to Chebyshev polynomials.

Cf. A000129, A001254, A001109, A001541, A001653, A174968.

Cf. A002203, A007598, A084158 (partial sums), A086346, A092184.

I:=[0,1,4]; [n le 3 select I[n] else 5*Self(n-1)+ 5*Self(n-2) - Self(n-3): n in [1..31]]; // Vincenzo Librandi, May 17 2013

with(combinat):seq(fibonacci(i,2)^2, i=0..31); # Zerinvary Lajos, Mar 20 2008

CoefficientList[Series[x(1-x)/((1+x)*(1-6x+x^2)), {x, 0, 30}], x] (* Vincenzo Librandi, May 17 2013 *)
LinearRecurrence[{5,5,-1},{0,1,4},40] (* Harvey P. Dale, Dec 20 2015 *)
Fibonacci[Range[0, 30], 2]^2 (* G. C. Greubel, Sep 17 2021 *)

[lucas_number1(n, 2, -1)^2 for n in (0..30)] # G. C. Greubel, Sep 17 2021

G.f.: x*(1-x)/((1+x)*(1-6*x+x^2)).
a(n) = (r^n + (1/r)^n - 2*(-1)^n)/8, with r = 3 + sqrt(8).
a(n+3) = 5*a(n+2) + 5*a(n+1) - a(n).
L.g.f.: (1/8)*log((1+2*x+x^2)/(1-6*x+x^2)) = Sum_{n>=0} (a(n)/n)*x^n, see p. 627 of the Fxtbook link; special case of the following: let v(0)=0, v(1)=1, and v(n) = u*v(n-1) + v(n-2), then (1/A)*log((1+2*x+x^2)/(1-(2-A)*x+x^2)) = Sum_{n>=0} v(n)^2/n*x^n where A = u^2 + 4. - Joerg Arndt, Apr 08 2011
a(n+1) = Sum_{k=0..n} ( (-1)^(n-k)*A001653(k) ); e.g., 144 = -1 + 5 - 29 + 169; 25 = 1 - 5 + 29. - Charlie Marion, Jul 16 2003
a(n) = A000129(n)^2.
a(n) = (T(n, 3) - (-1)^n)/4 with Chebyshev's polynomials of the first kind evaluated at x=3: T(n, 3) = A001541(n) = ((3 + 2*sqrt(2))^n + (3 - 2*sqrt(2))^n )/2. - Wolfdieter Lang, Oct 18 2004
a(n) is the rightmost term of M^n * [1 0 0] where M is the 3 X 3 matrix [4 4 1 / 2 1 0 / 1 0 0]. a(n+1) = leftmost term. E.g., a(6) = 4900, a(5) = 841 since M^5 * [1 0 0] = [4900 2030 841]. - Gary W. Adamson, Oct 31 2004
a(n) = ( (-1)^(n+1) + A001109(n+1) - 3*A001109(n) )/4. - R. J. Mathar, Nov 16 2007
a(n) = ( (((1 - sqrt(2))^n + (1 + sqrt(2))^n) /2 )^2 + (-1)^(n+1) )/2. - Antonio Pane (apane1(AT)spc.edu), Dec 15 2007
Lim_{k -> infinity} ( a(n+k)/a(k) ) = A001541(n) + 2*A001109(n)*sqrt(2). - Johannes W. Meijer, Aug 01 2010
For n>0, a(2*n) = 6*a(2*n-1) - a(2*n-2) - 2, a(2*n+1) = 6*a(2*n) - a(2*n-1) + 2. - Charlie Marion, Sep 24 2011
a(n) = (1/8)*(A002203(2*n) - 2*(-1)^n). - G. C. Greubel, Sep 17 2021
Conjectured formula for (X, Y, Z) for primitive Pythagorean triple of the form (X, Y, Z=Y+1) is (A001333(n)^2, A079291(n)^2, A079291(n)^2-1) or (A001333(n)^2, A079291(n)^2-1, A079291(n)^2). As a closed formula (X, Y, Z) = (((1-sqrt(2))^n + (1+sqrt(2))^n)/2, (((1-sqrt(2))^n + (1+sqrt(2))^n)^2 - 4)/8, (((1-sqrt(2))^n + (1+sqrt(2))^n)^2 + 4)/8). - Jules Beauchamp, Feb 02 2022
From Michael A. Allen, Dec 29 2022: (Start)
a(n+1) = 6*a(n) - a(n-1) + 2*(-1)^n.
a(n+1) = (1 + (-1)^n)/2 + 4*Sum_{k=1..n} ( k*a(n+1-k) ). (End)
Product_{n>=2} (1 + (-1)^n/a(n)) = (1 + sqrt(2))/2 (A174968) (Falcon, 2016, p. 189, eq. (3.1)). - Amiram Eldar, Dec 03 2024

A086347 On a 3 X 3 board, number of n-move routes of chess king ending in a given side square.

Original entry on oeis.org

1, 5, 24, 116, 560, 2704, 13056, 63040, 304384, 1469696, 7096320, 34264064, 165441536, 798822400, 3857055744, 18623512576, 89922273280, 434183143424, 2096421666816, 10122419240960, 48875363631104, 235991131488256, 1139465980477440, 5501828447862784

Offset: 0

Zak Seidov, Jul 17 2003

Number of aa-avoiding words of length n on alphabet {a,b,c,d,e}. - Tanya Khovanova, Jan 11 2007
Binomial transform of A164589 and second binomial transform of A096886. [Al Hakanson (hawkuu(AT)gmail.com), Aug 17 2009]
From Johannes W. Meijer, Aug 01 2010: (Start)
The a(n) represent the number of n-move paths of a chess king on a 3 X 3 board that end or start in a given side square m (m = 2, 4, 6, 8).
Inverse binomial transform of A001109 (without the leading 0).
(End)
Number of independent vertex subsets of the graph obtained by attaching two pendant edges to each vertex of the path graph P_n (see A235116). Example: a(1)=5; indeed, P_1 is the one-vertex graph and after attaching two pendant vertices we obtain the path graph ABC; the independent vertex subsets are: empty, {A}, {B}, {C}, and {A,C}.
Number of simple paths from corner to diagonally opposite corner on a 2 X n grid with king moves allowed. - Andrew Howroyd, Nov 06 2019
Number of 4-compositions of n+1 restricted to parts 1 and 2 (and allowed zeros); see Hopkins & Ouvry reference. - Brian Hopkins, Aug 16 2020

			a(3) = 116 = 5^3 - 9 (aaa, aab, aac, aad, aae, baa, caa, daa, eaa). [Al Hakanson (hawkuu(AT)gmail.com), Aug 17 2009]

Indranil Ghosh, Table of n, a(n) for n = 0..1459
Jean-Paul Allouche, Jeffrey Shallit, and Manon Stipulanti, Combinatorics on words and generating Dirichlet series of automatic sequences, arXiv:2401.13524 [math.CO], 2025. See p. 14.
Joerg Arndt, Matters Computational (The Fxtbook)
D. Birmajer, J. B. Gil, and M. D. Weiner, On the Enumeration of Restricted Words over a Finite Alphabet, J. Int. Seq. 19 (2016) # 16.1.3, Example 7.
Martin Burtscher, Igor Szczyrba, and Rafał Szczyrba, Analytic Representations of the n-anacci Constants and Generalizations Thereof, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.5.
Brian Hopkins and Stéphane Ouvry, Combinatorics of Multicompositions, arXiv:2008.04937 [math.CO], 2020.
Milan Janjic, On Linear Recurrence Equations Arising from Compositions of Positive Integers, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.7.
Tanya Khovanova, Recursive Sequences
Mike Oakes, KingMovesForPrimes.
Zak Seidov, KingMovesForPrimes.
Zak Seidov et al., New puzzle? King moves for primes, digest of 28 messages in primenumbers group, Jul 13 - Jul 23, 2003. [Cached copy]
Sleephound, KingMovesForPrimes.
Index entries for linear recurrences with constant coefficients, signature (4,4).

Row 2 of A329118.
Row sums of A235113.
Cf. A086346, A086348.
Cf. A028859.
Cf. A126473. - Johannes W. Meijer, Aug 01 2010

with(LinearAlgebra): nmax:=19; m:=2; A[5]:= [1,1,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-> (<<0|1>, <4|4>>^n. <<1, 5>>)[1,1]:
seq(a(n), n=0..30);  # Alois P. Heinz, Oct 12 2022

Table[(Sqrt[2]/32)((2+Sqrt[8])^(n+2)-(2-Sqrt[8])^(n+2)), {n, 0, 19}]

a(n) = (sqrt(2)/32)*((2+sqrt(8))^(n+2)-(2-sqrt(8))^(n+2)).
From Ralf Stephan, Feb 01 2004: (Start)
G.f.: (1+x)/(1-4*x-4*x^2).
a(n) = A057087(n) + A057087(n-1). (End)
a(n) = 4*a(n-1) + 4*a(n-2). - Tanya Khovanova, Jan 11 2007
Limit_{k->oo} a(n+k)/a(k) = A084128(n) + 2*A057087(n-1)*sqrt(2). - Johannes W. Meijer, Aug 01 2010
E.g.f.: exp(2*x)*(4*cosh(2*sqrt(2)*x) + 3*sqrt(2)*sinh(2*sqrt(2)*x))/4. - Stefano Spezia, Mar 17 2025

Offset changed and edited by Johannes W. Meijer, Jul 15 2010

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

Original entry on oeis.org

1, 3, 17, 73, 351, 1607, 7513, 34809, 161903, 751783, 3493353, 16227737, 75393055, 350251335, 1627192697, 7559508409, 35119644495, 163157037671, 757987215241, 3521419711833, 16359641017343, 76002822156295, 353090213774361

Offset: 0

Johannes W. Meijer, Jul 28 2010; edited Jun 21 2013

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 king on the eight side and corner squares but on the center square the king goes crazy and turns into a red king.
On a 3 X 3 chessboard there are 2^9 = 512 ways to go crazy on the center square (off the center the piece behaves like a normal king). The red king is represented by the A[5] vector in the fifth row of the adjacency matrix A, see the Maple program and A180140. For the corner squares the 512 red kings lead to 47 different red king sequences, see the overview of the red king sequences.
The sequence above corresponds to four A[5] vectors with decimal [binary] values 367 [101 101 111], 463 [111 001 111], 487 [111 100 111] and 493 [111 101 101]. These vectors lead for the side squares to A126473 and for the central square to A179597.
This sequence belongs to a family of sequences with g.f. (1+x)/(1 - 2*x - (k+8)*x^2 - 2*k*x^3). Red king sequences that are members of this family are A083424 (k=0), A179604 (k=1), A179600 (k=2), A179596 (k=3; this sequence) and A086346 (k=4). Other members of this family are A015528 (k=5) and A179608 (k=-4).

Gary Chartrand, Introductory Graph Theory, pp. 217-221, 1984.

Vincenzo Librandi, Table of n, a(n) for n = 0..100
Charles Krauthammer, Did Chess Make Him Crazy?, Time, April 26, 2005.
Johannes W. Meijer, The red king sequences.
Index entries for linear recurrences with constant coefficients, signature (2,11,6).

Cf. A180140 (berserker sequences).

Cf. Red king sequences corner squares [decimal value A[5]]: A086346 [495], A015525 [239], A179596 [367], A179600 [335], A015524 [95], A083858 [31], A179604 [327], A015523 [27], A179610 [85], A083424 [325], A015521 [11], A007482 [2], A014335 [16].

nmax:=22; m:=1; 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,3,17},30] (* Harvey P. Dale, May 18 2011 *)

Vec((1+x)/(1-2*x-11*x^2-6*x^3)+O(x^99)) \\ Charles R Greathouse IV, Jul 16 2011

G.f.: (1+x)/(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)=3 and a(2)=17.
a(n) = (-1)^(-n)*2^(n+1)/9 + ((49+17*sqrt(7))*A^(-n) + (49-17*sqrt(7))*B^(-n))/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)).

A084128 a(n) = 4a(n-1) + 4a(n-2), a(0)=1, a(1)=2.

Original entry on oeis.org

1, 2, 12, 56, 272, 1312, 6336, 30592, 147712, 713216, 3443712, 16627712, 80285696, 387653632, 1871757312, 9037643776, 43637604352, 210700992512, 1017354387456, 4912221519872, 23718303629312, 114522100596736, 552961616904192, 2669934870003712

Offset: 0

Paul Barry, May 16 2003

Original name was: Generalized Fibonacci sequence.

Binomial transform of A084058.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Martin Burtscher, Igor Szczyrba, and Rafał Szczyrba, Analytic Representations of the n-anacci Constants and Generalizations Thereof, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.5.
Tanya Khovanova, Recursive Sequences
Index entries for linear recurrences with constant coefficients, signature (4,4).

Cf. A001333 A001541, A002203, A057087, A084058, A084128, A201730.

Appears in A086346, A086347 and A086348. - Johannes W. Meijer, Aug 01 2010

[2^(n-1)*Evaluate(DicksonFirst(n,-1), 2): n in [0..40]]; // G. C. Greubel, Oct 13 2022

a:=proc(n) option remember; if n=0 then 1 elif n=1 then 2 else
4*a(n-1)+4*a(n-2); fi; end: seq(a(n), n=0..40); # Wesley Ivan Hurt, Jan 31 2017
a := n -> (2*I)^n*ChebyshevT(n, -I):
seq(simplify(a(n)), n = 0..23); # Peter Luschny, Dec 03 2023

CoefficientList[Series[(2 z - 1)/(4 z^2 + 4 z - 1), {z, 0, 100}], z] (* Vladimir Joseph Stephan Orlovsky, Jul 01 2011 *)
Table[2^(n-1) LucasL[n, 2], {n, 0, 20}] (* Vladimir Reshetnikov, Oct 07 2016 *)
LinearRecurrence[{4,4},{1,2},30] (* Harvey P. Dale, Mar 01 2018 *)

a(n)=if(n<0,0,polsym(4+4*x-x^2,n)[n+1]/2)

[lucas_number2(n,4,-4)/2 for n in range(0, 23)] # Zerinvary Lajos, May 14 2009

a(n) = 2^n * A001333(n).
G.f.: (1-2*x)/(1-4*x-4*x^2).
a(n) = 4*a(n-1) + 4*a(n-2), a(0)=1, a(1)=2.
a(n) = (2 + 2*sqrt(2))^n/2 + (2 - 2*sqrt(2))^n/2.
E.g.f.: exp(2*x)*cosh(2*x*sqrt(2)).
From Johannes W. Meijer, Aug 01 2010: (Start)
Lim_{k->infinity} a(n+k)/a(k) = A084128(n) + 2*A057087(n-1)*sqrt(2).
Lim_{n->infinity} A084128(n)/A057087(n-1) = sqrt(2). (End)
a(n) = Sum_{k=0..n} A201730(n,k)*7^k. - Philippe Deléham, Dec 06 2011
G.f.: G(0)/2, where G(k)= 1 + 1/(1 - x*(4*k-2)/(x*(4*k+2) - 1/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 27 2013
a(n) = 2^(n-1)*A002203(n). - Vladimir Reshetnikov, Oct 07 2016

A086348 On a 3 X 3 board, number of n-move routes of chess king ending in the central square.

Original entry on oeis.org

1, 8, 32, 168, 784, 3840, 18432, 89216, 430336, 2078720, 10035200, 48457728, 233967616, 1129709568, 5454692352, 26337640448, 127169265664, 614027755520, 2964787822592, 14315262836736

Offset: 0

Zak Seidov, Jul 17 2003

From Johannes W. Meijer, Aug 01 2010: (Start)
The a(n) represent the number of n-move paths of a chess king on a 3 X 3 board that end or start in the central square m (m = 5).
Inverse binomial transform of A090390 (without the first leading 1).
(End)
From R. J. Mathar, Oct 12 2010: (Start)
The row n=3 of an array T(n,k) counting king walks on an n X n board starting on a square on the diagonal next to a corner:
1,8,32,168,784,3840,18432,89216,430336,2078720,10035200,48457728,233967616,
1,8,47,275,1610,9425,55175,323000,1890875,11069375,64801250,379353125,
1,8,47,318,2013,13140,84555,547722,3537081,22874400,147831399,955690326,
1,8,47,318,2134,14539,99267,679189,4650100,31848677,218164072,1494530576,
1,8,47,318,2134,14880,103920,733712,5187856,36796224,261164848,1855327584,
1,8,47,318,2134,14880,104885,748845,5382180,38880243,281743740,2045995632,
1,8,47,318,2134,14880,104885,751590,5430735,39556080,289541500,2127935700,
1,8,47,318,2134,14880,104885,751590,5438580,39710495,291852880,2156410817,
1,8,47,318,2134,14880,104885,751590,5438580,39733008,292340803,2164218694,
1,8,47,318,2134,14880,104885,751590,5438580,39733008,292405638,2165752797, (End)

Mike Oakes, KingMovesForPrimes.
Zak Seidov, KingMovesForPrimes.
Zak Seidov et al., New puzzle? King moves for primes, digest of 28 messages in primenumbers group, Jul 13 - Jul 23, 2003. [Cached copy]
Sleephound, KingMovesForPrimes.
Index entries for linear recurrences with constant coefficients, signature (2, 12, 8).

Cf. A086346, A086347.

Cf. A179597.

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

Table[(1/16)(4(-2)^(n+1)+(2+Sqrt[8])^(n+2)+(2-Sqrt[8])^(n+2)), {n, 0, 19}]

a(n) = (1/16)(4(-2)^(n+1) + (2+sqrt(8))^(n+2) + (2-sqrt(8))^(n+2)).
From Johannes W. Meijer, Aug 01 2010: (Start)
G.f.: ( 1+6*x+4*x^2 ) / ( (2*x+1)*(-4*x^2-4*x+1) ).
a(n) = 2*a(n-1) + 12*a(n-2) + 8*a(n-3) with a(0)=1, a(1)=8 and a(2)=32.
Lim_{k->infinity} a(n+k)/a(k) = A084128(n) + 2*A057087(n-1)*sqrt(2). (End)
2*a(n) = 3*A057087(n) + 2*A057087(n-1) - (-2)^n. - R. J. Mathar, May 21 2019

Offset changed and edited by Johannes W. Meijer, Jul 15 2010

A110048 Expansion of 1/((1+2x)(1-4x-4x^2)).

Original entry on oeis.org

1, 2, 16, 64, 336, 1568, 7680, 36864, 178432, 860672, 4157440, 20070400, 96915456, 467935232, 2259419136, 10909384704, 52675280896, 254338531328, 1228055511040, 5929575645184, 28630525673472, 138240403177472

Offset: 0

Creighton Dement, Jul 10 2005

Floretion Algebra Multiplication Program, FAMP Code:
-kbasejseq[A*B] with A = + 'i - .5'j + .5'k - .5j' + .5k' - 'ii' - .5'ij' - .5'ik' - .5'ji' - .5'ki' and B = - .5'i + .5'j + 'k - .5i' + .5j' - 'kk' - .5'ik' - .5'jk' - .5'ki' - .5'kj'
See also comment for A110047.

G. C. Greubel, Table of n, a(n) for n = 0..1000
Robert Munafo, Sequences Related to Floretions
Index entries for linear recurrences with constant coefficients, signature (2,12,8).

Cf. A079291, A084159, A086346, A086348, A110046, A110047, A110049, A110050.

[2^(n-2)*(Evaluate(DicksonFirst(n+1,-1), 2) +2*(-1)^n): n in [0..40]]; // G. C. Greubel, Aug 18 2022

seriestolist(series(1/((1+2*x)*(1-4*x-4*x^2)), x=0,40));

CoefficientList[Series[1/((1+2x)(1-4x-4x^2)), {x,0,40}], x] (* or *) LinearRecurrence[{2,12,8}, {1,2,16}, 41] (* Harvey P. Dale, Nov 02 2011 *)

[2^(n-2)*(lucas_number2(n+1,2,-1) +2*(-1)^n) for n in (0..40)] # G. C. Greubel, Aug 18 2022

Superseeker finds: a(n+1) = 2*A086348(n+1) (A086348's offset is 1: On a 3 X 3 board, number of n-move routes of chess king ending at central cell); binomial transform matches A084159 (Pell oblongs); j-th coefficient of g.f.*(1+x)^j matches A079291 (Squares of Pell numbers); a(n) + a(n+1) = A086346(n+2) (A086346's offset is 1: On a 3 X 3 board, the number of n-move paths for a chess king ending in a given corner cell.)
From Maksym Voznyy (voznyy(AT)mail.ru), Jul 24 2008: (Start)
a(n) = 2*a(n-1) + 12*a(n-2) + 8*a(n-3), where a(1)=1, a(2)=2, a(3)=16.
a(n) = 2^(n-3)*( 4*(-1)^(1-n) + (sqrt(2)-1)^(-n) + (-sqrt(2)-1)^(-n)) . (End)
a(n) = 2^n*A097076(n+1). - R. J. Mathar, Mar 08 2021

A123109 a(0) = 1, a(1) = 3, a(n) = 3*a(n-1) + 3 for n > 1.

Original entry on oeis.org

1, 3, 12, 39, 120, 363, 1092, 3279, 9840, 29523, 88572, 265719, 797160, 2391483, 7174452, 21523359, 64570080, 193710243, 581130732, 1743392199, 5230176600, 15690529803, 47071589412, 141214768239, 423644304720, 1270932914163

Offset: 0

Philippe Deléham, Sep 28 2006

From R. J. Mathar, Oct 12 2010: (Start)
The top row, n=2, of an array that counts chess king walks with k >= 0 steps on an n X n board, starting at one of the four corners:
1,3,12, 39,120, 363, 1092, 3279, 9840, 29523, 88572, 265719, 797160,
1,3,21,101,501,2405,11653, 56197, 271493, 1310597, 6328709, 30556549,
1,3,21,126,741,4341,25416,148791, 871041, 5099166,29851041,174751041,
1,3,21,126,810,5169,33447,215796,1395588, 9018255,58302057,376845978,
1,3,21,126,810,5360,36167,246034,1680313,11495503,78705226,539048956,
1,3,21,126,810,5360,36700,254756,1788468,12617828,89338116,633604564,
1,3,21,126,810,5360,36700,256255,1816090,12993280,93566653,676648735,
1,3,21,126,810,5360,36700,256255,1820335,13080120,94845670,692120270,
1,3,21,126,810,5360,36700,256255,1820335,13092211,95117374,696421066,
1,3,21,126,810,5360,36700,256255,1820335,13092211,95151979,697268152,
1,3,21,126,810,5360,36700,256255,1820335,13092211,95151979,697367593,
These are partial sums along rows of the array described in A086346. (End)

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Madeleine Goertz and Aaron Williams, The Quaternary Gray Code and How It Can Be Used to Solve Ziggurat and Other Ziggu Puzzles, arXiv:2411.19291 [math.CO], 2024. See p. 17.
Index entries for linear recurrences with constant coefficients, signature (4,-3).

a:=[1,3,12];; for n in [4..30] do a[n]:=4*a[n-1]-3*a[n-2]; od; a; # G. C. Greubel, May 24 2019

I:=[1, 3, 12]; [n le 3 select I[n] else 4*Self(n-1)-3*Self(n-2): n in [1..30]]; // Vincenzo Librandi, Jun 27 2012

LinearRecurrence[{4,-3}, {1,3,12}, 30] (* Georg Fischer, May 24 2019 *)
Join[{1},NestList[3#+3&,3,30]] (* Harvey P. Dale, Aug 16 2020 *)

my(x='x+O('x^30)); Vec((1-x+3*x^2)/(1-4*x+3*x^2)) \\ G. C. Greubel, May 24 2019

((1-x+3*x^2)/(1-4*x+3*x^2)).series(x, 30).coefficients(x, sparse=False) # G. C. Greubel, May 24 2019

a(0) = 1 and a(n) = 3*A003462(n) for n > 0.
G.f.: (1-x+3*x^2)/(1-4*x+3*x^2). [Corrected by Georg Fischer, May 24 2019]
a(n) = Sum_{k=0..n} 3^k*A123110(n,k). - Philippe Deléham, Feb 09 2007
a(n) = A029858(n+1), n > 0. - R. J. Mathar, Jun 18 2008
a(n+1) - a(n) = 3^n, n >= 2. - R. J. Mathar, Aug 18 2011
E.g.f.: 1 + 3*(exp(3*x) - exp(x))/2. - G. C. Greubel, May 24 2019

A086349 On a 3 X 3 board, the number of n-move paths for a chess king.

Original entry on oeis.org

1, 9, 40, 200, 952, 4624, 22272, 107648, 519552, 2509056, 12113920, 58492928, 282425344, 1363677184, 6584401920, 31792332800, 153506906112, 741197021184, 3578815578112, 17280050659328, 83435464425472

Offset: 0

Zak Seidov, Jul 17 2003

			a(1)=9 because there are 9 cells in the 3 X 3 board;
a(2)=40 because from each of 4 corner cells, king can move to 3 cells, this gives 4*3=12 moves, from each of 4 side cells, king can move to 5 cells, this gives 4*5=20 moves and from the central cell, king can move to 8 cells, this gives 8 moves and the total is 12+20+8=40.

Mike Oakes, KingMovesForPrimes.
Zak Seidov, KingMovesForPrimes.
Zak Seidov et al., New puzzle? King moves for primes, digest of 28 messages in primenumbers group, Jul 13 - Jul 23, 2003. [Cached copy]
Sleephound, KingMovesForPrimes.

Cf. A086346, A086347, A086348.

a(n) = 4*A086346(n) + 4*A086347(n) + A086349(n).

a(n) = 2*a(n-1)+12*a(n-2)+8*a(n-3) for n>3. G.f.: (1+x)*(1+6*x+4*x^2)/((1+2*x)*(1-4*x-4*x^2)). - Colin Barker, Apr 12 2012

Edited by Johannes W. Meijer, Jul 15 2010

A355127 a(n) is the number of different (n-1)-move routes for a king on an empty n X n chessboard.

Original entry on oeis.org

1, 12, 200, 2880, 37680, 455224, 5186888, 56471040, 593296160, 6057160296, 60407414256, 590807590672, 5684125083000, 53924502344880, 505415790232592, 4687367714152128, 43070861665247616, 392532002390446600, 3551337773634149120, 31920035670120464496

Offset: 1

Frank Hollstein, Jun 20 2022

			n = 2:
.
Numeration of squares on board:
  0 1
  2 3
.
By symmetry, the number of routes from each of the 4 starting squares is the same.
.
3 routes starting at square 0:
  01 02 03
.
Total number of routes: 4*3 = 12.
---------------------------------
n = 3:
Numeration of squares on board:
  0 1 2
  3 4 5
  6 7 8
.
Using symmetry, only the numbers of routes starting from one of the 4 corner squares (e.g., square 0), one of the 4 side squares (e.g., square 1), and the 1 center square (square 4) need to be considered.
.
18 routes starting at square 0:
  010 012 015 014 013
  040 041 042 043 045 046 047 048
  030 031 034 036 037
.
24 routes starting at square 1:
  101 103 104
  121 124 125
  131 130 134 136 137
  141 140 142 143 145 146 147 148
  151 152 154 157 158
.
32 routes starting at square 4:
  404 401 403
  414 410 412 413 415
  424 421 425
  434 430 431 436 437
  454 451 452 457 458
  464 463 467
  474 473 475 476 478
  484 485 487
.
Total number of routes: 4*18 + 4*24 + 1*32 = 72 + 96 + 32 = 200.

Alois P. Heinz, Table of n, a(n) for n = 1..1101

Cf. A086346, A086347, A151331, A323562.

b:= proc(n, m, x, y) option remember; `if`(n=0, 1, add(
      add((s-> `if`({i, j}={0} or min(s)<1 or max(s)>m, 0,
        b(n-1, m, s[])))([x+i, y+j]), j=-1..1), i=-1..1))
    end:
a:= n-> add(add(b(n-1, n, x, y), x=1..n), y=1..n):
seq(a(n), n=1..20);  # Alois P. Heinz, Jun 20 2022

b[n_, m_, x_, y_] := b[n, m, x, y] = If[n == 0, 1, Sum[Sum[With[{s = {x + i, y + j}}, If[Union@{i, j} == {0} || Min[s] < 1 || Max[s] > m, 0, b[n - 1, m, Sequence @@ s]]], {j, -1, 1}], {i, -1, 1}]];
a[n_] := Sum[Sum[b[n - 1, n, x, y], {x, 1, n}], {y, 1, n}];
Table[a[n], {n, 1, 20}] (* Jean-François Alcover, Sep 10 2022, after Alois P. Heinz *)

From Vaclav Kotesovec, Jul 18 2022: (Start)
Recurrence: (n-4) * (n-2) * (n-1)^2 * (6561*n^8 - 212139*n^7 + 2950263*n^6 - 23053977*n^5 + 110718549*n^4 - 334617561*n^3 + 621301485*n^2 - 647573195*n + 289741950)*a(n) = (n-2) * (98415*n^11 - 3621672*n^10 + 58904658*n^9 - 557565930*n^8 + 3401022330*n^7 - 13968918180*n^6 + 39146085342*n^5 - 74076664722*n^4 + 91284487995*n^3 - 67946473736*n^2 + 26218206060*n-3608592880)*a(n-1) - 2 * (951345*n^11 - 35042301*n^10 + 573945345*n^9 - 5517149841*n^8 + 34570186911*n^7 - 148143645873*n^6 + 442497763659*n^5 - 919659425931*n^4 + 1300075875920*n^3 - 1186236344006*n^2 + 625358201108*n-143083453680)*a(n-2) - 8 * (n-3) * (538002*n^11 - 20170701*n^10 + 335662947*n^9 - 3269686095*n^8 + 20693992482*n^7 - 89239225257*n^6 + 267100420161*n^5 - 553559634623*n^4 + 775814257936*n^3 - 696718449512*n^2 + 358050585284*n-78798884240)*a(n-3) + 64 * (n-4) * (39366*n^11 - 747954*n^10 + 1036638*n^9 + 95287104*n^8 - 1244227635*n^7 + 8077634280*n^6 - 32356061235*n^5 + 84721205046*n^4 - 145611420210*n^3 + 158260316980*n^2 - 98341752748*n + 26435972680)*a(n-4) + 512 * (n-5) * (n-3) * (118098*n^10 - 3864429*n^9 + 55834110*n^8 - 468708363*n^7 + 2528957700*n^6 - 9150957666*n^5 + 22446838206*n^4 - 36764880492*n^3 + 38348031900*n^2 - 22886883656*n + 5886448960)*a(n-5) + 8192 * (n-6) * (n-5) * (n-4) * (n-3) * (6561*n^8 - 159651*n^7 + 1648998*n^6 - 9439902*n^5 + 32737014*n^4 - 70335324*n^3 + 91203060*n^2 - 64949504*n + 19261936)*a(n-6).
a(n) ~ n^2 * 8^(n-1) * (1 - 2*sqrt(6/(Pi*n))). (End)

a(11)-a(20) from Alois P. Heinz, Jun 20 2022

cp's OEIS Frontend

A057087 Scaled Chebyshev U-polynomials evaluated at i. Generalized Fibonacci sequence.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

Sage

Formula

A079291 Squares of Pell numbers.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Sage

Formula

A086347 On a 3 X 3 board, number of n-move routes of chess king ending in a given side square.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A084128 a(n) = 4*a(n-1) + 4*a(n-2), a(0)=1, a(1)=2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Sage

Formula

A086348 On a 3 X 3 board, number of n-move routes of chess king ending in the central square.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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

A084128 a(n) = 4a(n-1) + 4a(n-2), a(0)=1, a(1)=2.

A110048 Expansion of 1/((1+2x)(1-4x-4x^2)).