A135079 -id:A135079 - cp's OEIS frontend

A003024 Number of acyclic digraphs (or DAGs) with n labeled nodes.

1, 1, 3, 25, 543, 29281, 3781503, 1138779265, 783702329343, 1213442454842881, 4175098976430598143, 31603459396418917607425, 521939651343829405020504063, 18676600744432035186664816926721, 1439428141044398334941790719839535103, 237725265553410354992180218286376719253505

Offset: 0

N. J. A. Sloane

Also the number of n X n real (0,1)-matrices with all eigenvalues positive. - Conjectured by Eric W. Weisstein, Jul 10 2003 and proved by McKay et al. 2003, 2004
Also the number of n X n real (0,1)-matrices with permanent equal to 1, up to permutation of rows/columns, cf. A089482. - Vladeta Jovovic, Oct 28 2009
Also the number of nilpotent elements in the semigroup of binary relations on [n]. - Geoffrey Critzer, May 26 2022
From Gus Wiseman, Jan 01 2024: (Start)
Also the number of sets of n nonempty subsets of {1..n} such that there is a unique way to choose a different element from each. For example, non-isomorphic representatives of the a(3) = 25 set-systems are:
  {{1},{2},{3}}
  {{1},{2},{1,3}}
  {{1},{2},{1,2,3}}
  {{1},{1,2},{1,3}}
  {{1},{1,2},{2,3}}
  {{1},{1,2},{1,2,3}}
These set-systems have ranks A367908, subset of A367906, for multisets A368101.
The version for no ways is A368600, any length A367903, ranks A367907.
The version for at least one way is A368601, any length A367902.
(End)

			For n = 2 the three (0,1)-matrices are {{{1, 0}, {0, 1}}, {{1, 0}, {1, 1}}, {{1, 1}, {0, 1}}}.

Archer, K., Gessel, I. M., Graves, C., & Liang, X. (2020). Counting acyclic and strong digraphs by descents. Discrete Mathematics, 343(11), 112041.
S. R. Finch, Mathematical Constants, Cambridge, 2003, p. 310.
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 19, Eq. (1.6.1).
R. W. Robinson, Counting labeled acyclic digraphs, pp. 239-273 of F. Harary, editor, New Directions in the Theory of Graphs. Academic Press, NY, 1973.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
R. P Stanley, Enumerative Combinatorics I, 2nd. ed., p. 322.

