Don Knuth - cp's OEIS frontend

User: Don Knuth

Don Knuth has authored 232 sequences. Here are the ten most recent ones:

A384294 The number of Hamiltonian cycles in the concentric ring graph of order n.

6, 12, 30, 34, 56, 108, 150, 244, 418, 642, 1040, 1712, 2726, 4412, 7174, 11554, 18696, 30292, 48950, 79204, 128202, 207362, 335520, 542936, 878406, 1421292, 2299758, 3720994, 6020696, 9741756, 15762390, 25504084, 41266546, 66770562, 108037040, 174807680, 282844646, 457652252, 740496982, 1198149154, 1938646056

Offset: 3

Don Knuth, May 24 2025

The concentric ring graph of order n is a cubic graph with 4n vertices and 6n edges. If we name the vertices a_j,b_j,c_j,d_j for 0<=j

When n=5 it is isomorphic to the graph of the dodecahedron, which Hamilton used when he first considered "Hamiltonian cycles".

			The a[3]=6 cycles when n=3 are:
  a0--a1--a2--b2--c1--b1--c0--d0--d1--d2--c2--b0--a0,
  a0--a1--a2--b2--c2--d2--d0--d1--c1--b1--c0--b0--a0,
  a0--a1--b1--c0--b0--c2--d2--d0--d1--c1--b2--a2--a0,
  a0--a1--b1--c1--d1--d2--d0--c0--b0--c2--b2--a2--a0,
  a0--b0--c0--d0--d1--d2--c2--b2--c1--b1--a1--a2--a0,
  a0--b0--c2--b2--c1--d1--d2--d0--c0--b1--a1--a2--a0.

Donald E. Knuth, Prefascicle 8a of The Art of Computer Programming (planned to become part of Volume 4C).

Don Knuth, Table of n, a(n) for n = 3..100
Index entries for linear recurrences with constant coefficients, signature (1,1,2,-2,-2,-1,1,1).

Cf. A000032 (Lucas numbers).

a[n_]:=2LucasL[n]-2+If[Mod[n, 3]==2, 2n, 0]; Array[a,41,3]

a(n) = 2*Lucas(n) - 2 + 2*n*[Mod(n,3)==2], where [ ] denotes the Iverson bracket.

G.f.: -2*x^3*(3+3*x+6*x^2-10*x^3-10*x^4-3*x^5+4*x^6+4*x^7) / ( (x^2+x-1)*(x-1)^2*(1+x+x^2)^2 ). - R. J. Mathar, May 26 2025

A383661 Number of closed knight's tours in the first 2n cells of a 5 X ceiling(2n/5) board.

Original entry on oeis.org

1, 0, 1, 30, 0, 148, 8, 78, 9309, 612, 62749, 44202, 42049, 2916485, 147192, 18284136, 13311268, 13008389, 973107552, 51147756, 6190192748, 4557702762, 4311375354, 316985255470, 16552301184, 2015267424300, 1495135512514, 1417634375316, 104324890543686, 5459334927260, 663068761241948

Offset: 9

Don Knuth, May 04 2025

nonn

If n is not a multiple of 5, the rightmost column has only 2n mod 5 rows (see example).

			For n=9 the a(9)=1 example is
  1 14  5 10
  4  9  2 15
 13 18 11  6
  8  3 16
 17 12  7    .

Donald E. Knuth, Hamiltonian paths and cycles. Prefascicle 8a of The Art of Computer Programming (work in progress, 2025).

Don Knuth, Table of n, a(n) for n = 9..150
Don Knuth, CWEB program with input parameter board,60,5,0,0,5,0,0.gb [the graph "board(50, 6, 0, 0, 5, 0, 0)" generated by the Stanford GraphBase].

Cf. A175855, A383660, A383662, A383663, A383664.

a(5n) = A175855(n).

A383663 Number of closed knight's tours in the first 2n cells of a 7 X ceiling(2n/7) board.

Original entry on oeis.org

