[go: up one dir, main page]

login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A001831
Number of labeled graded partially ordered sets with n elements of height at most 1.
(Formerly M2956 N1194)
24
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
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.
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
Row sums of A052296.
Cf. variants: A135753, A135754.
Sequence in context: A300701 A174278 A352121 * A196561 A244755 A002725
KEYWORD
nonn,nice
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