A323502 -id:A323502 - cp's OEIS frontend

A006455 Number of partial orders on {1,2,...,n} that are contained in the usual linear order (i.e., xRy => x

1, 1, 2, 7, 40, 357, 4824, 96428, 2800472, 116473461, 6855780268, 565505147444, 64824245807684

Offset: 0

Also known as naturally labeled posets. - David Bevan, Nov 16 2023
Also the number of n X n upper triangular Boolean matrices B with all diagonal entries 1 such that B = B^2.
The asymptotic values derived by Brightwell et al. are relevant only for extremely large values of n. The average number of linear extensions (topological sorts) of a random partial order on {1,...,n} is n! S_n / N_n, where S_n is this sequence and N_n is sequence A001035

			a(3) = 7: {}, {1R2}, {1R3}, {2R3}, {1R2, 1R3}, {1R3, 2R3}, {1R2, 1R3, 2R3}.

N. B. Hindman, personal communication.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

S. P. Avann, The lattice of natural partial orders, Aequationes Mathematicae 8 (1972), 95-102.
David Bevan, Gi-Sang Cheon and Sergey Kitaev, On naturally labelled posets and permutations avoiding 12-34, arXiv:2311.08023 [math.CO], 2023.
Graham Brightwell, Hans Jürgen Prömel and Angelika Steger, The average number of linear extensions of a partial order, Journal of Combinatorial Theory A73 (1996), 193-206.
S. R. Finch, Transitive relations, topologies and partial orders
S. R. Finch, Transitive relations, topologies and partial orders, June 5, 2003. [Cached copy, with permission of the author]
Joël Gay and Vincent Pilaud, The weak order on Weyl posets, arXiv:1804.06572 [math.CO], 2018.
L. H. Harper, The Range of a Steiner Operation, arXiv preprint arXiv:1608.07747 [math.CO], 2016.
N. Hindman and N. J. A. Sloane, Correspondence, 1981-1991
Florent Hivert and Nicolas M. Thiéry, Controlling the C3 Super Class Linearization Algorithm for Large Hierarchies of Classes, Order (2022).
Adam King, A. Laubmeier, K. Orans, and A. Godbole, Universal and Overlap Cycles for Posets, Words, and Juggling Patterns, arXiv preprint arXiv:1405.5938 [math.CO], 2014.
D. E. Knuth, POSETS, program for n = 10, 11, 12.
J.-G. Luque, L. Mignot and F. Nicart, Some Combinatorial Operators in Language Theory, arXiv preprint arXiv:1205.3371 [cs.FL], 2012. - _N. J. A. Sloane_, Oct 22 2012
Index entries for sequences related to posets

Cf. A000112, A001035, A323502.

E.g.f.: exp(S(x)-1) where S(x)is the e.g.f. for A323502. - Ludovic Schwob, Mar 29 2024

Additional comments and more terms from Don Knuth, Dec 03 2001

A323842 Number of n-node Stanley graphs without isolated nodes.

Original entry on oeis.org

1, 0, 1, 2, 11, 72, 677, 8686, 152191, 3632916, 118317913, 5271781946, 322549557299, 27208234437984, 3177021912874253, 515436469519284358, 116581257420399219175, 36866447823471507563436, 16339685138335030408029889, 10170100145132835334268145362

Offset: 0

N. J. A. Sloane, Feb 04 2019

nonn

For precise definition see Knuth (1997).

Also, the number of naturally labeled posets on [n] with height at most two and no isolated elements. - David Bevan, Nov 17 2023

Alois P. Heinz, Table of n, a(n) for n = 0..115
David Bevan, Gi-Sang Cheon and Sergey Kitaev, On naturally labelled posets and permutations avoiding 12-34, arXiv:2311.08023 [math.CO], 2023.
D. E. Knuth, Letter to Daniel Ullman and others, Apr 29 1997. [Annotated scanned copy, with permission]

Cf. A135922, A323841, A323843, A323502, A356111.

b:= proc(n) option remember; add(mul(
      (2^(i+k)-1)/(2^i-1), i=1..n-k), k=0..n)
    end:
g:= proc(n) option remember;
      add(b(n-j)*binomial(n, j)*(-1)^j, j=0..n)
    end:
a:= proc(n) option remember;
      add(g(n-j)*binomial(n, j)*(-1)^j, j=0..n)
    end:
seq(a(n), n=0..21);  # Alois P. Heinz, Sep 24 2019

b[n_] := b[n] = Sum[Product[(2^(i+k) - 1)/(2^i - 1), {i, n-k}], {k, 0, n}];
g[n_] := g[n] = Sum[b[n-j] Binomial[n, j] (-1)^j, {j, 0, n}];
a[n_] := a[n] = Sum[g[n-j] Binomial[n, j] (-1)^j, {j, 0, n}];
a /@ Range[0, 21] (* Jean-François Alcover, May 24 2020, after Alois P. Heinz *)

P(n, k, x):=if k<0 or n<0 then 0 else if k=0 then 1 else x*P(n, k-1, x)+
2^k*P(n-1, k, (x+1)/2);
a(n):=sum(P(n-k, k, -1), k, 0, n);
makelist(a(n), n, 0, 10);
/* Vladimir Kruchinin, Mar 08 2020 */

a(n) = Sum_{j=0..n} (-1)^j * C(n,j) * A135922(n-j). - Alois P. Heinz, Sep 24 2019
a(n) = Sum_{k=0..n} P(n-k, k, -1), where  P(n, k, x) = x*P(n, k-1, x) + 2^k*P(n-1, k, (x+1)/2). - Vladimir Kruchinin, Mar 09 2020
G.f.: g(1,0), where g(u,v) = 1 + x*((v-1)*g(u,v) + g(2*u,u+v)). - David Bevan, Jul 28 2022
G.f.: 1/(1+z) * Sum_{k>=0} (z^k / Prod_{i=2..k} (1 - (2^i-2)*z)). - David Bevan, Nov 17 2023; simplified on Jul 25 2024

More terms from Alois P. Heinz, Sep 24 2019

A323658 Number of bipartite graphs associated with connected transitive oriented graphs.

Original entry on oeis.org

1, 1, 1, 2, 7, 25, 133, 854

Offset: 0

M. Farrokhi D. G., Jan 23 2019

Also the number of unlabeled connected Cohen-Macaulay bipartite graphs up to graph isomorphism.

If G is an oriented graph with vertex set {1,...,n}, then the associated bipartite graph is a bipartite graph B(G) with parts {a1,...,an} and {b1,...,bn} such that ai ~ bj if (i,j) is an edge in G.

			Example: For n = 4 the a(4) = 7 solutions are given by the edge sets
E1 = {(1,5), (1,7), (2,6), (2,7), (2,8), (3,7), (4,8)},
E2 = {(1,5), (1,8), (2,6), (2,8), (3,7), (3,8), (4,8)},
E3 = {(1,5), (1,8), (2,6), (2,7), (2,8), (3,7), (3,8), (4,8)},
E4 = {(1,5), (1,7), (1,8), (2,6), (2,7), (2,8), (3,7), (4,8)},
E5 = {(1,5), (1,7), (1,8), (2,6), (2,7), (2,8), (3,7), (3,8), (4,8)},
E6 = {(1,5), (1,6), (1,7), (1,8), (2,6), (2,8), (3,7), (3,8), (4,8)},
E7 = {(1,5), (1,6), (1,7), (1,8), (2,6), (2,7), (2,8), (3,7), (3,8), (4,8)}.

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, 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.

Cf. A006455, A323502.

cp's OEIS Frontend

A006455 Number of partial orders on {1,2,...,n} that are contained in the usual linear order (i.e., xRy => x

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

Extensions

A323842 Number of n-node Stanley graphs without isolated nodes.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Maxima

Formula

Extensions

A323658 Number of bipartite graphs associated with connected transitive oriented graphs.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs