A329118 -id:A329118 - cp's OEIS frontend

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

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

A140518 Number of simple paths from corner to corner of an n X n grid with king-moves allowed.

Original entry on oeis.org

1, 5, 235, 96371, 447544629, 22132498074021, 10621309947362277575, 50819542770311581606906543, 2460791237088492025876789478191411, 1207644919895971862319430895789323709778193, 5996262208084349429209429097224046573095272337986011

Offset: 1

Don Knuth, Jul 26 2008

This graph is the "strong product" of P_n with P_n, where P_n is a path of length n. Sequence A007764 is what we get when we restrict ourselves to rook moves of unit length.

Computed using ZDDs (ZDD = "reduced, order, zero-suppressed binary decision diagram").

			For example, when n=8 this is the number of ways to move a king from a1 to h8 without occupying any cell twice.

Donald E. Knuth, The Art of Computer Programming, Vol. 4, fascicle 1, section 7.1.4, p. 117, Addison-Wesley, 2009.

Jens Weise, Evolutionary Many-Objective Optimisation for Pathfinding Problems, Ph. D. Dissertation, Otto von Guercke Univ., Magdeburg (Germany, 2022), see p. 53.

Main diagonal of A329118.
Cf. A140519, A158651, A234622, A007764, A038496.
Cf. A220638 (Hosoya index).

a(9)-a(11) from Andrew Howroyd, Apr 07 2016

A350729 Array read by antidiagonals: T(m,n) is the number of (undirected) Hamiltonian paths in the m X n king graph.

Original entry on oeis.org

1, 1, 1, 1, 12, 1, 1, 48, 48, 1, 1, 208, 392, 208, 1, 1, 768, 4678, 4678, 768, 1, 1, 2752, 43676, 171592, 43676, 2752, 1, 1, 9472, 406396, 4743130, 4743130, 406396, 9472, 1, 1, 32000, 3568906, 132202038, 364618672, 132202038, 3568906, 32000, 1

Offset: 1

Andrew Howroyd, Jan 16 2022

			Array begins:
===========================================================
m\n | 1    2      3         4           5             6 ...
----+------------------------------------------------------
  1 | 1    1      1         1           1             1 ...
  2 | 1   12     48       208         768          2752 ...
  3 | 1   48    392      4678       43676        406396 ...
  4 | 1  208   4678    171592     4743130     132202038 ...
  5 | 1  768  43676   4743130   364618672   28808442502 ...
  6 | 1 2752 406396 132202038 28808442502 6544911081900 ...
     ...

Andrew Howroyd, Table of n, a(n) for n = 1..231
Eric Weisstein's World of Mathematics, Hamiltonian Path
Eric Weisstein's World of Mathematics, King Graph

Rows 1..5 are A000012, A339760, A339761, A339762, A339763.
Main diagonal is A308129.
Cf. A272445, A307026, A329118, A339098, A339190.

T(m,n) = T(n,m).

A193168 Number of simple paths from (1, 1) to (n, 3) on an n X 3 grid with king moves allowed.

Original entry on oeis.org

1, 24, 235, 2922, 38169, 494596, 6375379, 82191766, 1059980385, 13670322763, 176299392634, 2273637717194, 29321902354841, 378149186319554, 4876791443282017, 62893416210079645, 811103334429880838, 10460373436120693109, 134901938876902858230, 1739759409373842739031

Offset: 1

Matías Benzo, Jul 17 2011

Simple paths are self-avoiding walks.
Note: Number of paths from (1, 1) to (n, 2) on a n X 2 grid matches the sequence A086347.
Example: a(2) = 24 paths from (1, 1) to (2, 3)
[(1, 1), (2, 1), (1, 2), (1, 3), (2, 3)]
[(1, 1), (2, 2), (1, 3), (2, 3)]
[(1, 1), (2, 2), (2, 1), (1, 2), (2, 3)]
[(1, 1), (1, 2), (2, 1), (2, 2), (1, 3), (2, 3)]
[(1, 1), (2, 2), (2, 1), (1, 2), (1, 3), (2, 3)]
[(1, 1), (1, 2), (2, 2), (1, 3), (2, 3)]
[(1, 1), (1, 2), (1, 3), (2, 3)]
[(1, 1), (2, 2), (1, 3), (1, 2), (2, 3)]
[(1, 1), (2, 2), (2, 3)]
[(1, 1), (1, 2), (2, 3)]
[(1, 1), (2, 2), (1, 2), (1, 3), (2, 3)]
[(1, 1), (2, 1), (2, 2), (1, 3), (2, 3)]
[(1, 1), (2, 1), (2, 2), (1, 2), (2, 3)]
[(1, 1), (2, 1), (1, 2), (1, 3), (2, 2), (2, 3)]
[(1, 1), (1, 2), (2, 1), (2, 2), (2, 3)]
[(1, 1), (2, 1), (2, 2), (1, 3), (1, 2), (2, 3)]
[(1, 1), (2, 1), (1, 2), (2, 3)]
[(1, 1), (1, 2), (2, 2), (2, 3)]
[(1, 1), (1, 2), (1, 3), (2, 2), (2, 3)]
[(1, 1), (2, 1), (2, 2), (1, 2), (1, 3), (2, 3)]
[(1, 1), (2, 2), (1, 2), (2, 3)]
[(1, 1), (2, 1), (2, 2), (2, 3)]
[(1, 1), (2, 1), (1, 2), (2, 2), (2, 3)]
[(1, 1), (2, 1), (1, 2), (2, 2), (1, 3), (2, 3)]