Alois P. Heinz, Table of n, a(n) for n = 0..77 (first 41 terms from T. D. Noe)
T. E. Allen, J. Goldsmith, and N. Mattei, Counting, Ranking, and Randomly Generating CP-nets, 2014.
Huantian Cao, AutoGF: An Automated System to Calculate Coefficients of Generating Functions, thesis, 2002.
Huantian Cao, AutoGF: An Automated System to Calculate Coefficients of Generating Functions, thesis, 2002 [Local copy, with permission]
Eunice Y.-J. Chen, A. Choi, and A. Darwiche, On Pruning with the MDL Score, JMLR: Workshop and Conference Proceedings vol 52, 98-109, 2016.
S. Engstrom, Random acyclic orientations of graphs, Master's thesis written at the department of Mathematics at the Royal Institute of Technology (KTH) in Stockholm, Jan. 2013.
Zehao Jin, Mario Pasquato, Benjamin L. Davis, Tristan Deleu, Yu Luo, Changhyun Cho, Pablo Lemos, Laurence Perreault-Levasseur, Yoshua Bengio, Xi Kang, Andrea Valerio Maccio, and Yashar Hezaveh, A Data-driven Discovery of the Causal Connection between Galaxy and Black Hole Evolution, arXiv:2410.00965 [astro-ph.GA], 2024. See p. 33.
Zehao Jin, Mario Pasquato, Benjamin L. Davis, Andrea V. Macciò, and Yashar Hezaveh, Beyond Causal Discovery for Astronomy: Learning Meaningful Representations with Independent Component Analysis, arXiv:2410.14775 [astro-ph.GA], 2024. See pp. 2, 4, 10.
Zehao Jin, Mario Pasquato, Benjamin L. Davis, Tristan Deleu, Yu Luo, Changhyun Cho, Pablo Lemos, Laurence Perreault-Levasseur, Yoshua Bengio, and Xi Kang, Causal Discovery in Astrophysics: Unraveling Supermassive Black Hole and Galaxy Coevolution, Astrophys. J. (2025) Vol. 979, 212. See 4.1.
P. L. Krapivsky, Hiring Strategies, arXiv:2412.10490 [cs.GT], 2024. See p. 12.
Qipeng Kuang, Ondřej Kuželka, Yuanhong Wang, and Yuyi Wang, Bridging Weighted First Order Model Counting and Graph Polynomials, arXiv:2407.11877 [cs.LO], 2024. See p. 33.
Jack Kuipers and Giusi Moffa, Uniform generation of random acyclic digraphs, arXiv preprint arXiv:1202.6590 [stat.CO], 2012. - _N. J. A. Sloane_, Sep 14 2012
Laphou Lao, Zecheng Li, Songlin Hou, Bin Xiao, Songtao Guo, and Yuanyuan Yang, A Survey of IoT Applications in Blockchain Systems: Architecture, Consensus and Traffic Modeling, ACM Computing Surveys (CSUR, 2020) Vol. 53, No. 1, Article No. 18.
Tobias Ellegaard Larsen, Claus Thorn Ekstrøm, and Anne Helby Petersen, Score-Based Causal Discovery with Temporal Background Information, arXiv:2502.06232 [stat.ME], 2025. See p. 9.
Daniel Mallia, Towards an Unsupervised Bayesian Network Pipeline for Explainable Prediction, Decision Making and Discovery, Master's Thesis, CUNY Hunter College (2023).
B. D. McKay, F. E. Oggier, G. F. Royle, N. J. A. Sloane, I. M. Wanless and H. S. Wilf, Acyclic digraphs and eigenvalues of (0,1)-matrices, J. Integer Sequences, 7 (2004), #04.3.3.
B. D. McKay, F. E. Oggier, G. F. Royle, N. J. A. Sloane, I. M. Wanless and H. S. Wilf, Acyclic digraphs and eigenvalues of (0,1)-matrices, arXiv:math/0310423 [math.CO], Oct 28 2003.
A. Motzek and R. Möller, Exploiting Innocuousness in Bayesian Networks, Preprint 2015.
Yisu Peng, Y. Jiang, and P. Radivojac, Enumerating consistent subgraphs of directed acyclic graphs: an insight into biomedical ontologies, arXiv preprint arXiv:1712.09679 [cs.DS], 2017.
J. Peters, J. Mooij, D. Janzing, and B. Schölkopf, Causal Discovery with Continuous Additive Noise Models, arXiv preprint arXiv:1309.6779 [stat.ML], 2013.
R. W. Robinson, Enumeration of acyclic digraphs, Manuscript. (Annotated scanned copy)
V. I. Rodionov, On the number of labeled acyclic digraphs, Disc. Math. 105 (1-3) (1992) 319-321
I. Shpitser, T. S. Richardson, J. M. Robins and R. Evans, Parameter and Structure Learning in Nested Markov Models, arXiv preprint arXiv:1207.5058 [stat.ML], 2012.
I. Shpitser, R. J. Evans, T. S. Richardson, and J. M. Robins, Introduction to nested Markov models, Behaviormetrika, Behaviormetrika Vol. 41, No. 1, 2014, 3-39.
R. P. Stanley, Acyclic orientation of graphs, Discrete Math. 5 (1973), 171-178. North Holland Publishing Company.
Christian Toth, Christian Knoll, Franz Pernkopf, and Robert Peharz, Rao-Blackwellising Bayesian Causal Inference, arXiv:2402.14781 [cs.LG], 2024.
Sumanth Varambally, Yi-An Ma, and Rose Yu, Discovering Mixtures of Structural Causal Models from Time Series Data, arXiv:2310.06312 [cs.LG], 2023.
S. Wagner, Asymptotic enumeration of extensional acyclic digraphs, in Proceedings of the SIAM Meeting on Analytic Algorithmics and Combinatorics (ANALCO12).
Daniel Waxman, Kurt Butler, and Petar M. Djuric, Dagma-DCE: Interpretable, Non-Parametric Differentiable Causal Discovery, arXiv:2401.02930 [cs.LG], 2024.
Eric Weisstein's World of Mathematics, (0,1)-Matrix
Eric Weisstein's World of Mathematics, Acyclic Digraph
Eric Weisstein's World of Mathematics, Positive Eigenvalued Matrix
Eric Weisstein's World of Mathematics, Weisstein's Conjecture
Jun Wu and Mathias Drton, Partial Homoscedasticity in Causal Discovery with Linear Models, arXiv:2308.08959 [math.ST], 2023.
Chris Ying, Enumerating Unique Computational Graphs via an Iterative Graph Invariant, arXiv:1902.06192 [cs.DM], 2019.
Index entries for sequences related to binary matrices

