A059108 -id:A059108 - cp's OEIS frontend

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

John E. Miller (john@timehaven.us), Eric W. Weisstein, N. J. A. Sloane

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

			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.

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

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.

See A050998 for further examples of solutions.
If the zeros are omitted we get A192289.
Cf. A059106, A059107, A059108, A125762, A026272.

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

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

A059106 Number of solutions to Nickerson variant of Langford (or Langford-Skolem) problem.

Original entry on oeis.org

1, 0, 0, 3, 5, 0, 0, 252, 1328, 0, 0, 227968, 1520280, 0, 0, 700078384, 6124491248, 0, 0, 5717789399488, 61782464083584, 0, 0, 102388058845620672, 1317281759888482688, 0, 0, 3532373626038214732032, 52717585747603598276736, 0, 0

Offset: 1

N. J. A. Sloane, Feb 14 2001

How many ways are of arranging the numbers 1,1,2,2,3,3,...,n,n so that there are zero numbers between the two 1's, one number between the two 2's, ..., n-1 numbers between the two n's?
For n > 1, a(n) = A004075(n)/2 because A004075 also counts reflected solutions. - Martin Fuller, Mar 08 2007
Because of symmetry, is a(5) = 5 the largest prime in this sequence? - Jonathan Vos Post, Apr 02 2011

			For n=4 the a(4)=3 solutions, up to reversal of the order, are:
1 1 3 4 2 3 2 4
1 1 4 2 3 2 4 3
2 3 2 4 3 1 1 4
From _Gheorghe Coserea_, Aug 26 2017: (Start)
For n=5 the a(5)=5 solutions, up to reversal of the order, are:
1 1 3 4 5 3 2 4 2 5
1 1 5 2 4 2 3 5 4 3
2 3 2 5 3 4 1 1 5 4
2 4 2 3 5 4 3 1 1 5
3 5 2 3 2 4 5 1 1 4
(End)

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=8.
Gheorghe Coserea, Solutions for n=9.
J. E. Miller, Langford's Problem
R. S. Nickerson and D. C. B. Marsh, E1845: A variant of Langford's Problem, American Math. Monthly, 1967, 74, 591-595.
Zan Pan, Conjectures on the number of Langford sequences, (2021).

Cf. A014552, A050998, A059107, A059108.

Cf. A004075, A268535.

a(20)-a(23) from Mike Godfrey (m.godfrey(AT)umist.ac.uk), Mar 14 2002
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
a(28)-a(31) from Assarpour et al. (2015), added by Max Alekseyev, Sep 24 2023

A285527 Number of super perfect rhythmic tilings of [0,3n-1] with triples.

Original entry on oeis.org

1, 1, 0, 0, 0, 0, 0, 0, 0, 18, 40, 66, 0, 0, 0, 0, 0, 0, 400686, 1738012, 8495580, 0, 0, 0, 0, 0, 0

Offset: 0

Tony Reix, Apr 20 2017

A super perfect tiling of the line with triples consists of n groups of three evenly spaced points, each group having a different common interval such that all points of the line are covered, and such that all intervals are inferior or equal to n (thus, each interval belongs to [1..n]).

			For n = 9, there are 18 tilings.
One is: (0,2,4), (1,5,9), (3,11,19), (6,12,18), (7,14,21), (8,17,26), (10,13,16), (15,20,25), (22,23,24), with the intervals: 1,2,3,4,5,6,7,8,9 appearing in order: 2,4,8,6,7,9,3,5,1.
It can also be represented as:
2 4 2 8 2 4 6 7 9 4 3 8 6 3 7 5 3 9 6 8 5 7 1 1 1 5 9

Cf. A261516, A320392.

For n>1, a(n) = A059108(n)*2 because A059108 ignores reflected solutions. - Fausto A. C. Cariboni, May 20 2017

A332748 The number of permutations of {1,1,1,2,2,2,...,n,n,n} such that each triple of k's (k=1..n) is equally spaced with b(k) other elements in between and b(1) >= b(2) >= ... >= b(n).

Original entry on oeis.org

1, 1, 4, 18, 124, 738, 7464, 55890, 668778, 7030210, 90713844, 1054221258, 18597735744, 242795838520

Offset: 0

Seiichi Manyama, Feb 21 2020

			n = 1 case:
     |           | b(1)
-----+-----------+------
   1 | [1, 1, 1] | [0] *