Andrew Howroyd, Table of n, a(n) for n = 1..200

Row 3 of A329118.

Cf. A086347, A140518.

Conjectures from Andrew Howroyd, Nov 05 2019: (Start)
a(n) = 12*a(n-1) + 6*a(n-2) + 50*a(n-3) + 300*a(n-4) - 194*a(n-5) - 833*a(n-6) + 352*a(n-7) + 661*a(n-8) - 84*a(n-9) - 219*a(n-10) + 72*a(n-11) + 54*a(n-12) for n > 12.
G.f.: x*(1 + 12*x - 59*x^2 - 92*x^3 + 195*x^4 + 280*x^5 + 102*x^6 - 178*x^7 - 67*x^8 + 109*x^9 - 75*x^10 - 54*x^11)/((1 + x + 9*x^2 + 24*x^3 + 9*x^4)*(1 - 13*x - 2*x^2 + 45*x^3 - 24*x^4 - 22*x^5 + 9*x^6 + 8*x^7 - 6*x^8)).
(End)

Offset changed and more terms from Andrew Howroyd, Nov 05 2019

A351106 Triangle read by rows: T(m,n) is the number of simple paths for a Racetrack car (using Moore neighborhood) with initial velocity zero, going from one corner to the diagonally opposite corner on an m X n grid, 1 <= n <= m.

Original entry on oeis.org

1, 1, 3, 1, 6, 23, 2, 17, 118, 1470, 3, 47, 762, 23878, 914525, 5, 133, 5724, 420894, 40285572

Offset: 1

Pontus von Brömssen, Jan 31 2022

			Triangle begins:
  m\n| 1   2    3      4        5  6
  ---+------------------------------
  1  | 1
  2  | 1   3
  3  | 1   6   23
  4  | 2  17  118   1470
  5  | 3  47  762  23878   914525
  6  | 5 133 5724 420894 40285572  ?

Wikipedia, Racetrack

Cf. A291896 (column n=1), A329118, A351041, A351107 (main diagonal), A351108, A351110.

A193170 Number of simple paths from (1, 1) to (n, 4) on an n X 4 grid with king moves allowed.

Original entry on oeis.org

1, 116, 2922, 96371, 3764367, 150610151, 5898799685, 229260056150, 8913331166213, 346912968530666, 13505399293115778, 525732956071093698, 20464530153147155981, 796592566402543482684, 31007930721872464811580, 1207007982256603680132971, 46983727059243543906960086

Offset: 1

Matías Benzo, Jul 17 2011

Andrew Howroyd, Table of n, a(n) for n = 1..200

Row 4 of A329118.

Offset changed and terms a(7) and beyond from Andrew Howroyd, Nov 05 2019

A193171 Number of simple paths from (1, 1) to (n, 5) on an n X 5 grid with king moves allowed.

Original entry on oeis.org

1, 560, 38169, 3764367, 447544629, 56182569218, 6972159602221, 860282926307373, 106058594866721427, 13079879279632244767, 1613359976756293117691, 199005867656003390145969, 24546867122140625530760786, 3027781041159666215998006805, 373467431655380156034555333637

Offset: 1

Matías Benzo, Jul 17 2011

Andrew Howroyd, Table of n, a(n) for n = 1..200

Row 5 of A329118.

Offset changed and terms a(6) and beyond from Andrew Howroyd, Nov 05 2019

A193172 Number of simple paths from (1, 1) to (n, 6) on an n X 6 grid with king moves allowed.

Original entry on oeis.org

1, 2704, 494596, 150610151, 56182569218, 22132498074021, 8656506756327178, 3389938886108156202, 1331019952223152763862, 523382675043001210360214, 205904433904968682871489186, 81019053039706376245418011749, 31881826560222260172503676030065

Offset: 1

Matías Benzo, Jul 17 2011

Andrew Howroyd, Table of n, a(n) for n = 1..100

Row 6 of A329118.

Offset changed and terms a(5) and beyond from Andrew Howroyd, Nov 05 2019

cp's OEIS Frontend

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

A140518 Number of simple paths from corner to corner of an n X n grid with king-moves allowed.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions

A350729 Array read by antidiagonals: T(m,n) is the number of (undirected) Hamiltonian paths in the m X n king graph.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A193168 Number of simple paths from (1, 1) to (n, 3) on an n X 3 grid with king moves allowed.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A351106 Triangle read by rows: T(m,n) is the number of simple paths for a Racetrack car (using Moore neighborhood) with initial velocity zero, going from one corner to the diagonally opposite corner on an m X n grid, 1 <= n <= m.

Views

Author

Keywords

Examples

Links

Crossrefs

A193170 Number of simple paths from (1, 1) to (n, 4) on an n X 4 grid with king moves allowed.

Views

Author

Keywords

Links

Crossrefs

Extensions

A193171 Number of simple paths from (1, 1) to (n, 5) on an n X 5 grid with king moves allowed.

Views

Author

Keywords

Links

Crossrefs

Extensions

A193172 Number of simple paths from (1, 1) to (n, 6) on an n X 6 grid with king moves allowed.

Views

Author

Keywords

Links

Crossrefs

Extensions