|
| |
|
|
A014552
|
|
Number of solutions to Langford (or Langford-Skolem) problem (up to reversal of the order).
|
|
19
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,7
|
|
|
COMMENTS
|
These are also called Langford pairings.
2*a(n)=A176127(n) gives the number of ways are 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).
|
|
|
REFERENCES
|
Jaromir Abrham, "Exponential lower bounds for the numbers of Skolem and extremal Langford sequences," Ars Combinatoria 22 (1986), 187-198.
Elin Farnell, Puzzle Pedagogy: A Use of Riddles in Mathematics Education, PRIMUS, July 2016, pp. 202-211; http://dx.doi.org/10.1080/10511970.2016.1195465
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
|
Table of n, a(n) for n=1..30.
Ali Assarpour, Amotz Bar-Noy, 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.
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.
|
|
|
FORMULA
|
a(n) = A176127(n)/2.
|
|
|
EXAMPLE
|
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.
|
|
|
CROSSREFS
|
See A050998 for further examples of solutions.
If the zeros are omitted we get A192289.
Cf. A059106, A059107, A059108, A125762, A026272.
Sequence in context: A238917 A200449 A248465 * A192289 A230906 A232585
Adjacent sequences: A014549 A014550 A014551 * A014553 A014554 A014555
|
|
|
KEYWORD
|
nonn,hard,nice,more
|
|
|
AUTHOR
|
John E. Miller (john@timehaven.us), Eric W. Weisstein, N. J. A. Sloane
|
|
|
EXTENSIONS
|
a(20) from Ron van Bruchem and Mike Godfrey, Feb 18 2002
a(21)-a(23) sent by John E. Miller (john@timehaven.us) and Pab Ter (pabrlos(AT)yahoo.com), May 26 2004. These values were found by a team at Universite 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.
|
|
|
STATUS
|
approved
|
| |
|
|
