A395260 - OEIS

%I #22 May 04 2026 01:26:51

%S 4,13,33,71,136,239,393,613,916,1321,1849,2523,3368,4411,5681,7209,

%T 9028,11173,13681,16591,19944,23783,28153,33101,38676,44929,51913,

%U 59683,68296,77811,88289,99793,112388,126141,141121,157399,175048,194143,214761,236981,260884,286553,314073,343531,375016,408619,444433,482553,523076,566101

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

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

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

%H Paolo Xausa, <a href="/A395260/b395260.txt">Table of n, a(n) for n = 1..10000</a>

%H Brandy Barnette, Warren Nichols, and Tom 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).

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

%H <a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (5,-10,10,-5,1).

%F a(n) = (n^4 + 4*n^3 + 17*n^2 + 14*n + 12)/12.

%F a(n) = binomial(n,0) + 3*binomial(n,1) + 6*binomial(n,2) + 5*binomial(n,3) + 2*binomial(n,4).

%F a(n) = 5*a(n-1) - 10*a(n-2) + 10*a(n-3) - 5*a(n-4) + a(n-5) for n >= 6.

%F G.f.: x*(4 - 7*x + 8*x^2 - 4*x^3 + x^4)/(1-x)^5.

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

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

%t LinearRecurrence[{5, -10, 10, -5, 1}, {4, 13, 33, 71, 136}, 50] (* _Paolo Xausa_, May 03 2026 *)

%o (Python)

%o def a(n): return (n**4 + 4*n**3 + 17*n**2 + 14*n + 12) // 12

%o print([a(n) for n in range(1, 51)])

%Y Cf. A393665 (square case |CC([n] X [n])|), A394682 (cubic case |CC([n]^3)|), A394685.

%K nonn,easy

%O 1,1

%A _Thomas DiFiore_, Apr 17 2026