A186864 -id:A186864 - cp's OEIS frontend

A186861 Array read by antidiagonals: T(n,k) is the number of n-step king's tours on a k X k board summed over all starting positions.

1, 4, 0, 9, 12, 0, 16, 40, 24, 0, 25, 84, 160, 24, 0, 36, 144, 408, 496, 0, 0, 49, 220, 768, 1764, 1208, 0, 0, 64, 312, 1240, 3768, 6712, 2240, 0, 0, 81, 420, 1824, 6508, 17280, 22672, 2984, 0, 0, 100, 544, 2520, 9984, 32520, 74072, 68272, 2384, 0, 0, 121, 684

Offset: 1

R. H. Hardin, Feb 27 2011

			Table starts:
  1  4    9     16       25       36        49       64       81      100
  0 12   40     84      144      220       312      420      544      684
  0 24  160    408      768     1240      1824     2520     3328     4248
  0 24  496   1764     3768     6508      9984    14196    19144    24828
  0  0 1208   6712    17280    32520     52432    77016   106272   140200
  0  0 2240  22672    74072   156484    268048   408764   578632   777652
  0  0 2984  68272   296360   722384   1335984  2129440  3102752  4255920
  0  0 2384 183472  1110000  3193800   6481216 10899404 16418600 23038804
  0  0  784 436984  3908376 13530576  30543072 54738536 85743256
  0  0    0 905776 12956800 55056168 139775784
Some n=3 solutions for 3 X 3:
  3 2 0   0 0 0   0 3 0   0 0 0   0 0 0   0 0 1   0 1 0
  1 0 0   1 0 0   0 2 0   1 2 0   2 3 0   0 2 0   2 0 0
  0 0 0   2 3 0   0 0 1   3 0 0   0 1 0   0 0 3   0 3 0

R. H. Hardin, Table of n, a(n) for n = 1..145

Rows are A000290, A033586(n-1), A186862, A186863, A186864, A186865, A186866, A186867, A366829.

Empirical, for all rows: a(n) = 3*a(n-1) - 3*a(n-2) + a(n-3) for n > 3,3,3,5,6,7,8,9 respectively for row=1..8.

A186863 Number of 4-step king's tours on an n X n board summed over all starting positions.

Original entry on oeis.org

0, 24, 496, 1764, 3768, 6508, 9984, 14196, 19144, 24828, 31248, 38404, 46296, 54924, 64288, 74388, 85224, 96796, 109104, 122148, 135928, 150444, 165696, 181684, 198408, 215868, 234064, 252996, 272664, 293068, 314208, 336084, 358696, 382044, 406128, 430948, 456504, 482796, 509824

Offset: 1

R. H. Hardin, Feb 27 2011

From J. Volkmar Schmidt, Oct 25 2023 (Start)
Proof of formula for a(n) follows proof scheme from David A. Corneth for A186864.
Distribution matrix of surrounding rectangles for 4-step walks is:
  [0  0  0  2]
  [0 24 80 28]
  [0 80 80 20]
  [2 28 20  4] (End)

			Some solutions for 3 X 3:
  0 3 0   0 2 0   0 0 1   1 0 0   0 0 0   0 4 3   4 0 0
  0 2 4   0 3 1   0 0 2   4 2 0   0 1 4   0 2 1   1 3 0
  0 1 0   0 0 4   4 3 0   3 0 0   0 3 2   0 0 0   2 0 0

J. Volkmar Schmidt, Table of n, a(n) for n = 1..50
Index entries for linear recurrences with constant coefficients, signature (3, -3, 1).

Row 4 of A186861.

a(n) = 368*n^2 - 1308*n + 1108 = 4*(92*(n-1)*(n-3) + 41*n + 1) for n > 2.

G.f.: 4*x^2*(6 + 106*x + 87*x^2 - 15*x^3)/(1-x)^3. - Colin Barker, Jan 22 2012

a(34)-a(39) from J. Volkmar Schmidt, Sep 03 2023

A186867 Number of 8-step king's tours on an n X n board summed over all starting positions.

Original entry on oeis.org

0, 0, 2384, 183472, 1110000, 3193800, 6481216, 10899404, 16418600, 23038804, 30760016, 39582236, 49505464, 60529700, 72654944, 85881196, 100208456, 115636724, 132166000, 149796284, 168527576, 188359876, 209293184, 231327500, 254462824, 278699156

Offset: 1

R. H. Hardin, Feb 27 2011

nonn

From J. Volkmar Schmidt, Oct 24 2023 (Start)
Proof of a(n) follows proof scheme from David A. Corneth for A186864.
Distribution matrix of surrounding rectangles for 8-step walks is:
  [0    0     0     0     0     0     0    2]
  [0    0     0   416  3264  4224  2304  508]
  [0    0  2384 26004 38120 26164 10080 1764]
  [0  416 26004 67424 53320 26480  8460 1328]
  [0 3264 38120 53320 32032 13428  3816  560]
  [0 4224 26164 26480 13428  4952  1260  172]
  [0 2304 10080  8460  3816  1260   288   36]
  [2  508  1764  1328   560   172    36    4]
(End)

			Some solutions for 4 X 4:
  0 7 6 0    2 1 0 8    0 0 1 0    0 0 6 8    3 4 5 0
  8 0 5 1    4 3 7 0    0 0 3 2    0 0 7 5    2 0 6 0
  0 4 3 2    0 5 6 0    0 7 5 4    2 1 4 0    1 0 7 8
  0 0 0 0    0 0 0 0    0 8 6 0    0 3 0 0    0 0 0 0

Andrew Howroyd, Table of n, a(n) for n = 1..1000
Index entries for linear recurrences with constant coefficients, signature (3, -3, 1).