.
n = 2 case:
     |                    | b(1),b(2)
-----+--------------------+----------
   1 | [2, 2, 2, 1, 1, 1] | [0, 0]
   2 | [2, 1, 2, 1, 2, 1] | [1, 1]
   3 | [1, 2, 1, 2, 1, 2] | [1, 1]
   4 | [1, 1, 1, 2, 2, 2] | [0, 0]
.
n = 3 case:
     |                             | b(1),b(2),b(3)
-----+-----------------------------+---------------
   1 | [3, 3, 3, 2, 2, 2, 1, 1, 1] | [0, 0, 0]
   2 | [3, 3, 3, 2, 1, 2, 1, 2, 1] | [1, 1, 0]
   3 | [3, 3, 3, 1, 2, 1, 2, 1, 2] | [1, 1, 0]
   4 | [3, 3, 3, 1, 1, 1, 2, 2, 2] | [0, 0, 0]
   5 | [3, 2, 1, 3, 2, 1, 3, 2, 1] | [2, 2, 2]
   6 | [3, 1, 2, 3, 1, 2, 3, 1, 2] | [2, 2, 2]
   7 | [1, 3, 3, 3, 1, 2, 2, 2, 1] | [3, 0, 0]
   8 | [2, 3, 1, 2, 3, 1, 2, 3, 1] | [2, 2, 2]
   9 | [1, 3, 2, 1, 3, 2, 1, 3, 2] | [2, 2, 2]
  10 | [2, 1, 3, 2, 1, 3, 2, 1, 3] | [2, 2, 2]
  11 | [1, 2, 3, 1, 2, 3, 1, 2, 3] | [2, 2, 2]
  12 | [2, 2, 2, 3, 3, 3, 1, 1, 1] | [0, 0, 0]
  13 | [1, 1, 1, 3, 3, 3, 2, 2, 2] | [0, 0, 0]
  14 | [1, 2, 2, 2, 1, 3, 3, 3, 1] | [3, 0, 0]
  15 | [2, 2, 2, 1, 1, 1, 3, 3, 3] | [0, 0, 0]
  16 | [2, 1, 2, 1, 2, 1, 3, 3, 3] | [1, 1, 0]
  17 | [1, 2, 1, 2, 1, 2, 3, 3, 3] | [1, 1, 0]
  18 | [1, 1, 1, 2, 2, 2, 3, 3, 3] | [0, 0, 0]
* (strongly decreasing)

Column k=3 of A332762.

Cf. A104429, A059108, A261516 (strongly decreasing), A322178, A332752.

a(10)-a(13) from Max Alekseyev, Sep 26 2023

A059107 Number of solutions to triples version of Langford (or Langford-Skolem) problem.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 3, 5, 0, 0, 0, 0, 0, 0, 13440, 54947, 249280, 0, 0, 0, 0, 0, 0

Offset: 1

N. J. A. Sloane, Feb 14 2001

How many ways are there of arranging the numbers 1,1,1,2,2,2,3,3,3, ...,n,n,n so that there is one number between the first and second 1's and one number between the second and third 1's; two numbers between the first and second 2's and two numbers between the second and third 2's; ... n numbers between the first and second n's and n numbers between the second and third n's?

a(n)=0 for n mod 9 not in {-1,0,1}. - Gheorghe Coserea, Aug 23 2017

			For n=9 the a(9)=3 solutions, up to reversal of the order, are:
1 8 1 9 1 5 2 6 7 2 8 5 2 9 6 4 7 5 3 8 4 6 3 9 7 4 3
1 9 1 2 1 8 2 4 6 2 7 9 4 5 8 6 3 4 7 5 3 9 6 8 3 5 7
1 9 1 6 1 8 2 5 7 2 6 9 2 5 8 4 7 6 3 5 4 9 3 8 7 4 3
From _Gheorghe Coserea_, Aug 26 2017: (Start)
For n=10 the a(10)=5 solutions, up to reversal of the order, are:
1 3 1 10 1 3 4 9 6 3 8 4 5 7 10 6 4 9 5 8 2 7 6 2 5 10 2 9 8 7
1 10 1 2 1 4 2 9 7 2 4 8 10 5 6 4 7 9 3 5 8 6 3 10 7 5 3 9 6 8
1 10 1 6 1 7 9 3 5 8 6 3 10 7 5 3 9 6 8 4 5 7 2 10 4 2 9 8 2 4
4 10 1 7 1 4 1 8 9 3 4 7 10 3 5 6 8 3 9 7 5 2 6 10 2 8 5 2 9 6
5 2 7 9 2 10 5 2 6 4 7 8 5 9 4 6 10 3 7 4 8 3 6 9 1 3 1 10 1 8
(End)

F. S. Gillespie and W. R. Utz, A generalized Langford Problem, Fibonacci Quart., 1966, v4, 184-186.
J. E. Miller, Langford's Problem

Cf. A014552, A050998, A059106, A059108.

A334250 Number of set partitions of [3n] into 3-element subsets {i, i+k, i+2k} with 1<=k<=n.

Original entry on oeis.org

1, 1, 2, 4, 12, 35, 129, 567, 2920, 16110, 103467, 717608, 5748214, 47937957, 441139750, 4319093093, 45963368076, 510202534002, 6150655137844, 76789781005325, 1028853084775725, 14294680087131380

Offset: 0

Alois P. Heinz, Apr 20 2020

Differs from A331621 first at n=7.

			a(2) = 2: 123|456, 135|246.
a(3) = 4: 123|456|789, 123|468|579, 135|246|789, 147|258|369.

Wikipedia, Partition of a set

Cf. A014307 (the same for 2-element subsets), A025035, A059108, A104429 (where k is not restricted), A285527, A331621, A337520.

Main diagonal of A360334.

b:= proc(s, t) option remember; `if`(s={}, 1, (m-> add(
     `if`({m-j, m-2*j} minus s={}, b(s minus {m, m-j, m-2*j},
            t), 0), j=1..min(t, iquo(m-1, 2))))(max(s)))
    end:
a:= proc(n) option remember; forget(b): b({$1..3*n}, n) end:
seq(a(n), n=0..12);

b[s_List, t_] := b[s, t] = If[s == {}, 1, Function[m, Sum[If[{m - j, m - 2j} ~Complement~ s == {}, b[s ~Complement~ {m, m - j, m - 2j}, t], 0], {j, 1, Min[t, Quotient[m - 1, 2]]}]][Max[s]]];
a[n_] := a[n] = b[Range[3n], n];
Table[Print[n, " ", a[n]]; a[n], {n, 0, 12}] (* Jean-François Alcover, May 10 2020, after Maple *)

a(n) <= A104429(n) <= A025035(n).

a(17)-a(21) from Martin Fuller, Jul 19 2025

A284757 Number of solutions to Nickerson variant of quadruples version of Langford (or Langford-Skolem) problem.

Original entry on oeis.org

1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 10, 55, 0, 0, 0, 0, 0, 0

Offset: 1

Fausto A. C. Cariboni, Apr 02 2017

How many ways are of arranging the numbers 1,1,1,1,2,2,2,2,3,3,3,3,...,n,n,n,n so that there are zero numbers between the first and second 1's, between the second and third 1's and between the third and fourth 1's; one number between the first and second 2's, between the second and third 2's and between the third and fourth 2's; ... n-1 numbers between the first and second n's, between the second and third n's and between the third and fourth n's?
An equivalent definition is A261517 with added condition that all different common intervals are <= n.
a(n) ignores reflected solutions.

Fausto A. C. Cariboni, Solutions for a(24)-a(25)
J. E. Miller, Langford's Problem.

Cf. A014552, A059106, A059108, A261517.

a(n) = 0 if (n mod 8) not in {0, 1}. - Max Alekseyev, Sep 28 2023

a(28)-a(31) from Max Alekseyev, Sep 24 2023

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

Extensions

A059106 Number of solutions to Nickerson variant of Langford (or Langford-Skolem) problem.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A285527 Number of super perfect rhythmic tilings of [0,3n-1] with triples.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A332748 The number of permutations of {1,1,1,2,2,2,...,n,n,n} such that each triple of k's (k=1..n) is equally spaced with b(k) other elements in between and b(1) >= b(2) >= ... >= b(n).

Views

Author

Keywords

Examples

Crossrefs

Extensions

A059107 Number of solutions to triples version of Langford (or Langford-Skolem) problem.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A334250 Number of set partitions of [3n] into 3-element subsets {i, i+k, i+2k} with 1<=k<=n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A284757 Number of solutions to Nickerson variant of quadruples version of Langford (or Langford-Skolem) problem.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions