Johan de Ruiter - cp's OEIS frontend

A305190 a(n) is the number of different numbers of Hamiltonian cycles (up to direction) in graphs with n vertices.

1, 1, 2, 3, 6, 16, 49, 232, 1351, 10367

Offset: 1

Johan de Ruiter, May 27 2018

			A graph on 4 vertices can have either 0, 1 or 3 Hamiltonian cycles (up to direction), which are 3 numbers, so a(4)= 3.

Erich Friedman, Math Magic (September 2012)

Cf. A244511.

A214624 Braid numbers B((2)^n->(2)^n).

Original entry on oeis.org

1, 1, 16, 504, 28800, 2620800, 348364800, 63707212800, 15343379251200, 4707627724800000, 1792664637603840000, 829619584788234240000, 458592296933263933440000, 298435681233688170332160000, 225843218230899155927040000000, 196652982274555440023470080000000

Offset: 0

Johan de Ruiter, Jul 23 2012

The number of different possible outcomes when starting with n piles of 2 distinct playing cards and repeatedly moving a top card from either of these n piles to one of n new piles, until all new piles have height 2.

J. de Ruiter, Counting Classes of Klondike Solitaire Configurations, Master's Thesis (2012), 48-58.

a(n) = (2*n)!*(3*n-2)/(4*n-2); \\ Michel Marcus, Aug 18 2013

a(n) = (2*n)!-n^2*(2*n-2)! for n>0.
a(n) = (2*n)!*(3*n-2)/(4*n-2).
a(n) = a(n-1)*2*n*(2*n-3)*(3*n-2)/(3*n-5) for n>0.
a(n) = Sum_{i=1..n} a(n-i)*C(n,i)*C(n-1,i-1)*i!*(i-1)!*(2^(2*i-1)-1) for n>0.
a(n) = Sum_{i=0..n-1} a(i)*n!*(n-1)!*(2^(2*n-2*i-1)-1)/(i!)^2 for n>0. [corrected by Jason Yuen, Oct 27 2024]
a(n) = Sum_{i=0..n-1} a(i)*((2*n)!!*(2*n-2)!!/((2*i)!!)^2-n!*(n-1)!/(i!)^2) for n>0. [corrected by Jason Yuen, Oct 27 2024]

More terms from Michel Marcus, Aug 18 2013

A214623 Braid numbers B((n,n)->(n,n)).

Original entry on oeis.org

1, 2, 16, 128, 1156, 10952, 107584, 1083392, 11115556, 115702472, 1218289216, 12948910592, 138708574096, 1495661223968, 16218468710656, 176727219273728, 1933956651447076, 21243204576601928, 234121111199439424, 2587943032046002688

Offset: 0

Johan de Ruiter, Jul 23 2012

nonn

The number of different possible outcomes when starting with two piles of n distinct playing cards and repeatedly moving a top card from either of these two piles to one of two new piles, until both new piles have height n.

For even values of n, a(n) is a square, while for odd values of n, a(n) is twice a square.

J. de Ruiter, Counting Classes of Klondike Solitaire Configurations, Master's Thesis (2012), 48-58.

a[n_] := (-2)^n HypergeometricPFQ[{1/2, -n, n + 1}, {1, 1}, 2];
Table[a[n], {n, 0, 19}] (* Peter Luschny, Mar 14 2018 *)

G.f.: hypergeom([1/12, 5/12],[1],1728/(16*x^4-32*x^3-24*x^2-8*x+1)^3*x^4*(4*x^2-12*x+1)*(2*x+1)^2)/(16*x^4-32*x^3-24*x^2-8*x+1)^(1/4); (based on guessed recurrence). - Mark van Hoeij, Apr 11 2014
a(n) = (-2)^n*hypergeom([1/2, -n, n + 1], [1, 1], 2). - Peter Luschny, Mar 14 2018
a(n) ~ 2^(n - 3/2) * (1 + sqrt(2))^(2*n + 1) / (Pi*n). - Vaclav Kotesovec, Jun 09 2019
G.f.: Sum_{n >= 0} binomial(2*n,n)^2*x^n/(1 + 2*x)^(2*n+1). - Peter Bala, Feb 07 2022

A178673 Duplicate of A028452.

Original entry on oeis.org

1, 229, 117805, 64647289, 35669566217, 19690797527709, 10870506600976757, 6001202979497804657, 331304283062403135451, 1829008840116358153050197, 1009728374600381843221483965

Offset: 0

Johan de Ruiter, Dec 25 2010

dead

A175881 Number of closed Knight's tours on a 6 X n board.

Original entry on oeis.org

0, 0, 0, 0, 8, 9862, 1067638, 55488142, 3374967940, 239187240144, 15360134570696, 964730606632516, 61989683445413228, 4005716717182224826, 255967892553030600920, 16378998506224697063588, 1050504687249683771795632, 67351449674771471216148786, 4314151246752166099728445868

Offset: 1

Johan de Ruiter, Dec 05 2010

nonn

Could you please say how you calculated these numbers? - N. J. A. Sloane, Dec 05 2010?

I kept track of pairs of loose ends within the two rightmost columns of a 6 X n board, assuming that everything to the left of these two columns is fully connected and that there are no cycles (or one if this is a final state). Next I added a new column and connected it to the rightmost two columns in all ways such that there are no cycles formed(or one if this results in a final state) and the leftmost column in the current state is fully connected and can be dropped. From this followed a transition matrix. I can provide a reference to my writeup once it is completed and has been accepted by my supervisor. - Johan de Ruiter, Dec 05 2010

			The smallest 6 X n board admitting a closed Knight's tour is the 6 X 5, on which there are 8 such tours.

Johan de Ruiter, Table of n, a(n) for n = 1..40
J. de Ruiter, Counting Domino Coverings and Chessboard Cycles, 2010.

A070030 deals with 3 X 2n boards, A175855 with 5 X 2n boards.

Cf. A383662.

a(n) = A383662(3n). - Don Knuth, May 05 2025

A175855 The number of closed Knight's tours on a 5 X 2n board.

Original entry on oeis.org

0, 0, 8, 44202, 13311268, 4557702762, 1495135512514, 491857035772330, 161514101568508400, 53034853662012222798, 17414154188157170439208, 5717847862749642677204182, 1877435447920358266870897874, 616447390029326136628439042672, 202407848349722353779265745190616, 66459727085467788423206394162537418, 21821760546806761707309514948565417796, 7165079447164571822068029945303172129766, 2352622444655438705806553391345493395131580, 772473271844923268504474277422663237674924998

Offset: 1

Johan de Ruiter, Dec 05 2010

nonn

			The smallest 5 X 2n board admitting a closed Knight's tour is the 5 X 6, on which there are 8 such tours.

J. de Ruiter, Counting Domino Coverings and Chessboard Cycles, 2010.

A070030 deals with 3 X 2n boards, A175881 deals with 6 X n boards.

Cf. A383661.

a(n) = A383661(5n). - Don Knuth, May 05 2025

A172478 The number of ways to dissect an n X n square into polyominoes of size n and then fill it to make it a Latin square, with the extra requirement that each number occurs within each polyomino exactly once.

Original entry on oeis.org

1, 4, 72, 13872, 11762160, 234312972480, 41182101508222080

Offset: 1

Johan de Ruiter, Feb 04 2010

nonn

a(n) is the number of completed n X n jigsaw sudoku puzzles.

			A 2 X 2 square can be covered by two dominoes by either positioning them vertically or horizontally. Both of these coverings allow for two 2 X 2 Latin squares without violating the extra constraint.

J. de Ruiter, On Jigsaw Sudoku Puzzles and Related Topics, Bachelor Thesis, Leiden Institute of Advanced Computer Science, 2010. [From Johan de Ruiter, Jun 15 2010]

Cf. A002860 (Number of Latin squares of order n), A172477 (Number of ways to dissect an n X n square into polyominoes of size n).

A173103 The number of possible borders of Latin squares with the top row fixed.

Original entry on oeis.org

1, 1, 2, 26, 924, 81624, 13433520, 3706068240, 1582042381920, 987057348842880, 861632512758823680, 1016677874552767660800, 1576819957670934809817600, 3140963381712726319842892800, 7880571655922780897709237811200, 24492587962448960350527019884595200

Offset: 1

Johan de Ruiter, Feb 09 2010

nonn

The definition is not quite right, and should be corrected.

			The only two configurations for n=3, given the top row is 123:
  123   123
  2 1   3 2
  312   231
Two arbitrary configurations for n=4, given the top row is 1234:
  1234   1234
  2  1   4  3
  3  2   3  2
  4123   2341

Alois P. Heinz, Table of n, a(n) for n = 1..100
J. de Ruiter, On Jigsaw Sudoku Puzzles and Related Topics, Bachelor Thesis, Leiden Institute of Advanced Computer Science, 2010.

Related to A000166. Equals A173104 divided by n!.

d:= proc(n) d(n):= `if`(n<=1, 1-n, (n-1)*(d(n-1)+d(n-2))) end:
a:= proc(n) a(n):= `if`(n<4, [1, 1, 2][n], (n-2)!*((n-1)/
       (n-2)*d(n-1)^2+2*d(n-1)*d(n-2)+(2*n-5)/(n-3)*d(n-2)^2))
    end:
seq(a(n), n=1..20);  # Alois P. Heinz, Aug 18 2013

d = Subfactorial;
a[n_] := If[n <= 3, {1, 1, 2}[[n]], (n-2)! (((2n-5) d[n-2]^2)/(n-3) + 2d[n-1] d[n-2] + ((n-1) d[n-1]^2)/(n-2))];
Array[a, 20] (* Jean-François Alcover, Nov 10 2020 *)

