cp's OEIS Frontend

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.

%I A375254 #24 Sep 26 2024 23:55:30
%S A375254 0,0,0,6,4,0,0,60,186,0,0,1248,2590,0,0,22820,46384,0,0,365392,730456
%N 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.
%C A375254 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.
%C A375254 a(n) is zero for n mod 4 equals 2 or 3.
%C A375254 Proof: (Start)
%C A375254 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].
%C A375254 However, the parity of the sum of the n diameters is the parity of n itself.
%C A375254 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.
%C A375254 Therefore the parity of the sum of the n diameters of all valid ways is also the same as the parity of n itself.
%C A375254 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.
%C A375254 (End)
%C A375254 a(n) is nonzero for n mod 4 equals 1 and n>=5.
%C A375254 Proof (partly by T. Skolem, Theorem 2, see link): (Start)
%C A375254 For n=5, an example is (2,3,red), (6,8,red), (7,10,blue), (1,5,blue), (4,9,red).
%C A375254 For n=4m+1 with m>=2 the following way is valid:
%C A375254 1) all semicircles (4m+2+r, 8m+2-r,red) for r=0..2m-1,
%C A375254 2) the semicircles (r,4m+1-r,red) for r=1..m,
%C A375254 3) the semicircle (m+1,m+2,red),
%C A375254 4) the semicirles (m+2+r,3m+1-r,red) for r=1..m-2,
%C A375254 5) two semicircles (2m+1,6m+2,blue) and (2m+2,4m+1,blue).
%C A375254 (End)
%C A375254 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:
%C A375254             +---------------+
%C A375254             |       +-----+ |
%C A375254 +-------+   |       | +-+ | |
%C A375254 4 7 5 2 4 2 8 5 7 6 3 1 1 3 8 6
%C A375254   | | +---+   | | +-----------+
%C A375254   | +---------+ |
%C A375254   +-------------+
%C A375254             +---------------+
%C A375254 +-------+   |       +-----+ |
%C A375254 4 7 5 2 4 2 8 5 7 6 3 1 1 3 8 6
%C A375254   | | +---+   | | |   +-+     |
%C A375254   | +---------+ | +-----------+
%C A375254   +-------------+
%C A375254             +---------------+
%C A375254 +-------+   |         +-+   |
%C A375254 4 7 5 2 4 2 8 5 7 6 3 1 1 3 8 6
%C A375254   | | +---+   | | | +-----+   |
%C A375254   | +---------+ | +-----------+
%C A375254   +-------------+
%C A375254 +-------+   +---------------+
%C A375254 4 7 5 2 4 2 8 5 7 6 3 1 1 3 8 6
%C A375254   | | +---+   | | | | +-+ |   |
%C A375254   | +---------+ | | +-----+   |
%C A375254   +-------------+ +-----------+
%C A375254 However, the following four solutions are considered the same (horizontal or vertical mirroring):
%C A375254             +---------------+
%C A375254             |       +-----+ |
%C A375254 +-------+   |       | +-+ | |
%C A375254 4 7 5 2 4 2 8 5 7 6 3 1 1 3 8 6
%C A375254   | | +---+   | | +-----------+
%C A375254   | +---------+ |
%C A375254   +-------------+
%C A375254   +---------------+
%C A375254   |       +-----+ |
%C A375254   |       | +-+ | |   +-------+
%C A375254 6 8 3 1 1 3 6 7 5 8 2 4 2 5 7 4
%C A375254 +-----------+ | | +---+   | |
%C A375254               | +---------+ |
%C A375254               +-------------+
%C A375254   +-------------+
%C A375254   | +---------+ |
%C A375254   | | +---+   | | +-----------+
%C A375254 4 7 5 2 4 2 8 5 7 6 3 1 1 3 8 6
%C A375254 +-------+   |       | +-+ | |
%C A375254             |       +-----+ |
%C A375254             +---------------+
%C A375254               +-------------+
%C A375254               | +---------+ |
%C A375254 +-----------+ | | +---+   | |
%C A375254 6 8 3 1 1 3 6 7 5 8 2 4 2 5 7 4
%C A375254   |       | +-+ | |   +-------+
%C A375254   |       +-----+ |
%C A375254   +---------------+
%H A375254 T. Skolem, <a href="https://doi.org/10.7146/math.scand.a-10490">On certain distributions of integers in pairs with given differences</a>, Math. Scand., Vol. 5 (1957), pp. 57-68.
%H A375254 Wikipedia, <a href="https://en.wikipedia.org/wiki/Noncrossing_partition">Noncrossing partition</a>
%e A375254 For n=4 the a(4)=6 ways are as follows.
%e A375254 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):
%e A375254 { ({1,5},red), ({3,6},blue), ({2,4},red), ({7,8},red) },
%e A375254 { ({1,5},red), ({4,7},blue), ({6,8},red), ({2,3},red) },
%e A375254 { ({2,6},red), ({1,4},blue), ({3,5},red), ({7,8},red) },
%e A375254 { ({1,5},blue), ({3,6},red), ({2,4},blue), ({7,8},red) },
%e A375254 { ({1,5},blue), ({4,7},red), ({6,8},blue), ({2,3},red) } and
%e A375254 { ({2,6},blue), ({1,4},red), ({3,5},blue), ({7,8},red) }.
%e A375254 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.
%e A375254 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).
%K A375254 nonn,more
%O A375254 1,4
%A A375254 _Ron L.J. van den Burg_ and Daniël Kuckartz, Aug 07 2024