2, 11, 58, 0, 21, 1020, 9309, 1481, 34162, 1295034, 1067638, 2213327, 50139185, 682189688, 144994543, 2607067351, 53099426601, 34524432316, 57716933870, 1388556345255, 16330667126220, 3697750041989, 70341043737487, 1662805965511580, 1250063279938854, 2122662114673944

Offset: 11

Don Knuth, May 04 2025

nonn

If n is not a multiple of 7, the rightmost column has only 2n mod 7 rows (see example).

			For n=11, the first of a(11)=2 solutions is
  1  4 21  6
 20  7  2
  3 22  5
  8 19 10
 11 16 13
 14  9 18
 17 12 15
and the other is obtained by reflecting the bottom four rows:
  1  4 21  6
 20  7  2
  3 22  5
 10 19  8
 13 16 11
 18  9 14
 15 12 17 .

Donald E. Knuth, Hamiltonian paths and cycles. Prefascicle 8a of The Art of Computer Programming (work in progress, 2025).

Don Knuth, Table of n, a(n) for n = 11..147
Don Knuth, CWEB program with input parameter board,42,7,0,0,5,0,0.gb [the graph "board(50, 6, 0, 0, 5, 0, 0)" generated by the Stanford GraphBase].

Cf. A193054, A383660, A383661, A383662, A383664.

a(7n) = A193054(n).

A383664 Number of closed knight's tours in the first 2n cells of an 8 X ceiling(2n/8) board.

Original entry on oeis.org

4, 12, 212, 0, 50, 4525, 101730, 44202, 66034, 2408624, 69362264, 55488142, 101343548, 2398536889, 43391615822, 34524432316, 52661182514, 1231713564493, 20780788492646, 13267364410532, 21515340977481, 552407941427835, 10211663162678661, 7112881119092574, 11873618786859165

Offset: 13

Don Knuth, May 04 2025

nonn

If n is not a multiple of 4, the rightmost column has only 2n mod 8 rows (see example).

			For n=13 the a(13)=4 solutions are
  1  4 25 12
 24 11  2  5
  3 26 13
 10 23  6
  7 14  9
 22 17 20
 19  8 15
 16 21 18   ;
  1  4 25 12
 24 11  2  5
  3 26 13
 10 23  6
  7 14  9
 20 15 22
 15  8 19
 18 21 16   ;
  1 14 25 22
 24 21  2 15
 13 26 23
 20  3 16
 17 12 19
  4  9  6
  7 18 11
 10  5  8   ;
  1 14 25 22
 24 21  2 15
 13 26 23
 20  3 16
 17 12 19
  6  9  4
 11 18  7
  8  5 10   .

Donald E. Knuth, Hamiltonian paths and cycles, Prefascicle 8a of The Art of Computer Programming (work in progress, 2025).

Don Knuth, Table of n, a(n) for n = 13..96
Don Knuth, CWEB program with input parameter board,32,8,0,0,5,0,0.gb [the graph "board(50, 6, 0, 0, 5, 0, 0)" generated by the Stanford GraphBase].

Cf. A193055, A383660, A383661, A383662, A383663.

a(4n) = A193055(n).

A383662 Number of closed knight's tours in the first 2n cells of a 6 X ceiling(2n/6) board.

Original entry on oeis.org

6, 0, 2, 302, 8, 151, 19072, 9862, 18202, 1603948, 1067638, 1310791, 107096187, 55488142, 66608924, 6149236417, 3374967940, 4259963914, 402706752421, 239187240144, 292999006211, 26470682075988, 15360134570696, 18595568012716, 1685811256230132, 964730606632516, 1173328484648288

Offset: 11

Don Knuth, May 04 2025

nonn

If n is not a multiple of 3, the rightmost column has only 2n mod 6 rows (see example).

			For n=11, one of the a(11)=6 solutions is
  1  4 13 16
 12 15  2  5
  3 22 17 14
  8 11  6 19
 21 18  9
 10  7 20   .

