A328377 a(n) is the number of "generalized signotopes", i.e., mappings X:{{1..n} choose 3}->{+,-} such that for any four indices a < b < c < d, the sequence X(a,b,c), X(a,b,d), X(a,c,d), X(b,c,d) changes its sign at most twice (equivalently +-+- and -+-+ are forbidden).

2, 14, 544, 173128, 630988832, 35355434970848

Offset

3,1

Comments

Clearly a generalization of "signotopes" (cf. A006245), i.e., mappings X:{{1..n} choose 3}->{+,-} such that for any four indices a < b < c < d, the sequence X(a,b,c), X(a,b,d), X(a,c,d), X(b,c,d) changes its sign at most once (see Felsner-Weil and Balko-Fulek-Kynčl reference).

Also a generalization of "simple topological drawings" (a.k.a. good drawings, cf. A276109), i.e., non-isomorphic drawings of the complete graph K_n such that any two edges intersect at most once. In a simple topological drawings, each three vertices a < b < c determine a triangle which is either oriented clockwise or counterclockwise -- this clearly motivates the mapping X. It can be checked that in any simple topological drawing of K_4, the sequence X(a,b,c), X(a,b,d), X(a,c,d), X(b,c,d) changes its sign at most twice.

Also known as "Interior triple systems", see Knuth's book.

References

D. Knuth, Axioms and Hulls, Springer, 1992, 9-11.

Links

Table of n, a(n) for n=3..8.

M. Balko, R. Fulek, and J. Kynčl, Crossing Numbers and Combinatorial Characterization of Monotone Drawings of K_n, Discrete & Computational Geometry, Volume 53, Issue 1, 2015, Pages 107-143.

H. Bergold, S. Felsner, M. Scheucher, F. Schröder, and R. Steiner, Topological Drawings meet Classical Theorems from Convex Geometry, Discrete & Computational Geometry, Springer, 2022.

S. Felsner and H. Weil, Sweeps, arrangements and signotopes, Discrete Applied Mathematics, Volume 109, Issues 1-2, 2001, Pages 67-94.

Manfred Scheucher, C-program for computing the first terms

Crossrefs

Cf. A006245, A329980.

Sequence in context: A357508 A277134 A009997 * A048137 A005806 A015184

Adjacent sequences: A328374 A328375 A328376 * A328378 A328379 A328380

Keyword

nonn,more,hard

Author

Manfred Scheucher, Oct 14 2019

Extensions

a(8) from Robert Lauff and Manfred Scheucher, Nov 04 2022

Status

approved