login
Inequivalent solutions to Langford (or Langford-Skolem) problem of arranging the numbers 1,1,2,2,3,3,...,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, listed by length and lexicographic order.
5

%I #40 Aug 26 2017 14:57:55

%S 231213,23421314,14156742352637,14167345236275,15146735423627,

%T 15163745326427,15167245236473,15173465324726,16135743625427,

%U 16172452634753,17125623475364,17126425374635,23627345161475

%N Inequivalent solutions to Langford (or Langford-Skolem) problem of arranging the numbers 1,1,2,2,3,3,...,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, listed by length and lexicographic order.

%C Entries are indexed by numbers n == -1 or 0 mod 4 (A014601).

%C More precisely, for each given n = (3, 4, 7, 8, ...) in A014601, all of the A014552(n) inequivalent solutions are listed in lexicographic order. For example, a(1), a(2) and a(3) correspond to n=3, 4 and 7, but a(4) is not the first solution for n=8 but the second solution for n=7. - _M. F. Hasler_, Nov 12 2015

%C "Inequivalent" means that for two solutions related by symmetry (reading the digits backwards), only the (lexicographic) smaller one is listed. - _M. F. Hasler_, Nov 15 2015

%C It is unclear how the sequence goes on after the first 1+1+26+150 terms, with the solutions for n >= 11. Will a solution s=(s[1],...,s[n]) be coded again by Sum_{i=1..n} s[i]*b^(n-i) in base b=10, or in some larger base b >= n+1? Maybe using as many decimal digits as needed, i.e., b=100 for 11 <= n <= 99? - _M. F. Hasler_, Nov 16 2015

%D M. Gardner, Mathematical Magic Show, New York: Vintage, pp. 70 and 77-78, 1978.

%H Seiichi Manyama, <a href="/A050998/b050998.txt">Table of n, a(n) for n = 1..178</a>

%H R. K. Guy, <a href="http://dx.doi.org/10.1007/978-1-4613-3554-2_9">The unity of combinatorics</a>, Proc. 25th Iranian Math. Conf, Tehran, (1994), Math. Appl 329 129-159, Kluwer Dordrecht 1995, Math. Rev. 96k:05001.

%H C. D. Langford, <a href="http://www.jstor.org/stable/3610395">Problem</a>, Math. Gaz., 1958, vol. 42, p. 228.

%H J. Miller, <a href="http://dialectrix.com/langford.html">Langford's problem.</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/LangfordsProblem.html">Langford's Problem.</a>

%e The first n which allows a solution (A014552(n) > 0; n in A014601) is n=3, the solutions are a(1) = 231213 and the same read backwards, 312132.

%e The next solutions are given for n=4, again there is only A014552(4)=1 solution a(2) = 23421314 up to reversal (41312432, not listed).

%e Then follow the A014552(7)=26 (inequivalent) solutions for n=7, viz. a(3)-a(28).

%Y See A014552 (the main entry for this problem) for number of solutions.

%K nonn,nice,easy

%O 1,1

%A _Eric W. Weisstein_

%E Definition clarified by _M. F. Hasler_, Nov 15 2015