A004075 -id:A004075 - cp's OEIS frontend

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

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

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

Original entry on oeis.org

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

Offset: 1

Andrew McFarland, Apr 09 2010

			a(1)=0; a(2)=0; a(3)=a(4)=2 since {{2,3,1,2,1,3},{3,1,2,1,3,2}} and {{4,1,3,1,2,4,3,2},{2,3,4,2,1,3,1,4}} are the only ways to permute {1,2,3,1,2,3} and {1,2,3,4,1,2,3,4}, respectively, such that there is one number between the 1's, two numbers between the 2's,..., n numbers between the n's.

For references, see A014552.

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

Cf. A014552, A059106, A004075, A264813, A268536.

a=lambda n:sum(1 for i in DLXCPP([(i-1,j+n,i+j+n+1)for i in[1..n]for j in[0..n+n-i-2]]+[(i,)for i in[n..n+n-1]]))if n%4 in[0,3] else 0
# Tomas Boothby, Jun 14 2013

a(n) = 2 * A014552(n).

Edited and more terms added from A014552 by Max Alekseyev, May 31 2011, May 19 2015

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.

A275801 Number of alternating permutations of the multiset {1,1,2,2,...,n,n}.

Original entry on oeis.org

1, 0, 1, 4, 53, 936, 25325, 933980, 45504649, 2824517520, 217690037497, 20394614883316, 2282650939846781, 300814135522967736, 46103574973075123877, 8130996533576437261772, 1635028654501420083152785, 371853339350614571322913824, 94969025880924845123887493233

Offset: 0

Max Alekseyev, Aug 09 2016

nonn

Number of permutations (p(1),...,p(2n)) of {1,1,2,2,...,n,n} satisfying p(1) < p(2) > p(3) < ... < p(2n).

a(n) <= A005799(n) <= A275829(n).

Max Alekseyev, Table of n, a(n) for n = 0..70
Wikipedia, Alternating permutation.
hkju et al., Number of updown sequences of 1,1,2,2,...,n,n, Mathoverflow, 2016.

Column k=2 of A275784.

Cf. A000111, A001250, A000459, A004075, A005799, A114938, A137729, A137730, A137737, A137749, A275829.

A202951 Number of Nickerson-type partitions of [1,...,3n] into triples satisfying x+y=z.

Original entry on oeis.org

1, 1, 0, 0, 6, 10, 0, 0, 700

Offset: 0

N. J. A. Sloane, Dec 26 2011

Perhaps an incorrect version of A004075? Sequence values are from p. 51 of Nowakowski. - Martin Fuller, Jul 06 2025

R. S. Nickerson, Problem E1845, Amer. Math. Monthly, p. 81, 73 (1966).
R. S. Nickerson and D. C. B. Marsh, E1845: A variant of Langford's Problem, American Math. Monthly, 1967, 74, 591-595.
R. J. Nowakowski, Generalizations of the Langford-Skolem problem, M.S. Thesis, Dept. Math., Univ. Calgary, May 1975. [Scanned copy, with permission.]

Cf. A108235, A202952.

A275829 Number of weakly alternating permutations of the multiset {1,1,2,2,...,n,n}.

Original entry on oeis.org

1, 1, 2, 12, 140, 2564, 68728, 2539632, 123686800, 7677924688, 591741636128, 55438330474944, 6204888219697856, 817697605612952384, 125322509904814743424, 22102340129003429880576, 4444468680409243484516608, 1010802175212828388101900544, 258152577318424951261637001728

Offset: 0

Max Alekseyev, Aug 11 2016

nonn

Number of permutations (p(1),...,p(2n)) of {1,1,2,2,...,n,n} satisfying p(1) <= p(2) >= p(3) <= p(4) >= p(5) <= ... <= p(2n).

a(n) >= A005799(n) >= A275801(n).

Max Alekseyev, Table of n, a(n) for n = 0..70

Cf. A000111, A001250, A000459, A004075, A005799, A114938, A137729, A137730, A137737, A137749, A275801.

A268537 Number of Skolem sequences of order n, as n runs through the positive integers congruent to 0 and 1 mod 4.

Original entry on oeis.org

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

Offset: 1

N. J. A. Sloane, Feb 22 2016

nonn

Ali Assarpour, Amotz Bar-Noy, and Ou Liuo, Counting the Number of Langford Skolem Pairings, arXiv:1507.00315 [cs.DM], 2015.
James Bubear, Joanne Hall, Kevin Hendrey, and Tim Wilson, Skolem Circles, arXiv:1602.08879 [math.CO], 2016.

This is A004075 without the zeros.

Cf. A042948.

a(n) = A004075(2*n - (n mod 2)) = A004075(A042948(n)).

a(14)-a(15) from A004075 added by Max Alekseyev, Sep 26 2023

A107683 Number of perfect Skolem sets.

