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).
1, 1, 1, 3, 18, 181, 2792, 62960, 2020256, 90847421, 5674075324, 489320844468, 57995151443168
Offset: 0
Examples
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.
P1 = {(1,3), (2,3), (2,4)},
P2 = {(1,4), (2,4), (3,4)},
P3 = {(1,4), (2,3), (2,4)},
P4 = {(1,4), (2,3), (2,4), (3,4)},
P5 = {(1,2), (1,4), (3,4)},
P6 = {(1,2), (1,4), (2,4), (3,4)},
P7 = {(1,3), (1,4), (2,3)},
P8 = {(1,3), (1,4), (2,4)},
P9 = {(1,3), (1,4), (2,4), (3,4)},
P10 = {(1,3), (1,4), (2,3), (2,4)},
P11 = {(1,3), (1,4), (2,3), (2,4), (3,4)},
P12 = {(1,2), (1,3), (1,4)},
P13 = {(1,2), (1,3), (1,4), (3,4)},
P14 = {(1,2), (1,3), (1,4), (2,3)},
P15 = {(1,2), (1,3), (1,4), (2,4)},
P16 = {(1,2), (1,3), (1,4), (2,4), (3,4)},
P17 = {(1,2), (1,3), (1,4), (2,3), (2,4)},
P18 = {(1,2), (1,3), (1,4), (2,3), (2,4), (3,4)}.
Links
- M. Estrada and R. H. Villarreal, Cohen-Macaulay bipartite graphs, Arch. Math. (Basel) 68(2) (1997), 124-128.
- J. Herzog and T. Hibi, Distributive lattices, bipartite graphs and Alexander duality, J. Algebraic Combin. 22(3) (2005), 289-302.
- M. Mahmoudi and A. Mousivand, An alternative proof of a characterization of Cohen-Macaulay bipartite graphs, Abh. Math. Semin. Univ. Hambg. 80(1) (2010), 145-148.
- R. H. Villarreal, Cohen-Macaulay graphs, Manuscripta Math. 66(3) (1990), 277-293.
- R. H. Villarreal, Unmixed bipartite graphs, arXiv:math/0606479 [math.CO], 2006-2007; Rev. Colomb. Mat. 41(2) (2007), 393-395.
- R. Zaare-Nahandi, Cohen-Macaulayness of bipartite graphs, revisited, Bull. Malays. Math. Sci. Soc. 38(4) (2015), 1601-1607.
Programs
-
GAP
A006455 := [1, 2, 7, 40, 357, 4824, 96428, 2800472, 116473461, 6855780268, 565505147444, 64824245807684]; a := function(n) local b,i; b:= []; b[1] := 1; for i in [2..n] do b[i] :=0; 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]))); od; return b[n]; end;
Comments