|
%I #23 Aug 14 2019 10:52:58
%S 1,1,1,3,18,181,2792,62960,2020256,90847421,5674075324,489320844468,
%T 57995151443168
%N 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 a(n) is also the number of connected ordered bipartite Cohen-Macaulay graphs with 2n vertices.
%H 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 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 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 R. H. Villarreal, <a href="https://doi.org/10.1007/BF02568497">Cohen-Macaulay graphs</a>, Manuscripta Math. 66(3) (1990), 277-293.
%H 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 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 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 P1 = {(1,3), (2,3), (2,4)},
%e P2 = {(1,4), (2,4), (3,4)},
%e P3 = {(1,4), (2,3), (2,4)},
%e P4 = {(1,4), (2,3), (2,4), (3,4)},
%e P5 = {(1,2), (1,4), (3,4)},
%e P6 = {(1,2), (1,4), (2,4), (3,4)},
%e P7 = {(1,3), (1,4), (2,3)},
%e P8 = {(1,3), (1,4), (2,4)},
%e P9 = {(1,3), (1,4), (2,4), (3,4)},
%e P10 = {(1,3), (1,4), (2,3), (2,4)},
%e P11 = {(1,3), (1,4), (2,3), (2,4), (3,4)},
%e P12 = {(1,2), (1,3), (1,4)},
%e P13 = {(1,2), (1,3), (1,4), (3,4)},
%e P14 = {(1,2), (1,3), (1,4), (2,3)},
%e P15 = {(1,2), (1,3), (1,4), (2,4)},
%e P16 = {(1,2), (1,3), (1,4), (2,4), (3,4)},
%e P17 = {(1,2), (1,3), (1,4), (2,3), (2,4)},
%e P18 = {(1,2), (1,3), (1,4), (2,3), (2,4), (3,4)}.
%o (GAP) A006455 := [1, 2, 7, 40, 357, 4824, 96428, 2800472, 116473461, 6855780268, 565505147444, 64824245807684];
%o a := function(n)
%o local b,i;
%o b:= [];
%o b[1] := 1;
%o for i in [2..n] do
%o b[i] :=0;
%o 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 od;
%o return b[n];
%o end;
%Y Cf. A006455, A323658.
%K nonn,hard,more
%O 0,4
%A _M. Farrokhi D. G._, Jan 16 2019
|
