OFFSET
1,1
COMMENTS
A subset S of [2] X [n] = {1,2} X {1,...,n} with componentwise order is order-convex if, whenever a and b are in S with a <= c <= b for some element c of [2] X [n], then c is also in S. Equivalently, S is the intersection of a downset and an upset.
This is the width-2 case of the family |CC([m] X [n])| counting order-convex subsets of rectangular grid posets. For each fixed m >= 1, |CC([m] X [n])| is a polynomial of degree 2m in n. The m=1 case gives (n^2 + 3n + 2)/2 (intervals plus singletons plus empty set). The m=2 case is this sequence. The m=3 case has degree 6 with a(n) = Sum_{k=0..6} c_k * binomial(n,k) where (c_0,...,c_6) = (1, 6, 20, 35, 36, 20, 5).
LINKS
Paolo Xausa, Table of n, a(n) for n = 1..10000
Brandy Barnette, Warren Nichols, and Tom Richmond, The number of convex sets in a product of totally ordered sets, Rocky Mountain J. Math. 49(2): 369-385 (2019).
Thomas DiFiore, Lean 4 formal verification repository.
Index entries for linear recurrences with constant coefficients, signature (5,-10,10,-5,1).
FORMULA
a(n) = (n^4 + 4*n^3 + 17*n^2 + 14*n + 12)/12.
a(n) = binomial(n,0) + 3*binomial(n,1) + 6*binomial(n,2) + 5*binomial(n,3) + 2*binomial(n,4).
a(n) = 5*a(n-1) - 10*a(n-2) + 10*a(n-3) - 5*a(n-4) + a(n-5) for n >= 6.
G.f.: x*(4 - 7*x + 8*x^2 - 4*x^3 + x^4)/(1-x)^5.
EXAMPLE
a(1) = 4: the order-convex subsets of [2] X [1] = {(1,1), (2,1)} are {}, {(1,1)}, {(2,1)}, and {(1,1),(2,1)}.
a(2) = 13: labeling [2] X [2] as a=(1,1), b=(2,1), c=(1,2), d=(2,2) with a <= b <= d, a <= c <= d, and b,c incomparable, the 13 order-convex subsets are {}; {a}, {b}, {c}, {d}; {a,b}, {a,c}, {b,c}, {b,d}, {c,d}; {a,b,c}, {b,c,d}; {a,b,c,d}.
MATHEMATICA
LinearRecurrence[{5, -10, 10, -5, 1}, {4, 13, 33, 71, 136}, 50] (* Paolo Xausa, May 03 2026 *)
PROG
(Python)
def a(n): return (n**4 + 4*n**3 + 17*n**2 + 14*n + 12) // 12
print([a(n) for n in range(1, 51)])
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Thomas DiFiore, Apr 17 2026
STATUS
approved