cp's OEIS Frontend

A323502 Number of irreducible or connected partial orders on {1,2,...,n} that are contained in the usual linear order (i.e., xRy => x < y).

%I A323502 #23 Aug 14 2019 10:52:58
%S A323502 1,1,1,3,18,181,2792,62960,2020256,90847421,5674075324,489320844468,
%T A323502 57995151443168
%N A323502 Number of irreducible or connected partial orders on {1,2,...,n} that are contained in the usual linear order (i.e., xRy => x < y).
%C A323502 a(n) is also the number of connected ordered bipartite Cohen-Macaulay graphs with 2n vertices.
%H A323502 M. Estrada and R. H. Villarreal, <a href="https://doi.org/10.1007/s000130050040">Cohen-Macaulay bipartite graphs</a>, Arch. Math. (Basel) 68(2) (1997), 124-128.
%H A323502 J. Herzog and T. Hibi, <a href="https://doi.org/10.1007/s10801-005-4528-1">Distributive lattices, bipartite graphs and Alexander duality</a>, J. Algebraic Combin. 22(3) (2005), 289-302.
%H A323502 M. Mahmoudi and A. Mousivand, <a href="https://doi.org/10.1007/s12188-009-0032-1">An alternative proof of a characterization of Cohen-Macaulay bipartite graphs</a>, Abh. Math. Semin. Univ. Hambg. 80(1) (2010), 145-148.
%H A323502 R. H. Villarreal, <a href="https://doi.org/10.1007/BF02568497">Cohen-Macaulay graphs</a>, Manuscripta Math. 66(3) (1990), 277-293.
%H A323502 R. H. Villarreal, <a href="https://arxiv.org/abs/math/0606479">Unmixed bipartite graphs</a>, arXiv:math/0606479 [math.CO], 2006-2007; Rev. Colomb. Mat. 41(2) (2007), 393-395.
%H A323502 R. Zaare-Nahandi, <a href="https://doi.org/10.1007/s40840-014-0100-2">Cohen-Macaulayness of bipartite graphs, revisited</a>, Bull. Malays. Math. Sci. Soc. 38(4) (2015), 1601-1607.
%e A323502 For n = 4 the a(4) = 18 solutions are given below. The partial order is assumed to be strict; for the non-strict case, the elements (1,1), (2,2), (3,3), (4,4) should be added to each list.
%e A323502 P1 = {(1,3), (2,3), (2,4)},
%e A323502 P2 = {(1,4), (2,4), (3,4)},
%e A323502 P3 = {(1,4), (2,3), (2,4)},
%e A323502 P4 = {(1,4), (2,3), (2,4), (3,4)},
%e A323502 P5 = {(1,2), (1,4), (3,4)},
%e A323502 P6 = {(1,2), (1,4), (2,4), (3,4)},
%e A323502 P7 = {(1,3), (1,4), (2,3)},
%e A323502 P8 = {(1,3), (1,4), (2,4)},
%e A323502 P9 = {(1,3), (1,4), (2,4), (3,4)},
%e A323502 P10 = {(1,3), (1,4), (2,3), (2,4)},
%e A323502 P11 = {(1,3), (1,4), (2,3), (2,4), (3,4)},
%e A323502 P12 = {(1,2), (1,3), (1,4)},
%e A323502 P13 = {(1,2), (1,3), (1,4), (3,4)},
%e A323502 P14 = {(1,2), (1,3), (1,4), (2,3)},
%e A323502 P15 = {(1,2), (1,3), (1,4), (2,4)},
%e A323502 P16 = {(1,2), (1,3), (1,4), (2,4), (3,4)},
%e A323502 P17 = {(1,2), (1,3), (1,4), (2,3), (2,4)},
%e A323502 P18 = {(1,2), (1,3), (1,4), (2,3), (2,4), (3,4)}.
%o A323502 (GAP) A006455 := [1, 2, 7, 40, 357, 4824, 96428, 2800472, 116473461, 6855780268, 565505147444, 64824245807684];
%o A323502 a := function(n)
%o A323502 local b,i;
%o A323502 b:= [];
%o A323502 b[1] := 1;
%o A323502 for i in [2..n] do
%o A323502     b[i] :=0;
%o A323502     b[i] := A006455[i] - Sum(List(Partitions(i), P -> Factorial(i)/(Product(List(P, Factorial)) * Product(List(Collected(P), x -> Factorial(x[2])))) * Product(List(P), x -> b[x])));
%o A323502 od;
%o A323502 return b[n];
%o A323502 end;
%Y A323502 Cf. A006455, A323658.
%K A323502 nonn,hard,more
%O A323502 0,4
%A A323502 _M. Farrokhi D. G._, Jan 16 2019