|
|
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 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.
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
|
|
|
FORMULA
|
|
|
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.
|
|
KEYWORD
|
nonn,hard,nice,more
|
|
AUTHOR
|
|
|
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 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
|
|
STATUS
|
approved
|
|
|
|