A001831 Number of labeled graded partially ordered sets with n elements of height at most 1.

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

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• nice

Comments

Labeled posets where for all a,b,c in the set, do not have a

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

Examples

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

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

Crossrefs

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

Row sums of A052296.

Cf. variants: A135753, A135754.

Programs

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 *)

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

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

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

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.