OFFSET
1,4
COMMENTS
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
| | +-+ | | +-------+
| +-----+ |
+---------------+
LINKS
T. Skolem, On certain distributions of integers in pairs with given differences, Math. Scand., Vol. 5 (1957), pp. 57-68.
Wikipedia, Noncrossing partition
EXAMPLE
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).
CROSSREFS
KEYWORD
nonn,more
AUTHOR
Ron L.J. van den Burg and Daniël Kuckartz, Aug 07 2024
STATUS
approved