Original entry on oeis.org

1, 1, 3, 11, 35, 114, 407, 1486, 5414, 19923, 74230, 278462, 1049318, 3972395, 15101658, 57607431, 220391316, 845366406, 3250192681, 12521965697

Offset: 1

Ralf Stephan, Jun 10 2005

nonn

G. Nordh, Perfect Skolem sequences

Cf. A004075, A060963, A099152.

A222320 Number of open Skolem sequences of order n.

Original entry on oeis.org

1, 2, 4, 8, 20, 52, 146, 430, 1306, 4176, 13832, 47452, 169044, 619672, 234225

Offset: 1

N. J. A. Sloane, Feb 18 2013

S. Burrill and L. Yen, Constructing Skolem sequences via generating trees, arXiv preprint arXiv:1301.6424, 2013

Cf. A004075.

A285485 Number of (n+1)-extended Skolem sequences of order n.

Original entry on oeis.org

0, 0, 2, 2, 0, 0, 44, 260, 0, 0, 33104, 203712, 0, 0, 75499696, 621309008, 0, 0, 492805156768, 5068810602400, 0, 0, 7346944632542720

Offset: 1

Fausto A. C. Cariboni, Apr 19 2017

Number of Rosa sequences of order n.

a(n) computed counting reflected solutions.

			For n = 3, there are 2 solutions: 1 1 3 0 2 3 2 and 2 3 2 0 3 1 1.
For n = 4, there are 2 solutions: 1 1 3 4 0 3 2 4 2 and 2 4 2 3 0 4 3 1 1.

N. Francetić, E. Mendelsohn, A survey of Skolem-type sequences and Rosa's use of them, Math. Slovaca 59 (2009), pp. 39-76
Jeppe Winther Larsen, Counting the Skolem sequences using inclusion-exclusion
R. Rees, N. Shalaby, A. Sharary, Indecomposable Skolem and Rosa sequences

Cf. A004077, A004075

a(1)-a(18) from Jeppe Winther Larsen (jwl(AT)itu.dk), Oct 12 2009
a(1)-a(18) confirmed, a(19)-a(22) from Fausto A. C. Cariboni, Apr 19 2017
a(23) from Fausto A. C. Cariboni, May 11 2017

A375254 Number of distinct ways to erect n semicircles of distinct diameters in [n] on the number line from 1 to 2n using 2 colors where all semicircles of the same color are mutually noncrossing. Two ways are regarded the same if the number line is reversed or the colors are exchanged.

Original entry on oeis.org

0, 0, 0, 6, 4, 0, 0, 60, 186, 0, 0, 1248, 2590, 0, 0, 22820, 46384, 0, 0, 365392, 730456

Offset: 1

Ron L.J. van den Burg and Daniël Kuckartz, Aug 07 2024

a(n) is also half the number of ways to partition [2n] in n pairs, divided over two indistinct nonempty buckets such that the differences of all numbers in the pairs (the pair sizes) are distinct and all pairs in a bucket are mutually noncrossing.
a(n) is zero for n mod 4 equals 2 or 3.
Proof: (Start)
Fix n. The list of semicircle endpoint pairs { {1,2}, {3,4}, {5,6}, {7,8}, ..., {2n-1,2n} } is not a valid way, since the diameters of the n semicircles are all 1 and we need them to be distinct in [n].
However, the parity of the sum of the n diameters is the parity of n itself.
Every valid way can be retrieved by pairwise exchanges of two semicircle endpoints 1 and 2, or 2 and 3, or 3 and 4, ... or n-1 and n. The parity of the sum of the diamaters is an invariant in these pairwise exchanges.
Therefore the parity of the sum of the n diameters of all valid ways is also the same as the parity of n itself.
On the other hand, the sum of the n distings diameters is n(n+1)/2 and therefore has a parity of n(n+1)/2. Comparing the parity of n with the parity of n(n+1)/2 rules out the possibility of n being congruent to 2 or 3 mod 4.
(End)
a(n) is nonzero for n mod 4 equals 1 and n>=5.
Proof (partly by T. Skolem, Theorem 2, see link): (Start)
For n=5, an example is (2,3,red), (6,8,red), (7,10,blue), (1,5,blue), (4,9,red).
For n=4m+1 with m>=2 the following way is valid:
1) all semicircles (4m+2+r, 8m+2-r,red) for r=0..2m-1,
2) the semicircles (r,4m+1-r,red) for r=1..m,
3) the semicircle (m+1,m+2,red),
4) the semicirles (m+2+r,3m+1-r,red) for r=1..m-2,
5) two semicircles (2m+1,6m+2,blue) and (2m+2,4m+1,blue).
(End)
a(n) is also the number of planar solutions of order n for the Nickerson variant of Langford (or Langford-Skolem) problem where counting different colorings separately and considering reverse solutions and color exchanges the same. Compare with A004075 which doesn't restrict to planar solutions. Do note that here Skolem sequences can be counted multiple times. Take Skolem sequence 4 7 5 2 4 2 8 5 7 6 3 1 1 3 8 6 as an example, then these four solutions are counted separately. The numbers 1 and 3 are colored differently here:
            +---------------+
            |       +-----+ |