Donald E. Knuth, Hamiltonian paths and cycles, Prefascicle 8a of The Art of Computer Programming (work in progress, 2025).

Don Knuth, Table of n, a(n) for n = 11..150
Don Knuth, CWEB program with input parameter board,50,6,0,0,5,0,0.gb [the graph "board(50, 6, 0, 0, 5, 0, 0)" generated by the Stanford GraphBase].

Cf. A175881, A383660, A383661, A383663, A383664.

a(3n) = A175881(n).

A383660 Number of closed knight's tours in the first 2n cells of a 3 X ceiling(2n/3) board.

Original entry on oeis.org

4, 0, 4, 24, 16, 56, 306, 176, 456, 2632, 1536, 4828, 26788, 15424, 44952, 254288, 147728, 448032, 2502568, 1448416, 4310048, 24228704, 14060048, 42195584, 236335248, 136947616, 409403328, 2297294496, 1332257856, 3989883552, 22366625344, 12965578752, 38798663104, 217604833360, 126169362176

Offset: 11

Don Knuth, May 04 2025

nonn

If n is not a multiple of 3, the rightmost column has only 2n mod 3 rows (see example).

			For n=11 the a(11)=4 solutions are
  1  4  7 10 17 20 15 12
  6  9  2 21 14 11 18
  3 22  5  8 19 16 13    ;
  1  4  7 14 11 20  9 18
  6 15  2 21  8 17 12
  3 22  5 16 13 10 19    ;
  1  4 21 12 15  6 17  8
 20 11  2  5 18  9 14
  3 22 19 10 13 16  7    ;
  1  4 21 18  9  6 11 14
 20 17  2  5 12 15  8
  3 22 19 16  7 10 13    .

Donald E. Knuth, Hamiltonian paths and cycles, Prefascicle 8a of The Art of Computer Programming (work in progress, 2025).

