A393665 Number of order-convex subsets of the square grid poset [n]^2 with componentwise partial order.

2, 13, 114, 1146, 12578, 146581, 1784114, 22443232, 289721772, 3818789778, 51205458186, 696532306614, 9590979868122, 133456745720613, 1874038107800370, 26527162393038300, 378160443213077840, 5424985742151048640, 78266294077222701884, 1134914052039617826556

Offset

1,1

Comments

A subset S of [n]^2 = {1,...,n}^2 with componentwise order is order-convex if whenever a, b in S with a <= c <= b, then c in S. Equivalently, S is the intersection of a downset and an upset.

The growth constant rho = lim a(n)^(1/n) = 16. The upper bound rho <= 16 follows from an ideal/filter injection a(n) <= C(2n,n)^2; the lower bound follows from a tiling argument. Both bounds are formally verified in Lean 4.

The sequence is supermultiplicative: a(m+n) >= a(m)*a(n) for all m, n >= 1.

Barnette, Nichols, and Richmond (2019) gave exact formulas for the number of order-convex subsets of [n] x [m] for small fixed m. The present sequence counts order-convex subsets of the square grid [n]^2 as a function of n.

a(n) can be computed by a transfer-matrix method with C(n+2,2) states.

References

B. Barnette, W. Nichols, and T. Richmond, The number of convex sets in a product of totally ordered sets, Rocky Mountain J. Math., 49 (2019), no. 2, 369-385.

Links

Table of n, a(n) for n=1..20.

Thomas DiFiore, Lean 4 formal verification.

Thomas DiFiore, Causal-Algebraic Geometry, Zenodo.

B. Barnette, W. Nichols, and T. Richmond, The number of convex sets in a product of totally ordered sets, Rocky Mountain J. Math. 49(2): 369-385 (2019).

Formula

a(m+n) >= a(m)*a(n) for all m, n >= 1 .

a(n) <= C(2n,n)^2 <= 16^n.

Limit_{n->oo} a(n)^(1/n) = 16.

Example

a(1) = 2: the empty set and {(1,1)}.
a(2) = 13: the empty set, 4 singletons, 4 edges (pairs of comparable elements), 3 triples (L-shapes and the diagonal), and the full grid.

Prog

(Python)
# Brute force for small n; use transfer matrix for n > 4
from itertools import product, combinations
def is_convex(S, n):
    S = set(S)
    for a in S:
        for b in S:
            if a[0]<=b[0] and a[1]<=b[1]:
                for c in product(range(a[0], b[0]+1), range(a[1], b[1]+1)):
                    if c not in S: return False
    return True
def a(n):
    grid = list(product(range(n), repeat=2))
    count = 0
    for r in range(len(grid)+1):
        for S in combinations(grid, r):
            if is_convex(S, n): count += 1
    return count
print([a(n) for n in range(1, 5)])  # [2, 13, 114, 1146]

Crossrefs

Cf. A394682.

Sequence in context: A088604 A127891 A110369 * A212071 A258620 A379285

Adjacent sequences: A393662 A393663 A393664 * A393666 A393667 A393668

Keyword

nonn

Author

Thomas DiFiore, Mar 28 2026

Status

approved