A050998 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.

231213, 23421314, 14156742352637, 14167345236275, 15146735423627, 15163745326427, 15167245236473, 15173465324726, 16135743625427, 16172452634753, 17125623475364, 17126425374635, 23627345161475

Offset: 1

Author

Eric W. Weisstein

Keywords

• nonn
• nice
• easy

Comments

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

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

"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

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

Examples

			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.
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).
Then follow the A014552(7)=26 (inequivalent) solutions for n=7, viz. a(3)-a(28).
		

References

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

Links

• Seiichi Manyama, Table of n, a(n) for n = 1..178
• 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.
• C. D. Langford, Problem, Math. Gaz., 1958, vol. 42, p. 228.
• J. Miller, Langford's problem.
• Eric Weisstein's World of Mathematics, Langford's Problem.

Crossrefs

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

Extensions

Definition clarified by M. F. Hasler, Nov 15 2015