Don Knuth, Table of n, a(n) for n = 11..150
Don Knuth, CWEB program with input parameter board,100,3,0,0,5,0,0.gb [the graph "board(50, 6, 0, 0, 5, 0, 0)" generated by the Stanford GraphBase.

Cf. A070030, A383661, A383662, A383663, A383664.

a(3n) = A070030(n).

A383154 The number of 2n-by-2n fers-wazir tours.

Original entry on oeis.org

2, 2, 22, 1620, 882130, 3465050546

Offset: 1

Don Knuth, Apr 18 2025

The simplest fairy chess pieces, going back to 9th-century Persia, are the fers -- a (1,1) leaper -- and the wazir -- a (1,0) leaper. (A king combines the moves of a fers and a wazir.) A fers-wazir tour visits every cell of a board exactly once, making fers and wazir moves alternately, and returns to the starting cell.

Such tours exist only when the number of rows is even and the number of columns is even.

			For n=2 the a(2) = 2 solutions are transposes of each other:
.
  0-f 4-3   0 e-d b
   X   X    |X   X|
  e 1-2 5   f 1 a c
  |     |     | |
  d a-9 6   4 2 9 7
   X   X    |X   X|
  b-c 7-8   3 5-6 8

D. E. Knuth, Hamiltonian paths and cycles, Section 7.2.2.4 of The Art of Computer Programming (to appear).

George Jelliss, Introducing Knight's Tours, has a 9th century example of a fers-knight tour due to As-Suli.

Diagonal of A383153.

Cf. A140519.

A383153 Square array read by antidiagonals: A(m,n) is the number of 2m-by-2n fers-wazir tours.

Original entry on oeis.org

2, 1, 1, 1, 2, 1, 1, 4, 4, 1, 1, 9, 22, 9, 1, 1, 23, 124, 124, 23, 1, 1, 62, 818, 1620, 818, 62, 1, 1, 170, 6004, 25111, 25111, 6004, 170, 1, 1, 469, 46488, 455219, 882130, 455219, 46488, 469, 1, 1, 1297, 367880, 9103712, 36979379, 36979379, 9103712, 367880, 1297, 1

Offset: 1

Don Knuth, Apr 18 2025

The simplest fairy chess pieces, going back to 9th-century Persia, are the fers -- a (1,1) leaper -- and the wazir -- a (1,0) leaper. (A king combines the moves of a fers and a wazir.) A fers-wazir tour visits every cell of a board exactly once, making fers and wazir moves alternately, and returns to the starting cell.
Such tours exist only when the number of rows is even and the number of columns is even.
For fixed m, these tours can be enumerated with the transfer-matrix method, so the numbers A(m,n) satisfy a linear recurrence.

			Array begins: (example extended by _Filip Stappers_, Apr 21 2025)
  2,   1,    1,     1,      1,        1,       1,      1,    1,    1,    1,     1, ...
  1,   2,    4,     9,     23,       62,     170,    469, 1297, 3590, 9940, 27525, ...
  1,   4,   22,   124,    818,     6004,   46448, 367880, ...
  1,   9,  124,  1620,  25111,   455219, 9103712, ...
  1,  23,  818, 25111, 882130, 36979379, ...
  1,  62, 6004, ...
  1, 170, ...
  1, ...
  ...
For m = 2 and n = 3, the A(2,3) = 4 solutions are the following 4-by-6 tours (a to b to ... to x):
.
  a-x e-d i-h   a w-v p-q s   a w-v s-r p   a w-v d-e g
   X   X   X    |X   X   X|   |X   X   X|   |X   X   X|
  w b-c f-g j   x b o u-t r   x b t-u o q   x b-c u h f
  |         |     | |           |     |           | |
  v s-r o-n k   e c n h-i k   e c i-h n l   q o-n t i k
   X   X   X    |X   X   X|   |X   X   X|   |X   X   X|
  t-u p-q l-m   d f-g m-l j   d f-g j-k m   p r-s m-l j

D. E. Knuth, Hamiltonian paths and cycles, Section 7.2.2.4 of The Art of Computer Programming (to appear).

D. E. Knuth, Table of n, a(n) for n = 1..66
George Jelliss, Introducing Knight's Tours, has a 9th century example of a fers-knight tour due to As-Suli.

Cf. A383154 (the diagonal A(n,n)).

Cf. A339190 (the analog for king tours).

G.f. of column 2: z*(1 - 2*z - z^3)/((1 - z)*(1 - 3*z + z^2 - z^3)). - Filip Stappers, Apr 21 2025

A373796 a(n) = Product_{k=1..n} k^Stirling_2(n,k).

Original entry on oeis.org

1, 1, 2, 24, 373248, 145563074713240071045120, 4671362199215574200933052290575558394040074468464419088211590760845408889948035734306816000000000000000

Offset: 0

N. J. A. Sloane, Jul 07 2024, based on an email from Don Knuth, Jul 06 2024

nonn

a(n) is the number of n-ary clones of the "discriminator function" t(x,y,z) defined by t(x,y,z)=x if x != y, t(x,x,z)=z.
For example, one of the 24 clones when n=3 is the function f(x,y,z)=t(t(y,z,x),x,t(x,y,z)), which has the property that f(x,x,x)=x, f(x,x,y)=y, f(x,y,x)=y, f(x,y,y)=x, f(x,y,z)=y when x,y,z are distinct. There are 24 meaningful ways to specify the right-hand sides of these five equations, and each of those functions can be expressed as a term in t.
There are a(4) meaningful ways to specify the right-hand sides of A000110(4)=15 analogous equations for a four-parameter function, and so on. - Don Knuth, Jul 07 2024

Hugo Pfoertner, Table of n, a(n) for n = 0..7
Alden F. Pixley, The Ternary Discriminator Function in Universal Algebra, Mathematische Annalen, 191 (1971), 167-180.

Cf. A008277, A319761.

a:= n-> mul(k^Stirling2(n,k), k=1..n):
seq(a(n), n=0..6);  # Alois P. Heinz, Jan 30 2025

A373796[n_] := Product[k^StirlingS2[n, k], {k, n}];
Array[A373796, 8, 0] (* Paolo Xausa, Jul 10 2024 *)

a(n)=prod(k=1,n,k^stirling(n,k,2)) \\ Hugo Pfoertner, Jul 07 2024

A372068 Array read by antidiagonals: T(m,n) (m >= 0, n >= 0) = number of max-and-min-closed constraints between an m-element set and an n-element set.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 4, 4, 1, 1, 8, 13, 8, 1, 1, 16, 38, 38, 16, 1, 1, 32, 104, 147, 104, 32, 1, 1, 64, 272, 506, 506, 272, 64, 1, 1, 128, 688, 1612, 2103, 1612, 688, 128, 1, 1, 256, 1696, 4856, 7887, 7887, 4856, 1696, 256, 1, 1, 512, 4096, 14016, 27477, 34088, 27477, 14016, 4096, 512, 1

Offset: 0

N. J. A. Sloane, May 12 2024, based on emails from Don Knuth, May 06 2024 and May 08 2024

See the Knuth "Notes" link for much more information about these sequences. The present sequence is called "tab" in Part 2 of the Notes.

			The initial antidiagonals are:
   1,
   1, 1,
   1, 2, 1,
   1, 4, 4, 1,
   1, 8, 13, 8, 1,
   1, 16, 38, 38, 16, 1,
   1, 32, 104, 147, 104, 32, 1,
   1, 64, 272, 506, 506, 272, 64, 1,
   1, 128, 688, 1612, 2103, 1612, 688, 128, 1,
   1, 256, 1696, 4856, 7887, 7887, 4856, 1696, 256, 1,
   1, 512, 4096, 14016, 27477, 34088, 27477, 14016, 4096, 512, 1,
   ...
The array begins:
   1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...
   1, 2, 4, 8, 16, 32, 64, 128, 256, 512, ...
   1, 4, 13, 38, 104, 272, 688, 1696, 4096, 9728, ...
   1, 8, 38, 147, 506, 1612, 4856, 14016, 39104, 106112, ...
   1, 16, 104, 506, 2103, 7887, 27477, 90498, 285072, 865856, ...
   1, 32, 272, 1612, 7887, 34088, 134825, 498465, 1746830, 5859404, ...
   1, 64, 688, 4856, 27477, 134825, 597539, 2451038, 9455182, 34687916, ...
   1, 128, 1696, 14016, 90498, 498465, 2451038, 11055950, 46570858, 185484836, ...
   1, 256, 4096, 39104, 285072, 1746830, 9455182, 46570858, 212833803, 914854829, ...
   1, 512, 9728, 106112, 865856, 5859404, 34687916, 185484836, 914854829, 4223468802, ...
   ...

D. E. Knuth, Notes on four arrays of numbers arising from the enumeration of CRC constraints and min-and-max-closed constraints, May 06 2024

Cf. A099594, A100754, A272644, A372066, A372067.

cp's OEIS Frontend

User: Don Knuth

A384294 The number of Hamiltonian cycles in the concentric ring graph of order n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

A383661 Number of closed knight's tours in the first 2n cells of a 5 X ceiling(2n/5) board.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

A383663 Number of closed knight's tours in the first 2n cells of a 7 X ceiling(2n/7) board.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

A383664 Number of closed knight's tours in the first 2n cells of an 8 X ceiling(2n/8) board.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

A383662 Number of closed knight's tours in the first 2n cells of a 6 X ceiling(2n/6) board.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

A383660 Number of closed knight's tours in the first 2n cells of a 3 X ceiling(2n/3) board.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

A383154 The number of 2n-by-2n fers-wazir tours.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

A383153 Square array read by antidiagonals: A(m,n) is the number of 2m-by-2n fers-wazir tours.

Views

Author

Keywords

Comments

Examples

References