|
|
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).
|
|
3
|
|
|
|
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
|
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,more,hard
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|