A393665 - OEIS

%I #22 Apr 16 2026 22:26:42

%S 2,13,114,1146,12578,146581,1784114,22443232,289721772,3818789778,

%T 51205458186,696532306614,9590979868122,133456745720613,

%U 1874038107800370,26527162393038300,378160443213077840,5424985742151048640,78266294077222701884,1134914052039617826556

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

%C 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.

%C 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.

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

%C 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.

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

%D 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.

%H Thomas DiFiore, <a href="https://github.com/tomdif/causal-algebraic-geometry-lean">Lean 4 formal verification</a>.

%H Thomas DiFiore, <a href="https://zenodo.org/records/19271288">Causal-Algebraic Geometry</a>, Zenodo.

%H B. Barnette, W. Nichols, and T. Richmond, <a href="https://doi.org/10.1216/RMJ-2019-49-2-369">The number of convex sets in a product of totally ordered sets</a>, Rocky Mountain J. Math. 49(2): 369-385 (2019).

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

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

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

%e a(1) = 2: the empty set and {(1,1)}.

%e 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.

%o (Python)

%o # Brute force for small n; use transfer matrix for n > 4

%o from itertools import product, combinations

%o def is_convex(S, n):

%o     S = set(S)

%o     for a in S:

%o         for b in S:

%o             if a[0]<=b[0] and a[1]<=b[1]:

%o                 for c in product(range(a[0],b[0]+1), range(a[1],b[1]+1)):

%o                     if c not in S: return False

%o     return True

%o def a(n):

%o     grid = list(product(range(n), repeat=2))

%o     count = 0

%o     for r in range(len(grid)+1):

%o         for S in combinations(grid, r):

%o             if is_convex(S, n): count += 1

%o     return count

%o print([a(n) for n in range(1, 5)])  # [2, 13, 114, 1146]

%Y Cf. A394682.

%K nonn

%O 1,1

%A _Thomas DiFiore_, Mar 28 2026