Row 8 of A186861.

Empirical: a(n) = 550504*n^2 - 3839372*n + 6382124 for n > 6.

a(12)-a(26) from J. Volkmar Schmidt, Aug 27 2023

A186865 Number of 6-step king's tours on an n X n board summed over all starting positions.

Original entry on oeis.org

0, 0, 2240, 22672, 74072, 156484, 268048, 408764, 578632, 777652, 1005824, 1263148, 1549624, 1865252, 2210032, 2583964, 2987048, 3419284, 3880672, 4371212, 4890904, 5439748, 6017744, 6624892, 7261192, 7926644, 8621248, 9345004, 10097912, 10879972, 11691184

Offset: 1

R. H. Hardin, Feb 27 2011

nonn

From J. Volkmar Schmidt, Oct 18 2023: (Start)
Proof of a(n) = 14576*n^2 - 77924*n + 99292 for n>4 follows proof scheme from David A. Corneth for A186864.
Distribution matrix of surrounding rectangles for 6-step walks is:
  [0   0    0    0    0   2]
  [0   0   96  576  448 124]
  [0  96 1856 2272 1064 224]
  [0 576 2272 1552  560 104]
  [0 448 1064  560  168  28]
  [2 124  224  104   28   4]
(End)

			Some solutions for 3X3
..0..2..0....0..4..0....0..4..3....0..0..0....0..2..1....3..2..0....0..4..5
..1..3..4....2..3..5....6..5..2....1..2..6....0..4..3....4..0..1....3..0..6
..6..5..0....1..6..0....0..0..1....3..4..5....0..5..6....6..5..0....1..2..0

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

Row 6 of A186861.

Empirical: a(n) = 14576*n^2 - 77924*n + 99292 for n>4.

A186866 Number of 7-step king's tours on an n X n board summed over all starting positions.

Original entry on oeis.org

0, 0, 2984, 68272, 296360, 722384, 1335984, 2129440, 3102752, 4255920, 5588944, 7101824, 8794560, 10667152, 12719600, 14951904, 17364064, 19956080, 22727952, 25679680, 28811264, 32122704, 35614000, 39285152, 43136160, 47167024

Offset: 1

R. H. Hardin, Feb 27 2011

nonn

From J. Volkmar Schmidt, Oct 24 2023 (Start)
Proof of a(n) follows proof scheme from David A. Corneth for A186864.
Distribution matrix of surrounding rectangles for 7-step walks is:
 [0    0    0     0    0    0   2]
 [0    0    0   800 1600 1024 252]
 [0    0 2984  9780 7904 3360 644]
 [0  800 9780 12416 6636 2272 388]
 [0 1600 7904  6636 2912  864 136]
 [0 1024 3360  2272  864  224  32]
 [2  252  644   388  136   32   4]
(End)

			Some solutions for 3X3
..0..2..1....0..2..0....6..0..0....1..7..6....1..2..3....7..2..1....6..5..0
..4..3..0....3..7..1....7..5..2....2..0..5....0..4..7....3..6..0....7..4..1
..5..6..7....4..5..6....4..3..1....3..4..0....0..6..5....5..4..0....0..2..3

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

Row 7 of A186861.

Empirical: a(n) = 89928*n^2 - 555464*n + 817760 for n>5.

A366829 Number of 9-step self-avoiding king's tours on an n X n board summed over all starting positions.

Original entry on oeis.org

0, 0, 784, 436984, 3908376, 13530576, 30543072, 54738536, 85743256, 123447704, 167851880, 218955784, 276759416, 341262776, 412465864, 490368680, 574971224, 666273496, 764275496, 868977224, 980378680, 1098479864, 1223280776, 1354781416, 1492981784, 1637881880

Offset: 1

J. Volkmar Schmidt, Oct 25 2023

Proof of the formula follows proof scheme from David A. Corneth for A186864.
Distribution matrix of surrounding rectangles for 9-step walks is:
  [0     0      0      0      0      0     0     0    2]
  [0     0      0      0   3584  10496 10752  5120 1020]
  [0     0    784  43856 129100 136320 83208 29160 4680]
  [0     0  43856 258424 318816 215096 99984 29680 4296]
  [0  3584 129100 318816 262816 142888 57376 15400 2100]
  [0 10496 136320 215096 142888  67688 24288  5960  768]
  [0 10752  83208  99984  57376  24288  7864  1760  212]
  [0  5120  29160  29680  15400   5960  1760   360   40]
  [2  1020   4680   4296   2100    768   212    40    4]

			Some solutions for 3 X 3:
  1 2 3  1 2 3  1 2 3  1 2 3  1 7 8  1 2 8
  4 5 6  6 5 4  8 9 4  7 6 4  6 2 9  3 7 9
  7 8 9  7 8 9  7 6 5  8 9 5  5 4 3  4 5 6

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

Row 9 of A186861.

a(n) = 3349864*n^2 - 25942968*n + 47890984 for n>7.

a(n) = 3*a(n-1) - 3*a(n-2) + a(n-3) for n > 10. - Stefano Spezia, Oct 28 2023

cp's OEIS Frontend

A186861 Array read by antidiagonals: T(n,k) is the number of n-step king's tours on a k X k board summed over all starting positions.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A186863 Number of 4-step king's tours on an n X n board summed over all starting positions.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A186867 Number of 8-step king's tours on an n X n board summed over all starting positions.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A186865 Number of 6-step king's tours on an n X n board summed over all starting positions.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A186866 Number of 7-step king's tours on an n X n board summed over all starting positions.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A366829 Number of 9-step self-avoiding king's tours on an n X n board summed over all starting positions.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula