A176127 -id:A176127 - 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.

A026272 a(n) = smallest k such that k=a(n-k-1) is the only appearance of k so far; if there is no such k, then a(n) = least positive integer that has not yet appeared.

Original entry on oeis.org

1, 2, 1, 3, 2, 4, 5, 3, 6, 7, 4, 8, 5, 9, 10, 6, 11, 7, 12, 13, 8, 14, 15, 9, 16, 10, 17, 18, 11, 19, 20, 12, 21, 13, 22, 23, 14, 24, 15, 25, 26, 16, 27, 28, 17, 29, 18, 30, 31, 19, 32, 20, 33, 34, 21, 35, 36, 22, 37, 23, 38, 39, 24, 40, 41, 25

Offset: 1

Clark Kimberling

From Daniel Joyce, Apr 13 2001: (Start)
This sequence displays every positive integer exactly twice and the gap between the two occurrences of n contains exactly n other values. The first occurrence of n precedes the first occurrence of n+1.
Also related to the Wythoff array (A035513) and the Para-Fibonacci sequence (A035513) where every positive integer is displayed exactly once in the whole array. Take any integer n in A026272 and let C = number of terms from the beginning of the sequence to the second occurrence of n. Then C = (2nd term after n in the applicable sequence for n in A035513).
Also in the second occurrence of n in A026272, let N=n ( - one term) = (first term value after n in the applicable sequence for n in A035513). In this format the second occurrence of n in A026272 will produce in A035513, n itself and two of the succeeding terms of n in the Wythoff array where every positive integer can only be displayed once.
In A026272 if |a(n)-a(n+1)| > 10 then phi ~ a(n)/|a(n)-a(n+1)|. When n -> infinity it will converge to phi. (End)
Or, put a copy of n in A000027 n places further along! - Zak Seidov, May 24 2008
Another version would prefix this sequence with two leading 0's (see the Angelini reference). If we use this form and write down the indices of the two 0's, the two 1's, the two 2's, the two 3's, etc., then we get A072061. - Jacques ALARDET, Jul 26 2008

Eric Angelini, "Jeux de suites", in Dossier Pour La Science, pp. 32-35, Volume 59 (Jeux math'), April/June 2008, Paris.

Zak Seidov, Table of n, a(n) for n = 1..1000
Jon Asier Bárcena-Petisco, Luis Martínez, María Merino, Juan Manuel Montoya, and Antonio Vera-López, Fibonacci-like partitions and their associated piecewise-defined permutations, arXiv:2503.19696 [math.CO], 2025. See p. 3.
Jeffrey Shallit, The Hurt-Sada Array and Zeckendorf Representations, arXiv:2501.08823 [math.NT], 2025. See p. 10.

Cf. A000027, A035513, A014552, A176127.

s=Range[1000];n=0;Do[n++;s=Insert[s,n,Position[s,n][[1]]+n+1],{500}];A026272=Take[s,1000] (* Zak Seidov, May 24 2008 *)

A026272=apply(t->t-1,A026242[3..-1]) \\ Use vecextract(A026242,"3..") in PARI versions < 2.7. - M. F. Hasler, Sep 17 2014

from collections import Counter
from itertools import count, islice
def agen(): # generator of terms
    aset, alst, k, mink, counts = set(), [0], 0, 1, Counter()
    for n in count(1):
        for k in range(1, len(alst)-1):
            if k == alst[n-k-1] and counts[alst[n-k-1]] == 1: an = k; break
        else: an = mink
        yield an; aset.add(an); alst.append(an); counts.update([an])
        while mink in aset: mink += 1
print(list(islice(agen(), 66))) # Michael S. Branicky, Jun 27 2022

a(n) = A026242(n+2) - 1 = A026350(n+3) - 2 = A026354(n+4) - 3.

Edited by Max Alekseyev, May 31 2011

A004075 Number of Skolem sequences of order n.

Original entry on oeis.org

1, 0, 0, 6, 10, 0, 0, 504, 2656, 0, 0, 455936, 3040560, 0, 0, 1400156768, 12248982496, 0, 0, 11435578798976, 123564928167168, 0, 0, 204776117691241344, 2634563519776965376, 0, 0, 7064747252076429464064, 105435171495207196553472, 0, 0

Offset: 1

N. J. A. Sloane

Number of permutations of the multiset {1,1,2,2,...,n,n} such that the distance between the elements i equals i for every i=1,2,...,n.

Number of super perfect rhythmic tilings of [0,2n-1] with pairs. See A285698 and A285527 for the definition and tilings of triples and quadruples. - Tony Reix, Apr 25 2017

CRC Handbook of Combinatorial Designs, 1996, p. 460.

Ali Assarpour, Amotz Bar-Noy, Ou Liuo, Counting the Number of Langford Skolem Pairings, arXiv:1507.00315 [cs.DM], 2015.
S. Burrill and L. Yen, Constructing Skolem sequences via generating trees, arXiv preprint arXiv:1301.6424 [math.CO], 2013.
J. E. Miller, Langford's Problem
G. Nordh, Perfect Skolem sequences, arXiv:math/0506155 [math.CO], 2005.

Cf. A014552, A059106, A176127, A268537.

(* Program not suitable to compute a large number of terms. *)
iter[n_] := Sequence @@ Table[{x[i], {-1, 1}}, {i, 1, 2n}];
a[n_] := 1/2^(2n) Sum[Product[x[i], {i, 1, 2n}] Product[Sum[x[k] x[k+i], {k, 1, 2n-i}], {i, 1, n}], iter[n] // Evaluate];
Table[Print[a[n]]; a[n], {n, 1, 10}] (* Jean-François Alcover, Sep 29 2018, from formula in Assarpour et al. *)

For n > 1, a(n) = A059106(n)*2 because A059106 ignores reflected solutions. - Martin Fuller, Mar 08 2007

More terms (via A059106) from Martin Fuller, Mar 08 2007
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

A264813 Number of permutations of 3 indistinguishable copies of 1,...,n such that the first and second copies of j are adjacent and there are exactly j numbers between the second and the third copy of j.

Original entry on oeis.org

1, 0, 1, 1, 0, 3, 6, 0, 53, 199, 0, 2908, 13699, 0, 369985, 2135430, 0, 87265700, 611286653, 0

Offset: 0

Alois P. Heinz, Nov 25 2015

a(n) = 0 for n == 1 (mod 3).

			a(0) = 1: the empty permutation.
a(2) = 1: 221121.
a(3) = 1: 223321131.
a(5) = 3: 223325534411514, 225523344531141, 552244253341131.
a(6) = 6: 221121665544336543, 225523366534411614, 225526633544361141, 446611415563322532, 552266253344631141, 665544336543221121.

Eric Weisstein's World of Mathematics, Langford's Problem
Wikipedia, Dancing Links
Wikipedia, Langford pairing

Cf. A014552, A104185, A108235, A176127, A203435, A261516, A261517, A321956.

A268536 The number of permutations of {1,2,...,n,1,2,...,n} with the property that there are k numbers between the two k's in the set for k=1,...,n, as n runs through the positive integers congruent to -1 or 0 mod 4.

Original entry on oeis.org

2, 2, 52, 300, 35584, 216288, 79619280, 653443600, 513629782560, 5272675722400, 7598911885030976, 93690316113031872, 223367222197529806464, 3214766521218764786304

Offset: 1

N. J. A. Sloane, Feb 22 2016

nonn

Ali Assarpour, Amotz Bar-Noy, Ou Liuo, Counting the Number of Langford Skolem Pairings, arXiv:1507.00315 [cs.DM], 2015.

This is A176127 without the zeros.

A322179 The number of permutations of {1,2,...,n,1,2,...,n} with the property that there are k or more numbers between the two k's in the set for k=1,...,n.

Original entry on oeis.org

1, 0, 0, 2, 40, 1070, 38936, 1896220, 119912476, 9587033840

Offset: 0

Seiichi Manyama, Nov 30 2018

			In case of n = 3.
  | permutation
--+-------------------
1 | [2, 3, 1, 2, 1, 3]
2 | [3, 1, 2, 1, 3, 2]

Cf. A176127, A322180.

a(9) from Alois P. Heinz, Nov 30 2018

A322180 The number of permutations of {1,2,...,n,1,2,...,n} with the property that there are k or fewer numbers between the two k's in the set for k=1,...,n.

Original entry on oeis.org

1, 1, 5, 36, 466, 8942, 240366, 8576860, 392952468, 22470271108

Offset: 0

Seiichi Manyama, Nov 30 2018

			In case of n = 2.
  | permutation
--+-------------
1 | [1, 1, 2, 2]
2 | [1, 2, 1, 2]
3 | [2, 1, 1, 2]
4 | [2, 1, 2, 1]
5 | [2, 2, 1, 1]

Cf. A176127, A322179.

a(9) from Alois P. Heinz, Nov 30 2018

A381759 Number of words of length 2n+1 with one 0 entry and two entries of each of 1..n so that there are exactly k numbers between two equal k's and so that the first element does not exceed the last.

Original entry on oeis.org

1, 1, 3, 5, 11, 38, 182, 938, 4158, 23384, 160104, 1063772, 6987380, 53746000, 479965824, 4182552416, 35963592624, 351432650816, 3860219984448, 41614300175968

Offset: 1

Zhao Hui Du, Mar 06 2025

			a(4) = 5 since there are 5 different solutions: 131423024, 141302432, 240231413, 023421314, 041312432.

Chinese BBS for the problem

Cf. A014552, A176127, A381760.

a(n) = A381760(n) + A176127(n).

A381760 Number of words of length 2n+1 with one 0 entry and two entries of each of 1..n so that there are exactly k numbers between two equal k's and so that the first element is not 0 and also does not exceed the last.

Original entry on oeis.org

1, 1, 1, 3, 11, 38, 130, 638, 4158, 23384, 124520, 847484, 6987380, 53746000, 400346544, 3529108816, 35963592624, 351432650816, 3346590201888, 36341624453568

Offset: 1

Zhao Hui Du, Mar 06 2025

			For n=4, there are 3 different ways {131423024, 141302432, 240231413} so that a(4)=3 and both 023421314 and 041312432 are invalid since 0 in boundary.

Chinese BBS for the problem

Cf. A014552, A176127, A381759.

a(n) = A381759(n) - A176127(n).

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

A026272 a(n) = smallest k such that k=a(n-k-1) is the only appearance of k so far; if there is no such k, then a(n) = least positive integer that has not yet appeared.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

Extensions

A004075 Number of Skolem sequences of order n.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A264813 Number of permutations of 3 indistinguishable copies of 1,...,n such that the first and second copies of j are adjacent and there are exactly j numbers between the second and the third copy of j.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A268536 The number of permutations of {1,2,...,n,1,2,...,n} with the property that there are k numbers between the two k's in the set for k=1,...,n, as n runs through the positive integers congruent to -1 or 0 mod 4.

Views

Author

Keywords

Links

Crossrefs

A322179 The number of permutations of {1,2,...,n,1,2,...,n} with the property that there are k or more numbers between the two k's in the set for k=1,...,n.

Views

Author

Keywords

Examples

Crossrefs

Extensions

A322180 The number of permutations of {1,2,...,n,1,2,...,n} with the property that there are k or fewer numbers between the two k's in the set for k=1,...,n.

Views

Author

Keywords

Examples

Crossrefs

Extensions

A381759 Number of words of length 2n+1 with one 0 entry and two entries of each of 1..n so that there are exactly k numbers between two equal k's and so that the first element does not exceed the last.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A381760 Number of words of length 2n+1 with one 0 entry and two entries of each of 1..n so that there are exactly k numbers between two equal k's and so that the first element is not 0 and also does not exceed the last.

Views

Author

Keywords

Examples

Links