A014552 Number of solutions to Langford (or Langford-Skolem) problem (up to reversal of the order).

0, 0, 1, 1, 0, 0, 26, 150, 0, 0, 17792, 108144, 0, 0, 39809640, 326721800, 0, 0, 256814891280, 2636337861200, 0, 0, 3799455942515488, 46845158056515936, 0, 0, 111683611098764903232, 1607383260609382393152, 0, 0

Offset: 1

Author

John E. Miller ([e-mail]), Eric W. Weisstein, N. J. A. Sloane

Keywords

• nonn
• hard
• nice
• more

Comments

These are also called Langford pairings.

2*a(n) = A176127(n) gives the number of ways of arranging the numbers 1,1,2,2,...,n,n so that there is one number between the two 1's, two numbers between the two 2's, ..., n numbers between the two n's.

a(n) > 0 iff n == 0 or 3 (mod 4).

Examples

			Solutions for n=3 and 4: 312132 and 41312432.
Solution for n=16: 16, 14, 12, 10, 13, 5, 6, 4, 15, 11, 9, 5, 4, 6, 10, 12, 14, 16, 13, 8, 9, 11, 7, 1, 15, 1, 2, 3, 8, 2, 7, 3.
		

References

• Jaromir Abrham, "Exponential lower bounds for the numbers of Skolem and extremal Langford sequences," Ars Combinatoria 22 (1986), 187-198.
• M. Gardner, Mathematical Magic Show, New York: Vintage, pp. 70 and 77-78, 1978.
• M. Gardner, Mathematical Magic Show, Revised edition published by Math. Assoc. Amer. in 1989. Contains a postscript on pp. 283-284 devoted to a discussion of early computations of the number of Langford sequences.
• R. K. Guy, The unity of combinatorics, Proc. 25th Iranian Math. Conf, Tehran, (1994), Math. Appl 329 129-159, Kluwer Dordrecht 1995, Math. Rev. 96k:05001.
• D. E. Knuth, The Art of Computer Programming, Vol. 4A, Section 7.1.1, p. 2.
• M. Krajecki, Christophe Jaillet and Alain Bui, "Parallel tree search for combinatorial problems: A comparative study between OpenMP and MPI," Studia Informatica Universalis 4 (2005), 151-190.
• Roselle, David P. Distributions of integers into s-tuples with given differences. Proceedings of the Manitoba Conference on Numerical Mathematics (Univ. Manitoba, Winnipeg, Man., 1971), pp. 31--42. Dept. Comput. Sci., Univ. Manitoba, Winnipeg, Man., 1971. MR0335429 (49 #211). - From N. J. A. Sloane, Jun 05 2012

Links

• Ali Assarpour, Amotz Bar-Noy, and Ou Liuo, Counting the Number of Langford Skolem Pairings, arXiv:1507.00315 [cs.DM], 2015.
• Gheorghe Coserea, Solutions for n=7.
• Gheorghe Coserea, Solutions for n=8.
• Gheorghe Coserea, MiniZinc model for generating solutions.
• R. O. Davies, On Langford's problem II, Math. Gaz., 1959, vol. 43, 253-255.
• Elin Farnell, Puzzle Pedagogy: A Use of Riddles in Mathematics Education, PRIMUS, July 2016, pp. 202-211.
• M. Krajecki, L(2,23)=3,799,455,942,515,488.
• C. D. Langford, 2781. Parallelograms with Integral Sides and Diagonals, Math. Gaz., 1958, vol. 42, p. 228.
• J. E. Miller, Langford's Problem
• G. Nordh, Perfect Skolem sequences, arXiv:math/0506155 [math.CO], 2005.
• Zan Pan, Conjectures on the number of Langford sequences, (2021).
• Michael Penn, Why is this list "nice"? -- Langford's Problem, YouTube video, 2022.
• C. J. Priday, On Langford's Problem I, Math. Gaz., 1959, vol. 43, 250-255.
• W. Schneider, Langford's Problem
• T. Skolem, On certain distributions of integers in pairs with given differences, Math. Scand., 1957, vol. 5, 57-68.
• T. Saito and S. Hayasaka, Langford sequences: a progress report, Math. Gaz., 1979, vol. 63, #426, 261-262.
• J. E. Simpson, Langford Sequences: perfect and hooked, Discrete Math., 1983, vol. 44, #1, 97-104.
• Eric Weisstein's World of Mathematics, Langford's Problem.

Crossrefs

See A050998 for further examples of solutions.

If the zeros are omitted we get A192289.

Cf. A059106, A059107, A059108, A125762, A026272.

Formula

a(n) = A176127(n)/2.

Extensions

a(20) from Ron van Bruchem and Mike Godfrey, Feb 18 2002

a(21)-a(23) sent by John E. Miller ([e-mail]) and Pab Ter (pabrlos(AT)yahoo.com), May 26 2004. These values were found by a team at Université de Reims Champagne-Ardenne, headed by Michael Krajecki, using over 50 processors for 4 days.

a(24)=46845158056515936 was computed circa Apr 15 2005 by the Krajecki team. - Don Knuth, Feb 03 2007

Edited by Max Alekseyev, May 31 2011

a(27) from the J. E. Miller web page "Langford's problem"; thanks to Eric Desbiaux for reporting this. - N. J. A. Sloane, May 18 2015. However, it appears that the value was wrong. - N. J. A. Sloane, Feb 22 2016

Corrected and extended using results from the Assarpour et al. (2015) paper by N. J. A. Sloane, Feb 22 2016 at the suggestion of William Rex Marshall.