For n>3, a(n)=(n-2)!((n-1)/(n-2)d[n-1]^2+2d[n-1]d[n-2]+(2n-5)/(n-3)d[n-2]^2), where d[k] is the number of derangements of k elements (A000166).

A173104 The number of possible borders of Latin squares.

Original entry on oeis.org

1, 2, 12, 624, 110880, 58769280, 67704940800, 149428671436800, 574091539551129600, 3581833707481042944000, 34393612685291413069824000, 486990328595374993951457280000, 9818890674272030616178239406080000, 273823820339488809857168046768783360000

Offset: 1

Johan de Ruiter, Feb 09 2010

nonn

The definition is not quite right, and should be corrected.

			Two arbitrary configurations for n=3:
  123   312
  2 1   1 3
  312   231
Two arbitrary configurations for n=4:
  1234   1432
  2  1   3  4
  3  2   4  1
  4123   2143

Alois P. Heinz, Table of n, a(n) for n = 1..100
J. de Ruiter, On Jigsaw Sudoku Puzzles and Related Topics, Bachelor Thesis, Leiden Institute of Advanced Computer Science, 2010.

Related to A000166. Equals A173103 multiplied by n!.

d:= proc(n) d(n):= `if`(n<=1, 1-n, (n-1)*(d(n-1)+d(n-2))) end:
b:= proc(n) b(n):= `if`(n<4, [1, 1, 2][n], (n-2)!*((n-1)/
       (n-2)*d(n-1)^2+2*d(n-1)*d(n-2)+(2*n-5)/(n-3)*d(n-2)^2))
    end:
a:= n-> n!*b(n):
seq(a(n), n=1..20);  # Alois P. Heinz, Aug 18 2013

d = Subfactorial;
a[n_] := If[n <= 3, {1, 2, 12}[[n]], n! (n-2)! ((n-1)/(n-2) d[n-1]^2 + 2d[n-1] d[n-2] + (2n-5)/(n-3) d[n-2]^2)];
Array[a, 20] (* Jean-François Alcover, Nov 10 2020 *)

For n>3, a(n)=n!(n-2)!((n-1)/(n-2)d[n-1]^2+2d[n-1]d[n-2]+(2n-5)/(n-3)d[n-2]^2), where d[k] is the number of derangements of k elements (A000166).

A172477 The number of ways to dissect an n X n square into polyominoes of size n.

Original entry on oeis.org

1, 2, 10, 117, 4006, 451206, 158753814, 187497290034, 706152947468301

Offset: 1

Johan de Ruiter, Feb 04 2010

nonn

			A 2 X 2 square can be covered by two dominoes by either positioning them vertically or horizontally.

Jiahua Chen, Aneesha Manne, Rebecca Mendum, Poonam Sahoo, Alicia Yang, Minority Voter Distributions and Partisan Gerrymandering, arXiv:1911.09792 [cs.CY], 2019.
Johan de Ruiter, On Jigsaw Sudoku Puzzles and Related Topics, Bachelor Thesis, Leiden Institute of Advanced Computer Science, 2010.
Christopher Donnay and Matthew Kahle, Asymptotics of Redistricting the n X n grid, arXiv:2311.13550 [math.CO], 2023.
R. S. Harris, Counting Nonomino Tilings and Other Things of that Ilk, G4G9 Gift Exchange book, 2010.
R. S. Harris, Counting Polyomino Tilings [From Bob Harris (me13013(AT)gmail.com), Mar 13 2010]

Intersects with A167251, A167254, A167255, A167258.

Diagonal of A348452.

a(3) = A167243(3). a(4) = A167248(4). a(5) = A167251(5). a(6) = A167254(6). a(7) = A167255(7). a(8) = A167258(8). - R. J. Mathar, Oct 13 2024

a(9) from Bob Harris (me13013(AT)gmail.com), Mar 13 2010

cp's OEIS Frontend

User: Johan de Ruiter

A305190 a(n) is the number of different numbers of Hamiltonian cycles (up to direction) in graphs with n vertices.

Views

Author

Keywords

Examples

Links

Crossrefs

A214624 Braid numbers B((2)^n->(2)^n).

Views

Author

Keywords

Comments

Links

Programs

PARI

Formula

Extensions

A214623 Braid numbers B((n,n)->(n,n)).

Views

Author

Keywords

Comments

Links

Programs

Mathematica

Formula

A178673 Duplicate of A028452.

Views

Author

Keywords

A175881 Number of closed Knight's tours on a 6 X n board.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A175855 The number of closed Knight's tours on a 5 X 2n board.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A172478 The number of ways to dissect an n X n square into polyominoes of size n and then fill it to make it a Latin square, with the extra requirement that each number occurs within each polyomino exactly once.

Views

Author

Keywords

Comments

Examples

References

Crossrefs

A173103 The number of possible borders of Latin squares with the top row fixed.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A173104 The number of possible borders of Latin squares.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica