A001831 Number of labeled graded partially ordered sets with n elements of height at most 1. (Formerly M2956 N1194)

1, 1, 3, 13, 87, 841, 11643, 227893, 6285807, 243593041, 13262556723, 1014466283293, 109128015915207, 16521353903210521, 3524056001906654763, 1059868947134489801413, 449831067019305308555487, 269568708630308018001547681, 228228540531327778410439620963

Offset

0,3

Comments

Labeled posets where for all a,b,c in the set, do not have a<b<c. (Equivalently, labeled posets with no chain of length 3; 3-avoiding posets.) Labeled digraphs where every node has indegree 0 or outdegree 0.

Number of labeled digraphs with n vertices with no directed path of length 2. Number of n X n {0,1} matrices A such that A^2 = 0. - Michael Somos, Jul 28 2013

Number of relations on n labeled nodes that are simultaneously transitive and antitransitive. - Peter Kagey, Feb 14 2021

References

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

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

Links

T. D. Noe, Table of n, a(n) for n = 0..50

D. A. Klarner, The number of graded partially ordered sets, J. Combin. Theory, 6 (1969), 12-19. [Annotated scanned copy]

D. A. Klarner, The number of graded partially ordered sets, J. Combin. Theory, 6 (1969), 12-19.

A. Motzek and R. Möller, Exploiting Innocuousness in Bayesian Networks, Preprint, Australasian Joint Conference on Artificial Intelligence AI 2015: Advances in Artificial Intelligence, pp. 411-423.

Zvi Rosen and Yan X. Zhang, Convex Neural Codes in Dimension 1, arXiv:1702.06907 [math.CO], 2017. Mentions this sequence.

Index entries for sequences related to posets

Formula

a(n) = Sum((-1)^k*C(n, k)*A047863(k), k=0..n).

a(n) = Sum_{k=0..n} binomial(n, k)*(2^k-1)^(n-k). - Vladeta Jovovic, Apr 04 2003

E.g.f.: Sum_{n>=0} exp((2^n-1)*x) * x^n/n!. - Paul D. Hanna, Nov 27 2007 [correction made by Paul D. Hanna, Mar 08 2021]

O.g.f.: Sum_{n>=0} x^n/(1 - (2^n - 1)*x)^(n+1) = Sum_{n>=0} a(n)*x^n. - Paul D. Hanna, Sep 15 2009

a(n) ~ c * 2^(n^2/4 + n + 1/2) / sqrt(Pi*n), where c = JacobiTheta3(0,1/2) = EllipticTheta[3, 0, 1/2] = 2.1289368272118771586694585485449... if n is even, and c = JacobiTheta2(0,1/2) = EllipticTheta[2, 0, 1/2] = 2.1289312505130275585916134025753... if n is odd. - Vaclav Kotesovec, Mar 10 2014

Example

1 + x + 3*x^2 + 13*x^3 + 87*x^4 + 841*x^5 + 11643*x^6 + 227893*x^7 + ...

Maple

A001831 := proc(n)
    add(binomial(n, k)*(2^k-1)^(n-k), k=0..n) ;
end proc:
seq(A001831(n), n=0..10) ; # R. J. Mathar, Mar 08 2021

Mathematica

Join[{1}, Table[Sum[Binomial[n, k](2^k-1)^(n-k), {k, n}], {n, 20}]] (* Harvey P. Dale, Jan 05 2012 *)

Prog

(PARI) {a(n)=n!*polcoeff(sum(k=0, n, exp((2^k-1)*x)*x^k/k!), n)} \\ Paul D. Hanna, Nov 27 2007
(PARI) {a(n)=polcoeff(sum(k=0, n, x^k/(1-(2^k-1)*x +x*O(x^n))^(k+1)), n)} \\ Paul D. Hanna, Sep 15 2009

Crossrefs

Cf. A002031, A047863, A052332, A001833, A048194.

Row sums of A052296.

Cf. variants: A135753, A135754.

Sequence in context: A300701 A174278 A352121 * A196561 A244755 A002725

Adjacent sequences: A001828 A001829 A001830 * A001832 A001833 A001834

Keyword

nonn,nice

Author

N. J. A. Sloane

Extensions

More terms, formula and comments from Christian G. Bower, Dec 15 1999

Last 4 terms corrected by Vladeta Jovovic, Apr 04 2003

Comments corrected by Joel B. Lewis, Mar 28 2011

Status

approved