A058877 -id:A058877 - 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

A003025 Number of n-node labeled acyclic digraphs with 1 out-point.

Original entry on oeis.org

1, 2, 15, 316, 16885, 2174586, 654313415, 450179768312, 696979588034313, 2398044825254021110, 18151895792052235541515, 299782788128536523836784628, 10727139906233315197412684689421

Offset: 1

N. J. A. Sloane

nonn

From Gus Wiseman, Jan 02 2024: (Start)
Also the number of n-element sets of finite nonempty subsets of {1..n}, including a unique singleton, such that there is exactly one way to choose a different element from each. For example, the a(0) = 0 through a(3) = 15 set-systems are:
  .  {{1}}  {{1},{1,2}}  {{1},{1,2},{1,3}}
            {{2},{1,2}}  {{1},{1,2},{2,3}}
                         {{1},{1,3},{2,3}}
                         {{2},{1,2},{1,3}}
                         {{2},{1,2},{2,3}}
                         {{2},{1,3},{2,3}}
                         {{3},{1,2},{1,3}}
                         {{3},{1,2},{2,3}}
                         {{3},{1,3},{2,3}}
                         {{1},{1,2},{1,2,3}}
                         {{1},{1,3},{1,2,3}}
                         {{2},{1,2},{1,2,3}}
                         {{2},{2,3},{1,2,3}}
                         {{3},{1,3},{1,2,3}}
                         {{3},{2,3},{1,2,3}}
These set-systems are all connected.
The case of labeled graphs is A000169.
(End)

			a(2) = 2: o-->--o (2 ways)
a(3) = 15: o-->--o-->--o (6 ways) and
o ... o o-->--o
.\ . / . \ . /
. v v ... v v
.. o ..... o
(3 ways) (6 ways)

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

Andrew Howroyd, Table of n, a(n) for n = 1..50
Marcel et al., Is there a formula for the number of st-dags (DAG with 1 source and 1 sink) with n vertices?, MathOverflow, 2021.

A diagonal of A058876.
Row sums of A350487.
The unlabeled version is A350415.
Column k=1 of A361718.
Cf. A003026, A003028, A345258.
For any number of sinks we have A003024, unlabeled A003087.
For n-1 sinks we have A058877.
For a fixed sink we have A134531 (up to sign), column k=1 of A368602.
Cf. A000169, A058891, A059201, A082402, A088957, A323818, A334282, A367904, A368600, A368601.

Table[Length[Select[Subsets[Subsets[Range[n]],{n}],Count[#,{}]==1&&Length[Select[Tuples[#],UnsameQ@@#&]]==1&]],{n,0,4}] (* _Gus Wiseman, Jan 02 2024 *)

\\ requires A058876.
my(T=A058876(20)); vector(#T, n, T[n][1]) \\ Andrew Howroyd, Dec 27 2021

\\ see Marcel et al. link (formula for a').
seq(n)={my(a=vector(n)); a[1]=1; for(n=2, #a, a[n]=sum(k=1, n-1, (-1)^(k-1) * binomial(n,k) * (2^(n-k)-1)^k * a[n-k])); a} \\ Andrew Howroyd, Jan 01 2022

a(n) = (-1)^(n-1) * n * A134531(n). - Gus Wiseman, Jan 02 2024

More terms from Vladeta Jovovic, Apr 10 2001

A062111 Upper-right triangle resulting from binomial transform calculation for nonnegative integers.

Original entry on oeis.org

0, 1, 1, 4, 3, 2, 12, 8, 5, 3, 32, 20, 12, 7, 4, 80, 48, 28, 16, 9, 5, 192, 112, 64, 36, 20, 11, 6, 448, 256, 144, 80, 44, 24, 13, 7, 1024, 576, 320, 176, 96, 52, 28, 15, 8, 2304, 1280, 704, 384, 208, 112, 60, 32, 17, 9, 5120, 2816, 1536, 832, 448, 240, 128, 68, 36, 19, 10

Offset: 0

Henry Bottomley, May 30 2001

From Philippe Deléham, Apr 15 2007: (Start)
This triangle can be found in the Laisant reference in the following form:
  .......................5...11..
  ...................4...9...20..
  ...............3...7..16...36..
  ...........2...5..12..28.......
  .......1...3...8..20..48.......
  ...0...1...4..12..32..80....... (End)
Triangle A152920 reversed. - Philippe Deléham, Apr 21 2009

			As a lower triangle (T(n, k)):
    0;
    1,   1;
    4,   3,   2;
   12,   8,   5,  3;
   32,  20,  12,  7,  4;
   80,  48,  28, 16,  9,  5;
  192, 112,  64, 36, 20, 11,  6;
  448, 256, 144, 80, 44, 24, 13, 7;

G. C. Greubel, Rows n = 0..50 of the triangle, flattened
F. Ellermann, Illustration of binomial transforms
C.-A. Laisant, Sur les tableaux de sommes - Nouvelles applications, Compt. Rendus de l'Association Francaise pour l'Avancement des Sciences, Aout 04 1893, pp. 206-216 (table given on p. 212).

Rows include (essentially) A001787, A001792, A034007, A045623, A045891.
Diagonals include (essentially) A001477, A005408, A008586, A008598, A017113.
Column sums are A058877.
Cf. A111297, A159694, A159695, A159696, A159697. - Philippe Deléham, Apr 21 2009
Cf. A058877, A073371, A130129, A152920.

[2^(n-k-1)*(n+k): k in [0..n], n in [0..12]]; // G. C. Greubel, Sep 28 2022

Table[2^(n-k-1)*(n+k), {n,0,12}, {k,0,n}]//Flatten (* G. C. Greubel, Sep 28 2022 *)

def A062111(n,k): return 2^(n-k-1)*(n+k)
flatten([[A062111(n,k) for k in range(n+1)] for n in range(12)]) # G. C. Greubel, Sep 28 2022

A(n, k) = A(n, k-1) + A(n+1, k) if k > n with A(n, n) = n.
A(n, k) = (k+n)*2^(k-n-1) if k >= n.
T(2*n, n) = 3*n*2^(n-1) = 3*A001787(n). - Philippe Deléham, Apr 21 2009
From G. C. Greubel, Sep 28 2022: (Start)
T(n, k) = 2^(n-k-1)*(n+k) for 0 <= k <= n, n >= 0.
T(m*n, n) = 2^((m-1)*n-1)*(m+1)*A001477(n), m >= 1.
T(2*n-1, n-1) = A130129(n-1).
T(2*n+1, n-1) = 12*A001787(n).
Sum_{k=0..n} T(n, k) = A058877(n+1).
Sum_{k=0..n} (-1)^k*T(n, k) = 3*A073371(n-2), n >= 2.
T(n, k) = A152920(n, n-k). (End)

A152920 Triangle read by rows: triangle A062111 reversed.

Original entry on oeis.org

0, 1, 1, 2, 3, 4, 3, 5, 8, 12, 4, 7, 12, 20, 32, 5, 9, 16, 28, 48, 80, 6, 11, 20, 36, 64, 112, 192, 7, 13, 24, 44, 80, 144, 256, 448, 8, 15, 28, 52, 96, 176, 320, 576, 1024, 9, 17, 32, 60, 112, 208, 384, 704, 1280, 2304, 10, 19, 36, 68, 128, 240, 448, 832, 1536, 2816, 5120

Offset: 0

Paul Curtz, Dec 15 2008

			Triangle starts:
  0;
  1,  1;
  2,  3,  4;
  3,  5,  8, 12;
  4,  7, 12, 20, 32;
  ...

Alois P. Heinz, Rows n = 0..150, flattened

Cf. A053220, A058877 (row sums), A193844, A212697.

Columns and diagonals: A001787, A001792, A034007, A045623, A045891, A111297, A159694, A159695, A159696, A159697.

[2^k*(n-k/2): k in [0..n], n in [0..12]]; // G. C. Greubel, Sep 27 2022

A062111 := proc(n,k) (k+n)*2^(k-n-1) ; end: A152920 := proc(n,k) A062111(n-k,n) ; end: for n from 0 to 15 do for k from 0 to n do printf("%d,",A152920(n,k)) ; od: od: # R. J. Mathar, Jan 22 2009
# second Maple program:
T:= proc(n, k) option remember;
     `if`(k=0, n, T(n, k-1)+T(n-1, k-1))
    end:
seq(seq(T(n, k), k=0..n), n=0..12);  # Alois P. Heinz, Sep 12 2022

t[0, k_]:= k; t[n_, k_]:= t[n, k]= t[n-1, k] + t[n-1, k+1];
Table[t[n-k, k], {n,0,10}, {k,n,0,-1}]//Flatten (* Jean-François Alcover, Sep 11 2016 *)

flatten([[2^(k-1)*(2*n-k) for k in range(n+1)] for n in range(12)]) # G. C. Greubel, Sep 27 2022

Row sums: (2^n-1)(n+1) = A058877(n). - R. J. Mathar, Jan 22 2009
T(2n, n) = 3*n*2^(n-1) = 3*A001787(n). - Philippe Deléham, Apr 20 2009
From Werner Schulte, Jul 31 2020: (Start)
T(n, k) = (2*n-k) * 2^(k-1) for 0 <= k <= n.
G.f.: Sum_{n>=0, k=0..n} T(n,k) * x^k * t^n = t*(1+x-3*x*t) / ((1-t)^2 * (1-2*x*t)^2).
Sum_{k=0..n} (-1)^k * binomial(n,k) * T(n,k) = 0 for n >= 0.
Sum_{k=0..n} binomial(n,k) * T(n,k) = 2*n * 3^(n-1) for n >= 0.
Define the array B(n,p) = (Sum_{k=0..n} binomial(p+k,p) * T(n,k))/(n+p+1) for n >= 0 and p >= 0. Then see the comment of Robert Coquereaux (2014) at A193844. Conjecture: B(n+1,p) = A(n,p). (End)
T(n, k) = T(n, k-1) + T(n-1, k-1) for k>=1, T(n,0) = n. - Alois P. Heinz, Sep 12 2022
From G. C. Greubel, Sep 27 2022: (Start)
T(n, n-1) = A001792(n).
T(2*n-1, n-1) = A053220(n).
T(2*n+1, n-1) = 3*A001792(n).
T(m*n, n) = (2*m-1)*A001787(n), for m >= 1. (End)

Edited by N. J. A. Sloane, Dec 19 2008

More terms from R. J. Mathar, Jan 22 2009

A141618 Triangle read by rows: number of nilpotent partial transformations (of an n-element set) of height r (height(alpha) = |Im(alpha)|), 0 <= r < n.

Original entry on oeis.org

1, 1, 2, 1, 9, 6, 1, 28, 72, 24, 1, 75, 500, 600, 120, 1, 186, 2700, 7800, 5400, 720, 1, 441, 12642, 73500, 117600, 52920, 5040, 1, 1016, 54096, 571536, 1764000, 1787520, 564480, 40320, 1, 2295, 217800, 3916080, 21019824, 40007520, 27941760, 6531840, 362880, 1, 5110, 839700, 24555600, 214326000

Offset: 1

Abdullahi Umar, Aug 23 2008

The sum of each row of the sequence (as a triangular array) is A000272. Second left-downward diagonal is A058877.
From Tom Copeland, Oct 26 2014: (Start)
With T(x,t) the e.g.f. for A055302 for the number of labeled rooted trees with n nodes and k leaves, the mirror of the row polynomials of this array are given by e^T(x,t) = exp[ t * x + (2t) * x^2/2! + (6t + 3t^2) * x^3/3! + ...] = 1 + t * x + (2t + t^2) * x^2/2! + (6t + 9t^2 + t^3) * x^3/3! + ... = 1 + Nr(x,t).
Equivalently, e^x-1 = Nr[Tinv(x,t),t] = t * N[t*Tinv(x,t),1/t], where N(x,t) is the e.g.f. of this array and Tinv(x,t) is the comp. inverse in x of T(x,t). Note that Nr(x,t) = t * N(x*t,1/t), and N(x,t) = t * Nr(x*t,1/t). Also, log[1 + Nr(x,t)]= x * [t + Nr(x,t)] = T(x,t).
E.g.f. is N(x,t)= t * {exp[T(x*t,1/t)] - 1}, and log[1 + N(x,t)/t] =  T(x*t,1/t) =  x + (2t) * x^2/2! +  (3t + 6t^2) * x^3/3! + (4t + 36t^2 + 24t^3) * x^4/4! + ... = x + (t) * x^2 + (t + 2t^2) * x^3/2! + (t + 9t^2 + 6t^3) * x^4/3! +  ... is the comp. inverse in x of x / [1 + t * (e^x - 1)].
The exp/log transforms (A036040/A127671) generally give associations between enumerations of sets of connected graphs/objects (in this case, trees) and sets of disconnected (or not necessarily connected) graphs/objects (in this case, bipartite graphs of the nilpotent transformations). The transforms also relate formal cumulants and moments so that Nr(x,t) is then the e.g.f. for the formal moments associated to the formal cumulants whose e.g.f. is T(x,t). (End)
T(n,k) is the number of parking functions of length n containing exactly k+1 distinct values in its image. - Alan Kappler, Jun 08 2024

			N(J(4,2)) = 6*6*2 = 72.
From _Peter Bala_, Oct 22 2008: (Start)
Triangle begins
n\k|..0.....1.....2.....3.....4....5
=====================================
.1.|..1
.2.|..1.....2
.3.|..1.....9.....6
.4.|..1....28....72....24
.5.|..1....75...500...600...120
.6.|..1...186..2700..7800..5400...720
...
(End)

A. Laradji and A. Umar, On the number of nilpotents in the partial symmetric semigroup, Comm. Algebra 32 (2004), 3017-3023.
A. Laradji and A. Umar, On the number of nilpotents in the partial symmetric semigroup, Tech. Report TR305, King Fahd Univ. of Petroleum and Minerals, (2003).
Wikipedia, Cumulant

Cf. A000272, A007318, A036040, A048993, A055302, A058877, A127671, A198204.

A048993 := proc(n,k)
    combinat[stirling2](n,k) ;
end proc:
A141618 := proc(n,k)
    binomial(n,k)*k!*A048993(n,k+1) ;
end proc:

Flatten[CoefficientList[CoefficientList[InverseSeries[Series[Log[1 + x]/(1 + t*x),{x,0,9}]],x]*Table[n!, {n,0,9}],t]] (* Peter Luschny, Oct 24 2015, after Peter Bala *)

A055302(n,k)=n!/k!*stirling(n-1, n-k,2);
T(n,k)=A055302(n+1,n+1-k) / (n+1);
for(n=1,10,for(k=1,n,print1(T(n,k),", "));print());
\\ Joerg Arndt, Oct 27 2014

N(J(n,r)) = C(n,r)*S(n,r+1)*r! where S(n, r + 1) is a Stirling number of the second kind (given by A048993 with zeros removed); generating function = (x+1)^(n-1).
From Peter Bala, Oct 22 2008: (Start)
Define a functional I on formal power series of the form f(x) = 1 + ax + bx^2 + ... by the following iterative process. Define inductively f^(1)(x) = f(x) and f^(n+1)(x) = f(x*f^(n)(x)) for n >= 1. Then set I(f(x)) = lim_{n -> infinity} f^(n)(x) in the x-adic topology on the ring of formal power series; the operator I may also be defined by I(f(x)) := 1/x*series reversion of x/f(x).
Let f(x) = 1 + a*x + a*x^2/2! + a*x^3/3! + ... . Then the e.g.f. for this table is I(f(x)) = 1 + a*x +(a + 2*a^2)*x^2/2! + (a + 9*a^2 + 6*a^3)*x^3/3! + (a + 28*a^2 + 72*a^3 + 24*a^4)*x^4/4! + ... . Note, if we take f(x) = 1 + a*x + a*x^2 + a*x^3 + ... then I(f(x)) is the o.g.f. of the Narayana triangle A001263. (End)
A generator for this array is given by the inverse, g(x,t), of f(x,t)= x/(1 + t * (e^x-1)). Then A248927 gives h(x,t)= x / f(x,t) = 1 + t*(e^x-1)= 1 + t * (x + x^2/2! + x^3/3! + ...) and g(x,t)= x * (1 + t * x + (t + 2 t^2) * x^2/2! + (t + 9 t^2 + 6 t^3) * x^3/3! + ...), so by Bala's arguments A248927 is a refinement of A141618 with row sums A000272. The connection to Narayana numbers is reflected in the relation between A248927 and A134264. See A145271 for more relations that g(x,t) and f(x,t) must satisfy. - Tom Copeland, Oct 17 2014
T(n,k) = C(n,k-1) * A028246(n,k) = C(n,k-1) * A019538(n,k)/k = A055302(n+1,n+1-k) / (n+1). - Tom Copeland, Oct 25 2014
E.g.f. is the series reversion of log(1 + x)/(1 + t*x) with respect to x. Cf. A198204. - Peter Bala, Oct 21 2015

More terms from Joerg Arndt, Oct 27 2014

A058876 Triangle read by rows: T(n,k) = number of labeled acyclic digraphs with n nodes, containing exactly n+1-k points of in-degree zero (n >= 1, 1<=k<=n).

Original entry on oeis.org

1, 1, 2, 1, 9, 15, 1, 28, 198, 316, 1, 75, 1610, 10710, 16885, 1, 186, 10575, 211820, 1384335, 2174586, 1, 441, 61845, 3268125, 64144675, 416990763, 654313415, 1, 1016, 336924, 43832264, 2266772550, 44218682312, 286992935964, 450179768312

Offset: 1

N. J. A. Sloane, Jan 07 2001

			Triangle begins:
  1;
  1,  2;
  1,  9,   15;
  1, 28,  198,   316;
  1, 75, 1610, 10710, 16885;
  ...

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 19, (1.6.4).
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.

Andrew Howroyd, Table of n, a(n) for n = 1..1275 (rows 1..50)
R. W. Robinson, Enumeration of acyclic digraphs, Manuscript. (Annotated scanned copy)

Columns give A058877, A060337.
Diagonals give A003025, A003026, A060335.
Row sums give A003024.
Cf. A122078 (unlabeled case).

a[p_, k_] :=a[p, k] =If[p == k, 1, Sum[Binomial[p, k]*a[p - k, n]*(2^k - 1)^n*2^(k (p - k - n)), {n,1, p - k}]];
Map[Reverse, Table[Table[a[p, k], {k, 1, p}], {p, 1, 6}]] // Grid (* Geoffrey Critzer, Aug 29 2016 *)

A058876(n)={my(v=vector(n)); for(n=1, #v, v[n]=vector(n, i, if(i==n, 1, my(u=v[n-i]); sum(j=1, #u, 2^(i*(#u-j))*(2^i-1)^j*binomial(n,i)*u[j])))); v}
{ my(T=A058876(10)); for(n=1, #T, print(Vecrev(T[n]))) } \\ Andrew Howroyd, Dec 27 2021

Harary and Prins (following Robinson) give a recurrence.

More terms from Vladeta Jovovic, Apr 10 2001

A048493 a(n) = (n+1)*2^n - n.

Original entry on oeis.org

1, 3, 10, 29, 76, 187, 442, 1017, 2296, 5111, 11254, 24565, 53236, 114675, 245746, 524273, 1114096, 2359279, 4980718, 10485741, 22020076, 46137323, 96468970, 201326569, 419430376, 872415207, 1811939302, 3758096357, 7784628196, 16106127331, 33285996514

Offset: 0

Clark Kimberling

Old definition was: "a(n) = T(n,n), array T given by A048483".

Also the number of connected induced subgraphs in the n-sunlet graph. - Eric W. Weisstein, May 25 2017

Vincenzo Librandi, Table of n, a(n) for n = 0..2000
Eric Weisstein's World of Mathematics, Sunlet Graph
Eric Weisstein's World of Mathematics, Vertex-Induced Subgraph
Index entries for linear recurrences with constant coefficients, signature (6,-13,12,-4).

Cf. A058877.

[(n+1)*2^n-n: n in [0..30]]; // Vincenzo Librandi, Sep 26 2011

Table[(n + 1) 2^n - n, {n, 20}] (* Eric W. Weisstein, May 25 2017 *)
Table[2^n + (2^n - 1) n, {n, 20}] (* Eric W. Weisstein, May 25 2017 *)
LinearRecurrence[{6, -13, 12, -4}, {3, 10, 29, 76}, 20] (* Eric W. Weisstein, May 25 2017 *)

Vec(-(4*x^3-5*x^2+3*x-1)/((x-1)^2*(2*x-1)^2) + O(x^100)) \\ Colin Barker, Nov 26 2014

a(n) = (n+1)*2^n-n. - Vladeta Jovovic, Feb 28 2003
a(n) = 5*a(n-1)-7*a(n-2)-a(n-3)+8*a(n-4)-4*a(n-5). - Colin Barker, Nov 26 2014
G.f.: -(4*x^3-5*x^2+3*x-1) / ((x-1)^2*(2*x-1)^2). - Colin Barker, Nov 26 2014

Description changed to more explicit formula by Eric W. Weisstein, May 25 2017

A133399 Triangle T(n,k)=number of forests of labeled rooted trees with n nodes, containing exactly k trees of height one, all others having height zero (n>=0, 0<=k<=floor(n/2)).

Original entry on oeis.org

1, 1, 1, 2, 1, 9, 1, 28, 12, 1, 75, 120, 1, 186, 750, 120, 1, 441, 3780, 2100, 1, 1016, 16856, 21840, 1680, 1, 2295, 69552, 176400, 45360, 1, 5110, 272250, 1224720, 705600, 30240, 1, 11253, 1026300, 7692300, 8316000, 1164240, 1, 24564, 3762132, 45018600

Offset: 0

Alois P. Heinz, Nov 24 2007

			Triangle begins:
  1;
  1;
  1,     2;
  1,     9;
  1,    28,     12;
  1,    75,    120;
  1,   186,    750,     120;
  1,   441,   3780,    2100;
  1,  1016,  16856,   21840,   1680;
  1,  2295,  69552,  176400,  45360;
  1,  5110, 272250, 1224720, 705600, 30240;
  ...

Alois P. Heinz, Rows n = 0..200, flattened
A. P. Heinz, Finding Two-Tree-Factor Elements of Tableau-Defined Monoids in Time O(n^3), Ed. S. G. Akl, F. Fiala, W. W. Koczkodaj: Advances in Computing and Information, ICCI90 Niagara Falls, LNCS 468, Springer-Verlag (1990), pp. 120-128.

Columns k=1,2 give: A058877, A133386.
Row sums give: A000248.
T(2n,n) = A001813(n), T(2n+1,n) = A002691(n).
Reading the table by diagonals gives triangle A198204. - Peter Bala, Jul 31 2012
Cf. A235596.

/* As triangle */ [[Binomial(n,k)*Factorial(k)*StirlingSecond(n-k+1,k+1): k in [0..Floor(n/2)]]: n in [0.. 15]]; // Vincenzo Librandi, Jun 06 2019

T:= (n,k)-> binomial(n,k)*k!*Stirling2(n-k+1,k+1): for n from 0 to 10 do lprint(seq(T(n, k), k=0..floor(n/2))) od;

nn=12;f[list_]:=Select[list,#>0&];Map[f,Range[0,nn]!CoefficientList[ Series[Exp[y x (Exp[x]-1)] Exp[x],{x,0,nn}],{x,y}]]//Grid (* Geoffrey Critzer, Feb 09 2013 *)
t[n_, k_] := Binomial[n, k]*k!*StirlingS2[n-k+1, k+1]; Table[t[n, k], {n, 0, 12}, {k, 0, n/2}] // Flatten (* Jean-François Alcover, Dec 19 2013 *)

T(n,k) = C(n,k) * k! * stirling2(n-k+1,k+1).
E.g.f.: exp(y*x*(exp(x)-1))*exp(x). - Geoffrey Critzer, Feb 09 2013
Sum_{k=1..floor(n/2)} T(n,k) = A235596(n+1). - Alois P. Heinz, Jun 21 2019

A198204 Series reversion of (1 - tx)log(1 + x) with respect to x.

Original entry on oeis.org

1, 1, 2, 1, 9, 12, 1, 28, 120, 120, 1, 75, 750, 2100, 1680, 1, 186, 3780, 21840, 45360, 30240, 1, 441, 16856, 176400, 705600, 1164240, 665280, 1, 1016, 69552, 1224720, 8316000, 25280640, 34594560, 17297280, 1, 2295, 272250, 7692300, 82577880, 408648240, 998917920, 1167566400, 518918400

Offset: 1

Peter Bala, Jul 31 2012

This triangle is A133399 read by diagonals.

			Triangle begins
.n\k.|..0....1.....2......3......4......5
= = = = = = = = = = = = = = = = = = = = =
..1..|..1
..2..|..1....2
..3..|..1....9....12
..4..|..1...28...120....120
..5..|..1...75...750...2100...1680
..6..|..1..186..3780..21840..45360..30240
...

Cf. A001813, A002691, A052892, A058877, A133386, A133399, A141618.

Flatten[CoefficientList[CoefficientList[InverseSeries[Series[Log[1 + x]*(1 - t*x),{x,0,9}]], x]*Table[n!, {n,0,9}], t]] (* Peter Luschny, Oct 25 2015 *)

T(n,k) = k!*binomial(n + k - 1,k)*Stirling2(n,k + 1) (n >= 1, k >=0).
E.g.f.: A(x,t) = series reversion of (1 - t*x)*log(1 + x) w.r.t. x = x + (1 + 2*t)*x^2/2! + (1 + 9*t + 12*t^2)*x^3/3! + ....
Main diagonal A001813, first subdiagonal A002691.
Column 1 A058877, column 2 A133386. Row sums A052892.
1 - t*A(x,t) = x/series reversion of x*(1 - t(exp(x) - 1)) with respect to x. Cf. A141618. - Peter Bala, Oct 22 2015

A133386 Number of forests of labeled rooted trees with n nodes, containing exactly 2 trees of height one, all others having height zero.

Original entry on oeis.org

0, 0, 0, 0, 12, 120, 750, 3780, 16856, 69552, 272250, 1026300, 3762132, 13498056, 47615750, 165683700, 570024240, 1942538592, 6566094450, 22038141420, 73510278380, 243854707320, 804962754750, 2645408201700, 8658857196552, 28237920483600, 91778694166250

Offset: 0

Alois P. Heinz, Nov 22 2007

nonn

			a(4) = 12 because 12 trees of the given kind exist: 1<-3 2<-4, 1<-4 2<-3, 1<-2 3<-4, 1<-4 3<-2, 1<-2 4<-3, 1<-3 4<-2, 2<-1 3<-4, 2<-4 3<-1, 2<-1 4<-3, 2<-3 4<-1, 3<-1 4<-2 and 3<-2 4<-1.

Alois P. Heinz, Table of n, a(n) for n = 0..650
A. P. Heinz, Finding Two-Tree-Factor Elements of Tableau-Defined Monoids in Time O(n^3), Ed. S. G. Akl, F. Fiala, W. W. Koczkodaj: Advances in Computing and Information, ICCI90 Niagara Falls, LNCS 468, Springer-Verlag (1990), pp. 120-128.
Index entries for linear recurrences with constant coefficients, signature (18,-141,630,-1767,3222,-3815,2826,-1188,216).

Cf. A058877, A000248.
Column k=2 of A133399.
Column 2 of A198204. - Peter Bala, Aug 01 2012

a:= n-> n*(n-1)*Stirling2(n-1, 3):
seq(a(n), n=0..50);

Join[{0},Table[n(n-1)StirlingS2[n-1,3],{n,30}]] (* or *) LinearRecurrence[{18,-141,630,-1767,3222,-3815,2826,-1188,216},{0,0,0,0,12,120,750,3780,16856},30] (* Harvey P. Dale, May 02 2015 *)

a(n) = n*(n-1) * Stirling2(n-1,3).
G.f.: -2*x^4*(85*x^4-180*x^3+141*x^2-48*x+6) / ((x-1)^3*(3*x-1)^3*(2*x-1)^3). - Maksym Voznyy (voznyy(AT)mail.ru), Jul 27 2009
a(0)=0, a(1)=0, a(2)=0, a(3)=0, a(4)=12, a(5)=120, a(6)=750, a(7)=3780, a(8)=16856, a(n)=18*a(n-1)-141*a(n-2)+630*a(n-3)-1767*a(n-4)+ 3222*a(n-5)- 3815*a(n-6)+2826*a(n-7)-1188*a(n-8)+216*a(n-9). - Harvey P. Dale, May 02 2015

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

A003025 Number of n-node labeled acyclic digraphs with 1 out-point.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions

A062111 Upper-right triangle resulting from binomial transform calculation for nonnegative integers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

SageMath

Formula

A152920 Triangle read by rows: triangle A062111 reversed.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

SageMath

Formula

Extensions

A141618 Triangle read by rows: number of nilpotent partial transformations (of an n-element set) of height r (height(alpha) = |Im(alpha)|), 0 <= r < n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A058876 Triangle read by rows: T(n,k) = number of labeled acyclic digraphs with n nodes, containing exactly n+1-k points of in-degree zero (n >= 1, 1<=k<=n).

Views

Author

Keywords

Examples

References

Links

Crossrefs

A198204 Series reversion of (1 - tx)log(1 + x) with respect to x.