+-------+   |       | +-+ | |
4 7 5 2 4 2 8 5 7 6 3 1 1 3 8 6
  | | +---+   | | +-----------+
  | +---------+ |
  +-------------+
            +---------------+
+-------+   |       +-----+ |
4 7 5 2 4 2 8 5 7 6 3 1 1 3 8 6
  | | +---+   | | |   +-+     |
  | +---------+ | +-----------+
  +-------------+
            +---------------+
+-------+   |         +-+   |
4 7 5 2 4 2 8 5 7 6 3 1 1 3 8 6
  | | +---+   | | | +-----+   |
  | +---------+ | +-----------+
  +-------------+
+-------+   +---------------+
4 7 5 2 4 2 8 5 7 6 3 1 1 3 8 6
  | | +---+   | | | | +-+ |   |
  | +---------+ | | +-----+   |
  +-------------+ +-----------+
However, the following four solutions are considered the same (horizontal or vertical mirroring):
            +---------------+
            |       +-----+ |
+-------+   |       | +-+ | |
4 7 5 2 4 2 8 5 7 6 3 1 1 3 8 6
  | | +---+   | | +-----------+
  | +---------+ |
  +-------------+
  +---------------+
  |       +-----+ |
  |       | +-+ | |   +-------+
6 8 3 1 1 3 6 7 5 8 2 4 2 5 7 4
+-----------+ | | +---+   | |
              | +---------+ |
              +-------------+
  +-------------+
  | +---------+ |
  | | +---+   | | +-----------+
4 7 5 2 4 2 8 5 7 6 3 1 1 3 8 6
+-------+   |       | +-+ | |
            |       +-----+ |
            +---------------+
              +-------------+
              | +---------+ |
+-----------+ | | +---+   | |
6 8 3 1 1 3 6 7 5 8 2 4 2 5 7 4
  |       | +-+ | |   +-------+
  |       +-----+ |
  +---------------+

			For n=4 the a(4)=6 ways are as follows.
If the notation for the semicircle of diameter 4 connecting 2 to 6 colored red is ({2,6},red), then the six ways are (in descending diameters 4, 3, 2, 1):
{ ({1,5},red), ({3,6},blue), ({2,4},red), ({7,8},red) },
{ ({1,5},red), ({4,7},blue), ({6,8},red), ({2,3},red) },
{ ({2,6},red), ({1,4},blue), ({3,5},red), ({7,8},red) },
{ ({1,5},blue), ({3,6},red), ({2,4},blue), ({7,8},red) },
{ ({1,5},blue), ({4,7},red), ({6,8},blue), ({2,3},red) } and
{ ({2,6},blue), ({1,4},red), ({3,5},blue), ({7,8},red) }.
The way { ({1,5},blue), ({3,6},red), ({2,4},blue), ({7,8},blue) } is considered the same as the first one listed above by exchanging red and blue.
The way { ({4,8},red), ({3,6},blue), ({5,7},red), ({1,2},red) } is also considered the same as the first one listed above by mirroring the number line (1 becomes 8, 2 becomes 7, ..., 8 becomes 1).

T. Skolem, On certain distributions of integers in pairs with given differences, Math. Scand., Vol. 5 (1957), pp. 57-68.
Wikipedia, Noncrossing partition

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

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

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Sage

Formula

Extensions

A275801 Number of alternating permutations of the multiset {1,1,2,2,...,n,n}.

Views

Author

Keywords

Comments

Links

Crossrefs

A202951 Number of Nickerson-type partitions of [1,...,3n] into triples satisfying x+y=z.

Views

Author

Keywords

Comments

Links

Crossrefs

A275829 Number of weakly alternating permutations of the multiset {1,1,2,2,...,n,n}.

Views

Author

Keywords

Comments

Links

Crossrefs

A268537 Number of Skolem sequences of order n, as n runs through the positive integers congruent to 0 and 1 mod 4.

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

A107683 Number of perfect Skolem sets.

Views

Author

Keywords

Links

Crossrefs

A222320 Number of open Skolem sequences of order n.

Views

Author

Keywords

Links

Crossrefs

A285485 Number of (n+1)-extended Skolem sequences of order n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A375254 Number of distinct ways to erect n semicircles of distinct diameters in [n] on the number line from 1 to 2n using 2 colors where all semicircles of the same color are mutually noncrossing. Two ways are regarded the same if the number line is reversed or the colors are exchanged.

Views

Author

Keywords

Comments

Examples

Links