Cf. A086510, A081064 (refined by # arcs), A307049 (by # descents).
Cf. A055165, which counts nonsingular {0, 1} matrices and A085656, which counts positive definite {0, 1} matrices.
Cf. A188457, A135079, A137435 (acyclic 3-multidigraphs), A188490.
For a unique sink we have A003025.
The unlabeled version is A003087.
These are the reverse-alternating sums of rows of A046860.
The weakly connected case is A082402.
A reciprocal version is A334282.
Row sums of A361718.
Cf. A003465, A058877, A058891, A059201, A088957, A133686, A323818.

p:=evalf(solve(sum((-1)^n*x^n/(n!*2^(n*(n-1)/2)), n=0..infinity) = 0, x), 50); M:=evalf(sum((-1)^(n+1)*p^n/((n-1)!*2^(n*(n-1)/2)), n=1..infinity), 40); # program for evaluation of constants p and M in the asymptotic formula, Vaclav Kotesovec, Dec 09 2013

a[0] = a[1] = 1; a[n_] := a[n] = Sum[ -(-1)^k * Binomial[n, k] * 2^(k*(n-k)) * a[n-k], {k, 1, n}]; Table[a[n], {n, 0, 13}](* Jean-François Alcover, May 21 2012, after PARI *)
Table[2^(n*(n-1)/2)*n! * SeriesCoefficient[1/Sum[(-1)^k*x^k/k!/2^(k*(k-1)/2),{k,0,n}],{x,0,n}],{n,0,20}] (* Vaclav Kotesovec, May 19 2015 *)
Table[Length[Select[Subsets[Subsets[Range[n]],{n}],Length[Select[Tuples[#],UnsameQ@@#&]]==1&]],{n,0,5}] (* Gus Wiseman, Jan 01 2024 *)

a(n)=if(n<1,n==0,sum(k=1,n,-(-1)^k*binomial(n,k)*2^(k*(n-k))*a(n-k)))

{a(n)=polcoeff(1-sum(k=0, n-1, a(k)*x^k/(1+2^k*x+x*O(x^n))^(k+1)), n)} \\ Paul D. Hanna, Oct 17 2009

a(0) = 1; for n > 0, a(n) = Sum_{k=1..n} (-1)^(k+1)*C(n, k)*2^(k*(n-k))*a(n-k).
1 = Sum_{n>=0} a(n)*exp(-2^n*x)*x^n/n!. - Vladeta Jovovic, Jun 05 2005
a(n) = Sum_{k=1..n} (-1)^(n-k)*A046860(n,k) = Sum_{k=1..n} (-1)^(n-k)*k!*A058843(n,k). - Vladeta Jovovic, Jun 20 2008
1 = Sum_{n=>0} a(n)*x^n/(1 + 2^n*x)^(n+1). - Paul D. Hanna, Oct 17 2009
1 = Sum_{n>=0} a(n)*C(n+m-1,n)*x^n/(1 + 2^n*x)^(n+m) for m>=1. - Paul D. Hanna, Apr 01 2011
log(1+x) = Sum_{n>=1} a(n)*(x^n/n)/(1 + 2^n*x)^n. - Paul D. Hanna, Apr 01 2011
Let E(x) = Sum_{n >= 0} x^n/(n!*2^C(n,2)). Then a generating function for this sequence is 1/E(-x) = Sum_{n >= 0} a(n)*x^n/(n!*2^C(n,2)) = 1 + x + 3*x^2/(2!*2) + 25*x^3/(3!*2^3) + 543*x^4/(4!*2^6) + ... (Stanley). Cf. A188457. - Peter Bala, Apr 01 2013
a(n) ~ n!*2^(n*(n-1)/2)/(M*p^n), where p = 1.488078545599710294656246... is the root of the equation Sum_{n>=0} (-1)^n*p^n/(n!*2^(n*(n-1)/2)) = 0, and M = Sum_{n>=1} (-1)^(n+1)*p^n/((n-1)!*2^(n*(n-1)/2)) = 0.57436237330931147691667... Both references to the article "Acyclic digraphs and eigenvalues of (0,1)-matrices" give the wrong value M=0.474! - Vaclav Kotesovec, Dec 09 2013 [Response from N. J. A. Sloane, Dec 11 2013: The value 0.474 has a typo, it should have been 0.574. The value was taken from Stanley's 1973 paper.]
exp( Sum_{n >= 1} a(n)*x^n/n ) = 1 + x + 2*x^2 + 10*x^3 + 146*x^4 + 6010*x^5 + ... appears to have integer coefficients (cf. A188490). - Peter Bala, Jan 14 2016

A047863 Number of labeled graphs with 2-colored nodes where black nodes are only connected to white nodes and vice versa.

Original entry on oeis.org

1, 2, 6, 26, 162, 1442, 18306, 330626, 8488962, 309465602, 16011372546, 1174870185986, 122233833963522, 18023122242478082, 3765668654914699266, 1114515608405262434306, 467221312005126294077442, 277362415313453291571118082, 233150477220213193598856331266

Offset: 0

N. J. A. Sloane

Row sums of A111636. - Peter Bala, Sep 30 2012
Column 2 of Table 2 in Read. - Peter Bala, Apr 11 2013
It appears that 5 does not divide a(n), that a(n) is even for n>0, that 3 divides a(2n) for n>0, that 7 divides a(6n+5), and that 13 divides a(12n+3). - Ralf Stephan, May 18 2013

			For n=2, {1,2 black, not connected}, {1,2 white, not connected}, {1 black, 2 white, not connected}, {1 black, 2 white, connected}, {1 white, 2 black, not connected}, {1 white, 2 black, connected}.
G.f. = 1 + 2*x + 6*x^2 + 26*x^3 + 162*x^4 + 1442*x^5 + 18306*x^6 + ...

H. S. Wilf, Generatingfunctionology, Academic Press, NY, 1990, p. 79, Eq. 3.11.2.

T. D. Noe, Table of n, a(n) for n = 0..50
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
S. R. Finch, Bipartite, k-colorable and k-colored graphs
S. R. Finch, Bipartite, k-colorable and k-colored graphs, June 5, 2003. [Cached copy, with permission of the author]
A. Gainer-Dewar and I. M. Gessel, Enumeration of bipartite graphs and bipartite blocks, arXiv:1304.0139 [math.CO], 2013.
D. A. Klarner, The number of graded partially ordered sets, J. Combin. Theory, 6 (1969), 12-19. [Annotated scanned copy]
Y. Puri and T. Ward, Arithmetic and growth of periodic orbits, J. Integer Seqs., Vol. 4 (2001), #01.2.1.
R. C. Read, The number of k-colored graphs on labelled nodes, Canad. J. Math., 12 (1960), 410-414.
R. P. Stanley, Acyclic orientation of graphs Discrete Math. 5 (1973), 171-178. North Holland Publishing Company.
Martin Svatoš, Peter Jung, Jan Tóth, Yuyi Wang, and Ondřej Kuželka, On Discovering Interesting Combinatorial Integer Sequences, arXiv:2302.04606 [cs.LO], 2023, p. 17.
Eric Weisstein's World of Mathematics, k-Colorable Graph
H. S. Wilf, Generatingfunctionology, 2nd edn., Academic Press, NY, 1994, p. 88, Eq. 3.11.2.

Column k=2 of A322280.
Cf. A135079 (variant).
Cf. A000683, A001831, A002031, A033995, A047864, A052332, A111636, A191371, A223887.

A047863:= func< n | (&+[Binomial(n,k)*2^(k*(n-k)): k in [0..n]]) >;
[A047863(n): n in [0..40]]; // G. C. Greubel, Nov 03 2024

Table[Sum[Binomial[n,k]2^(k(n-k)),{k,0,n}],{n,0,20}] (* Harvey P. Dale, May 09 2012 *)
nmax = 20; CoefficientList[Series[Sum[E^(2^k*x)*x^k/k!, {k, 0, nmax}], {x, 0, nmax}], x] * Range[0, nmax]! (* Vaclav Kotesovec, Jun 05 2019 *)

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

{a(n)=polcoeff(sum(k=0, n, x^k/(1-2^k*x +x*O(x^n))^(k+1)), n)} \\ Paul D. Hanna, Mar 08 2008

N=66; x='x+O('x^N); egf = sum(n=0, N, exp(2^n*x)*x^n/n!);
Vec(serlaplace(egf))  \\ Joerg Arndt, May 04 2013

from sympy import binomial
def a(n): return sum([binomial(n, k)*2**(k*(n - k)) for k in range(n + 1)]) # Indranil Ghosh, Jun 03 2017

def A047863(n): return sum(binomial(n,k)*2^(k*(n-k)) for k in range(n+1))
[A047863(n) for n in range(41)] # G. C. Greubel, Nov 03 2024

a(n) = Sum_{k=0..n} binomial(n, k)*2^(k*(n-k)).
a(n) = 4 * A000683(n) + 2. - Vladeta Jovovic, Feb 02 2000
E.g.f.: Sum_{n>=0} exp(2^n*x)*x^n/n!. - Paul D. Hanna, Nov 27 2007
O.g.f.: Sum_{n>=0} x^n/(1 - 2^n*x)^(n+1). - Paul D. Hanna, Mar 08 2008
From Peter Bala, Apr 11 2013: (Start)
Let E(x) = Sum_{n >= 0} x^n/(n!*2^C(n,2)) = 1 + x + x^2/(2!*2) + x^3/(3!*2^3) + .... Then a generating function is E(x)^2 = 1 + 2*x + 6*x^2/(2!*2) + 26*x^3/(3!*2^3) + .... In general, E(x)^k, k = 1, 2, ..., is a generating function for labeled k-colored graphs (see Stanley). For other examples see A191371 (k = 3) and A223887 (k = 4).
If A(x) = 1 + 2*x + 6*x^2/2! + 26*x^3/3! + ... denotes the e.g.f. for this sequence then sqrt(A(x)) = 1 + x + 2*x^2/2! + 7*x^3/3! + ... is the e.g.f. for A047864, which counts labeled 2-colorable graphs. (End)
a(n) ~ c * 2^(n^2/4+n+1/2)/sqrt(Pi*n), where c = Sum_{k = -infinity..infinity} 2^(-k^2) = EllipticTheta[3, 0, 1/2] = 2.128936827211877... if n is even and c = Sum_{k = -infinity..infinity} 2^(-(k+1/2)^2) = EllipticTheta[2, 0, 1/2] = 2.12893125051302... if n is odd. - Vaclav Kotesovec, Jun 24 2013

Better description from Christian G. Bower, Dec 15 1999

A188457 G.f.: 1 = Sum_{n>=0} a(n)x^n/(1 + 3^nx)^(n+1).

Original entry on oeis.org

1, 1, 5, 109, 9449, 3068281, 3586048685, 14668583277349, 205716978569685329, 9737002299093315531121, 1536239893108209683958428885, 799846636937376803320381186364509, 1362900713950636674946135205457794784569

Offset: 0

Paul D. Hanna, Mar 31 2011

G.f. satisfies a variant of an identity involving A003024:
1 = Sum_{n>=0} A003024(n)*x^n/(1 + 2^n*x)^(n+1),
where A003024(n) is the number of acyclic digraphs with n labeled nodes.
a(n) is the number of acyclic 2-multidigraphs. Cf. A137435, A339768. - Geoffrey Critzer, Feb 21 2021

			Illustration of the generating functions.
E.g.f.: 1 = exp(-x) + exp(-3*x)*x + 5*exp(-9*x)*x^2/2! + 109*exp(-27*x)*x^3/3! +...
L.g.f.: log(1+x) = x/(1+3*x) + 5*(x^2/2)/(1+9*x)^2 + 109*(x^3/3)/(1+27*x)^3 +...
G.f.: 1 = 1/(1+x) + 1*x/(1+3*x)^2 + 5*x^2/(1+9*x)^3 + 109*x^3/(1+27*x)^4 +...
G.f.: 1 = 1/(1+x)^2 + 1*2*x/(1+3*x)^3 + 5*3*x^2/(1+9*x)^4 + 109*4*x^3/(1+27*x)^5 +...
G.f.: 1 = 1/(1+x)^3 + 1*3*x/(1+3*x)^4 + 5*6*x^2/(1+9*x)^5 + 109*10*x^3/(1+27*x)^6 +...

Seiichi Manyama, Table of n, a(n) for n = 0..62

Cf. A003024, A137435, A188456, A188455, A135079.

Cf. A137435, A339768.

a[n_] := a[n] = If[n == 0, 1, Sum[-(-1)^k Binomial[n, k] 3^(k(n-k)) a[n-k], {k, 1, n}]];
a /@ Range[0, 12] (* Jean-François Alcover, Nov 02 2019 *)

{a(n)=polcoeff(1-sum(k=0, n-1, a(k)*x^k/(1+3^k*x+x*O(x^n))^(k+1)), n)}
for(n=0,20, print1(a(n),", "))

/* Holds for m>=1: */
{a(n)=local(m=1);polcoeff(1-sum(k=0, n-1, a(k)*binomial(m+k-1,k)*x^k/(1+3^k*x+x*O(x^n))^(k+m)), n)/binomial(m+n-1,n)}
for(n=0,20, print1(a(n),", "))

/* Recurrence: */
{a(n)=if(n<1, n==0, sum(k=1, n, -(-1)^k*binomial(n, k)*3^(k*(n-k))*a(n-k)))}
for(n=0,20, print1(a(n),", "))

/* E.g.f.: */
{a(n)=n!*polcoeff(1-sum(k=0, n-1, a(k)*exp(-3^k*x+x*O(x^n))*x^k/k!), n)}
for(n=0,20, print1(a(n),", "))

G.f.: 1 = Sum_{n>=0} a(n)*C(n+m-1,n)*x^n/(1 + 3^n*x)^(n+m) for m>=1.
L.g.f.: log(1+x) = Sum_{n>=1} a(n)*(x^n/n)/(1 + 3^n*x)^n.
E.g.f.: 1 = Sum_{n>=0} a(n)*exp(-3^n*x)*x^n/n!.
a(n) = Sum_{k=1..n} (-1)^(k+1)*C(n, k)*3^(k*(n-k))*a(n-k) for n>0 with a(0)=1.
From Peter Bala, Apr 01 2013: (Start)
Let E(x) = sum {n >= 0} x^n/(n!*3^C(n,2)). Then a generating function for this sequence is 1/E(-x) = sum {n >= 0} a(n)*x^n/(n!*3^C(n,2)) = 1 + x + 5*x^2/(2!*3) + 109*x^3/(3!*3^3) + 9449*x^4/(4!*3^6) + .... (End)
exp( Sum_{n >= 1} a(n)*x^n/n ) = 1 + x + 3*x^2 + 39*x^3 + 2403*x^4 + 616131*x^5 + ... appears to have integer coefficients. - Peter Bala, Jan 14 2016

A244755 a(n) = Sum_{k=0..n} C(n,k) * (1 + 3^k)^(n-k).

Original entry on oeis.org

1, 3, 13, 87, 985, 19563, 697573, 44195007, 4985202865, 987432857043, 344306650353853, 209169206074748967, 222262777197258910345, 409907753371580011362363, 1317924525238880964004945813, 7341603216747343890845790989967, 71176841502529490992224798115792225

Offset: 0

Paul D. Hanna, Jul 05 2014

nonn

			E.g.f.: A(x) = 1 + 3*x + 13*x^2/2! + 87*x^3/3! + 985*x^4/4! + 19563*x^5/5! +...
ILLUSTRATION OF INITIAL TERMS:
a(1) = (1+3^0)^1 + (1+3^1)^0 = 3;
a(2) = (1+3^0)^2 + 2*(1+3^1)^1 + (1+3^2)^0 = 13;
a(3) = (1+3^0)^3 + 3*(1+3^1)^2 + 3*(1+3^2)^1 + (1+3^3)^0 = 87;
a(4) = (1+3^0)^4 + 4*(1+3^1)^3 + 6*(1+3^2)^2 + 4*(1+3^3)^1 + (1+3^4)^0 = 985; ...

G. C. Greubel, Table of n, a(n) for n = 0..90

Cf. A244754, A244756, A244760, A135079, A243918.

Table[Sum[Binomial[n,k] * (1 + 3^k)^(n-k),{k,0,n}],{n,0,20}] (* Vaclav Kotesovec, Jan 25 2015 *)

{a(n) = sum(k=0,n,binomial(n,k) * (1 + 3^k)^(n-k) )}
for(n=0,25,print1(a(n),", "))

/* E.g.f. Sum_{n>=0} exp((1+3^n)*x)*x^n/n!" */
{a(n)=n!*polcoeff(sum(k=0, n, exp((1+3^k)*x +x*O(x^n))*x^k/k!), n)}
for(n=0,25,print1(a(n),", "))

/* O.g.f. Sum_{n>=0} x^n/(1 - (1+3^n)*x)^(n+1): */
{a(n)=polcoeff(sum(k=0, n, x^k/(1-(1+3^k)*x +x*O(x^n))^(k+1)), n)}
for(n=0,25,print1(a(n),", "))

E.g.f.: Sum_{n>=0} exp((1+3^n)*x) * x^n/n!.
O.g.f.: Sum_{n>=0} x^n/(1 - (1+3^n)*x)^(n+1).
a(n) ~ c * 3^(n^2/4) * 2^(n+1/2) / sqrt(Pi*n), where c = JacobiTheta3(0,1/3) = EllipticTheta[3, 0, 1/3] = 1.69145968168171534134842... if n is even, and c = JacobiTheta2(0,1/3) = EllipticTheta[2, 0, 1/3] = 1.69061120307521423305296... if n is odd. - Vaclav Kotesovec, Jan 25 2015

A193198 G.f.: A(x) = Sum_{n>=0} x^n/(1 - 3^n*x)^n.

Original entry on oeis.org

1, 1, 4, 28, 352, 7696, 296704, 19845568, 2325071872, 472050401536, 167325747134464, 102717666720160768, 109887628080679616512, 203517277347030338768896, 656102983404750860283019264, 3660938644168893995628877692928

Offset: 0

Paul D. Hanna, Jul 17 2011

nonn

			G.f.: A(x) = 1 + x + 4*x^2 + 28*x^3 + 352*x^4 + 7696*x^5 +...
where:
A(x) = 1 + x/(1-3*x) + x^2/(1-9*x)^2 + x^3/(1-27*x)^3 + x^4/(1-81*x)^4 +...

Seiichi Manyama, Table of n, a(n) for n = 0..90

Cf. A000684, A135079, A193199.

{a(n)=local(A=1);A=1+sum(m=1,n,x^m/(1-3^m*x +x*O(x^n))^m);polcoeff(A,n)}

{a(n)=if(n==0,1,sum(k=0,n-1,binomial(n-1,k)*3^(k*(n-k))))}

a(n) = Sum_{k=0..n-1} binomial(n-1,k)*3^(k*(n-k)) for n>0 with a(0)=1.

A320287 a(n) = n! * [x^n] Sum_{k>=0} exp(n^kx)x^k/k!.

Original entry on oeis.org

1, 2, 6, 56, 2050, 318752, 252035714, 980755711616, 23647746367946754, 3088949241542073508352, 2940240000900000020000000002, 16218429504693724464229916894517248, 748528620411995327278028288988088683724802, 210422023062476527874650307058798916093350502080512

Offset: 0

Ilya Gutkovskiy, Oct 09 2018

nonn

G. C. Greubel, Table of n, a(n) for n = 0..48

Cf. A047863, A135079.

[(&+[Binomial(n,k)*n^(k*(n-k)):k in [0..n]]): n in [0..20]]; // G. C. Greubel, Nov 04 2018

Join[{1}, Table[n! SeriesCoefficient[Sum[Exp[n^k x] x^k/k!, {k, 0, n}], {x, 0, n}], {n, 13}]]
Join[{1}, Table[SeriesCoefficient[Sum[x^k/(1 - n^k x)^(k + 1), {k, 0, n}], {x, 0, n}], {n, 13}]]
Join[{1}, Table[Sum[Binomial[n, k] n^(k (n - k)), {k, 0, n}], {n, 13}]]

for(n=0,20, print1(sum(k=0,n, binomial(n,k)*n^(k*(n-k))), ", ")) \\ G. C. Greubel, Nov 04 2018

a(n) = [x^n] Sum_{k>=0} x^k/(1 - n^k*x)^(k+1).
a(n) = Sum_{k=0..n} binomial(n,k)*n^(k*(n-k)).
a(n) ~ 2^(n + 1/2) * n^(n^2/4 - 1/2) / sqrt(Pi) if n is even and a(n) ~ 2^(n + 3/2) * n^(n^2/4 - 3/4) / sqrt(Pi) if n is odd. - Vaclav Kotesovec, Jul 06 2022

A360933 Expansion of e.g.f. Sum_{k>=0} exp((3^k - 1)x) x^k/k!.

Original entry on oeis.org

1, 1, 5, 37, 521, 12361, 510605, 35837677, 4348414481, 903630399121, 325415100648725, 201805338104622517, 217331913727442676761, 404193405278758441895641, 1306527408146744068362681245, 7302236837745565755664036677757

Offset: 0

Seiichi Manyama, Feb 26 2023

Cf. A001831, A360934, A360935.

Cf. A135079, A135753.

my(N=20, x='x+O('x^N)); Vec(serlaplace(1+sum(k=1, N, exp((3^k-1)*x)*x^k/k!)))

my(N=20, x='x+O('x^N)); Vec(sum(k=0, N, x^k/(1-(3^k-1)*x)^(k+1)))

a(n) = sum(k=0, n, (3^k-1)^(n-k)*binomial(n, k));

G.f.: Sum_{k>=0} x^k/(1 - (3^k - 1)*x)^(k+1).

a(n) = Sum_{k=0..n} (3^k - 1)^(n-k) * binomial(n,k).

A135078 E.g.f. A(x) = 1 + Sum_{n>=1} (1/n!)Product_{k=0..n-1} [exp(3^kx) - 1].

Original entry on oeis.org

1, 1, 4, 46, 1519, 145795, 41134753, 34354750885, 85260288495316, 630102185300832652, 13884412839047621240875, 912975607895806507921828357, 179255108346123463104458490745825

Offset: 0

Paul D. Hanna, Nov 24 2007

nonn

			A(x) = 1 + x + 4x^2/2! + 46x^3/3! + 1519x^4/4! + 145795x^5/5! +...;
A(x) = 1 + [exp(x)-1] + [exp(x)-1][exp(3x)-1]/2! + [exp(x)-1][exp(3x)-1][exp(9x)-1]/3! + [exp(x)-1][exp(3x)-1][exp(9x)-1][exp(27x)-1]/4! +...

Cf. variants: A135077, A135079.

{a(n)=n!*polcoeff(1+sum(j=1,n,(1/j!)*prod(k=0,j-1,1*exp(3^k*x)-1)),n)}

A172389 a(n) = Sum_{k=0..n} C(n,k)3^(k(n-k))/2^n.

Original entry on oeis.org

1, 1, 2, 7, 44, 481, 9272, 310087, 18164624, 1843946881, 326808099872, 100310221406407, 53656068398769344, 49686835289802328801, 80090696216400251499392, 223445962168511596412895367

Offset: 0

Paul D. Hanna, Feb 03 2010

nonn

			O.g.f.: A(x) = 1 + x + 2*x^2 + 7*x^3 + 44*x^4 + 481*x^5 + 9272*x^6 +...
A(x) = 2/(2-x) + 2*x/(2-3*x)^2 + 2*x^2/(2-3^2*x)^3 + 2*x^3/(2-3^3*x)^4 +...+ 2*x^n/(2-3^n*x)^(n+1) +...
E.g.f.: E(x) = 1 + x + 2*x^2/2! + 7*x^3/3! + 44*x^4/4! + 481*x^5/5! +...
E(x) = exp(x/2) + exp(3*x/2)*x/2 + exp(3^2*x/2)*(x/2)^2/2! + exp(3^3*x/2)*(x/2)^3/3! +...+ exp(3^n*x/2)*(x/2)^n/n! +...

Cf. variants: A135079, A047863.

{a(n)=sum(k=0,n,binomial(n,k)*3^(k*(n-k)))/2^n}

{a(n)=n!*polcoeff(sum(k=0, n, exp(3^k*x/2 +x*O(x^n))*(x/2)^k/k!), n)}

{a(n)=polcoeff(sum(k=0, n, (x/2)^k/(1-3^k*x/2 +x*O(x^n))^(k+1)), n)}

O.g.f.: A(x) = Sum_{n>=0} 2*x^n/(2 - 3^n*x)^(n+1).
E.g.f.: E(x) = Sum_{n>=0} exp(3^n*x/2)*(x/2)^n/n!.
a(n) = A135079(n)/2^n.

A355395 Square array T(n,k), n >= 0, k >= 0, read by antidiagonals downwards, where T(n,k) = Sum_{j=0..n} k^(j(n-j)) binomial(n,j).

Original entry on oeis.org

1, 1, 2, 1, 2, 2, 1, 2, 4, 2, 1, 2, 6, 8, 2, 1, 2, 8, 26, 16, 2, 1, 2, 10, 56, 162, 32, 2, 1, 2, 12, 98, 704, 1442, 64, 2, 1, 2, 14, 152, 2050, 15392, 18306, 128, 2, 1, 2, 16, 218, 4752, 84482, 593408, 330626, 256, 2, 1, 2, 18, 296, 9506, 318752, 7221250, 39691136, 8488962, 512, 2

Offset: 0

Seiichi Manyama, Jul 02 2022

The Stanley reference below describes a family of binomial posets whose elements are two colored graphs with vertices labeled on [n] and with edges labeled on [k-1]. T(n,k) is the number of elements in an n-interval of such a binomial poset. - Geoffrey Critzer, Aug 21 2023

			Square array begins:
  1,  1,    1,     1,     1,      1, ...
  2,  2,    2,     2,     2,      2, ...
  2,  4,    6,     8,    10,     12, ...
  2,  8,   26,    56,    98,    152, ...
  2, 16,  162,   704,  2050,   4752, ...
  2, 32, 1442, 15392, 84482, 318752, ...

R. P. Stanley, Enumerative Combinatorics, Volume 1, Second Edition, Example 3.18.3(e), page 323.

Columns k=0..4 give A040000, A000079, A047863, A135079, A355440.
Main diagonal gives A320287.
Cf. A009999.

T(n, k) = sum(j=0, n, k^(j*(n-j))*binomial(n, j));

E.g.f. of column k: Sum_{j>=0} exp(k^j * x) * x^j/j!.
G.f. of column k: Sum_{j>=0} x^j/(1 - k^j * x)^(j+1).
For k>=1, E(x)^2 = Sum_{n>=0} T(n,k)*x^n/B_k(n) where B_k(n) = n!*k^binomial(n,2) and E(x) = Sum_{n>=0} x^n/b_k(n). - Geoffrey Critzer, Aug 21 2023

cp's OEIS Frontend

A003024 Number of acyclic digraphs (or DAGs) with n labeled nodes.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

A047863 Number of labeled graphs with 2-colored nodes where black nodes are only connected to white nodes and vice versa.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Mathematica

PARI

PARI

PARI

Python

SageMath

Formula

Extensions

A188457 G.f.: 1 = Sum_{n>=0} a(n)*x^n/(1 + 3^n*x)^(n+1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

PARI

PARI

Formula

A244755 a(n) = Sum_{k=0..n} C(n,k) * (1 + 3^k)^(n-k).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

PARI

Formula

A193198 G.f.: A(x) = Sum_{n>=0} x^n/(1 - 3^n*x)^n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

PARI

Formula

A320287 a(n) = n! * [x^n] Sum_{k>=0} exp(n^k*x)*x^k/k!.

Views

Author

Keywords

Links

Crossrefs

A188457 G.f.: 1 = Sum_{n>=0} a(n)x^n/(1 + 3^nx)^(n+1).

A320287 a(n) = n! * [x^n] Sum_{k>=0} exp(n^kx)x^k/k!.

A360933 Expansion of e.g.f. Sum_{k>=0} exp((3^k - 1)x) x^k/k!.

A135078 E.g.f. A(x) = 1 + Sum_{n>=1} (1/n!)Product_{k=0..n-1} [exp(3^kx) - 1].

A172389 a(n) = Sum_{k=0..n} C(n,k)3^(k(n-k))/2^n.

A355395 Square array T(n,k), n >= 0, k >= 0, read by antidiagonals downwards, where T(n,k) = Sum_{j=0..n} k^(j(n-j)) binomial(n,j).