A284287 Number of possible legal open chains of a set of dominoes tiles with 0 to 2n pips.

12, 126720, 7959229931520, 10752728122249860612096000, 829276462388385539562198269952000000000000, 7969891788752886799729592752113502210704733844275200000000000000, 18306383771271364475276585375748692499524930312437317320546133915243380736000000000000000000

Offset: 1

Author

Amiram Eldar, Mar 24 2017

Keywords

• nonn

Comments

a(3) corresponds to the standard double-six set of 28 tiles. The question for its value was asked by Louis Poinsot in 1809 and by Orly Terquem in 1849 and was first calculated by Michel Reiss in 1859 (published in 1871).

The problem of finding a(2) appears in Henry Dudeney's book.

a(4) was calculated by Gaston Tarry in 1886.

The number of legally closed chains is a(n)/((n+1)*(2n+1)) = n^(2n+1) * A135388(n) (i.e., divided by the number of tiles in the set, A000217(2n+1)) = 2, 8448, 284258211840, 238949513827774680268800, ... .

If reverse order is not counted, the number of open chains is a(n)/2 = 6, 63360, 3979614965760, 5376364061124930306048000, ..., and the number of closed chains is a(n)/(2*(n+1)*(2n+1)) = 1, 4224, 142129105920, 119474756913887340134400, ... .

Examples

			For n=1 there is 1 basic chain of 6 tiles: (0|0)(0|1)(1|1)(1|2)(2|2)(2|0). There are 6 cyclic permutations and a 2nd version for each, in a reverse order, so a(1) = 1 * 6 * 2 = 12.
		

References

• Henry Ernest Dudeney, "The Fifteen Dominoes", Amusements in Mathematics, Nelson, Edinburgh 1917, pp. 209-210.
• Martin Gardner, Mathematical Circus, Alfred A. Knopf, NY, 1979, pp. 137-142.
• Donald E. Knuth, The Art of Computer Programming, Volume 4A, Addison-Wesley, 2011, pp. 389 and 745.
• K. W. H. Leeflang, Domino games and domino puzzles, St. Martin's Press, New York, 1975, Chapter VIII, section 1, pp. 125-134.
• Édouard Lucas, "La géométrie des réseaux et le problème des dominos", Récréations mathématiques, Volume 4, Gauthier-Villars, Paris, 1894, pp. 125-129.
• Yakov Perelman, Figures for Fun, Foreign Languages Publishing House, Moscow, 1957, p. 38.
• Miodrag S. Petković, "Poinsot's Diagram-tracing Puzzle", Famous Puzzles of Great Mathematicians, Amer. Math. Soc. (AMS), Providence RI, 2009, pp. 245-247
• Michel Reiss, Evaluation du nombre de combinaisons desquelles les 28 dés d'un jeu du Domino sont susceptibles d'après la règle de ce jeu, Annali di Matematica Pura ed Applicata, Vol. 5.1 (1871), pp. 63-120.
• W. W. Rouse Ball and H. S. M. Coxeter, Mathematical Recreations and Essays, Dover NY, 1987, pp. 243-254.

Links

• Amiram Eldar, Table of n, a(n) for n = 1..10
• Pierre Audibert, Enumeration of Eulerian Paths in Undirected Graphs, Mathematics for Informatics and Computer Science, Wiley, 2010, Chapter 36, Section 36.4.1., "Number of domino chains", pp. 813-816.
• Philippe Chevanne, Eulériens (in French); Eulerian circuits (English translation, Wayback Machine link).
• Henry Ernest Dudeney, The Fifteen Dominoes, Amusements in Mathematics, 1917.
• Martin Gardner, A handful of combinatorial problems based on dominoes, Mathematical Games, Scientific American, Vol. 221, No. 6 (1969), pp. 122-127; JSTOR link.
• Italo Ghersi, Matematica dilettevole e curiosa (in Italian), Hoepli, Milano, 1913, p. 695.
• Allan J. Gottlieb, Streaker at the Banquet Table, Puzzle Corner, Technology Review, MIT, June 1976, pp. 64-69.
• Donald E. Knuth, Generating all combinations, The Art of Computer Programming, Volume 4, Combinatorial Algorithms, p. 35 and 57.
• Édouard Lucas, Récréations mathématiques, Vol. 4., pp. 125-129.
• Brendan D. McKay and Robert W. Robinson, Asymptotic Enumeration of Eulerian Circuits in the Complete Graph, Combinatorics, Probability and Computing, Vol. 7, No. 4 (1998), pp. 437-449; author's copy.
• L. Poinsot, Mémoire sur les polygones et les polyèdres, J. de l'Ecole Polytechnique, Volume 4 (1810) pp. 16—49.
• M. Reiss, Evaluation du nombre de combinaisons desquelles les 28 dés d'un jeu du Domino sont susceptibles d'après la règle de ce jeu, Annali di Matematica Pura ed Applicata, Vol. 5.1 (1871), pp. 63-120; HathiTrust link.
• G. Tarry, Géométrie de situation: Nombre de manières distinctes de parcourir en une seule course toutes les allées d'un labyrinthe rentrant, en ne passant qu'une seule fois par chacune des allées, Comptes Rendus Assoc. Franç. Avance. Sci. 15, part 2 (1886), pp. 49-53.
• O. Terquem, Sur les polygones et les polyèdres étoilés, polygones funiculaires, Nouv. Ann. Math., Vol. 8 (1849), pp. 68-74.

Crossrefs

Cf. A000217, A007082, A135388.

Formula

a(n) = (n+1)*(2n+1)*n^(2n+1)*A135388(n) = (n+1)*(2n+1)*n^(2n+1)*(n-1)!^(2n+1)*A007082(n).