A055533 -id:A055533 - cp's OEIS frontend

A081064 Irregular array, read by rows: T(n,k) is the number of labeled acyclic digraphs with n nodes and k arcs (n >= 0, 0 <= k <= n*(n-1)/2).

1, 1, 1, 2, 1, 6, 12, 6, 1, 12, 60, 152, 186, 108, 24, 1, 20, 180, 940, 3050, 6180, 7960, 6540, 3330, 960, 120, 1, 30, 420, 3600, 20790, 83952, 240480, 496680, 750810, 838130, 691020, 416160, 178230, 51480, 9000, 720, 1, 42, 840, 10570, 93030, 601944

Offset: 0

Vladeta Jovovic, Apr 15 2003

			Array T(n,k) (with n >= 0 and 0 <= k <= n*(n-1)/2) begins as follows:
  1;
  1;
  1,  2;
  1,  6,  12,   6;
  1, 12,  60, 152,  186,  108,   24;
  1, 20, 180, 940, 3050, 6180, 7960, 6540, 3330, 960, 120;
  ...
From _Petros Hadjicostas_, Apr 10 2020: (Start)
For n=2 and k=2, we have T(2,2) = 2 labeled directed acyclic graphs with 2 nodes and 2 arcs: [A (double ->) B] and [B (double ->) A].
For n=3 and k=4, we have T(3,4) = 6 labeled directed acyclic graphs with 3 nodes and 4 arcs: [X (double ->) Y (single ->) Z (single <-) X] with (X,Y,Z) a permutation of {A,B,C}. (End)

Andrew Howroyd, Table of n, a(n) for n = 0..1350 (rows 0..20)
E. de Panafieu and S. Dovgal, Symbolic method and directed graph enumeration, arXiv:1903.09454 [math.CO], 2019.
R. W. Robinson, Counting digraphs with restrictions on the strong components, Combinatorics and Graph Theory '95 (T.-H. Ku, ed.), World Scientific, Singapore (1995), 343-354.
V. I. Rodionov, On the number of labeled acyclic digraphs, Discr. Math. 105 (1-3) (1992), 319-321.

Cf. A003024 (row sums), A055533 (subdiagonal).

Columns: A147796 (k = 3), A147817 (k = 4), A147821 (k = 5), A147860 (k = 6), A147872 (k = 7), A147881 (k = 8), A147883 (k = 9), A147964 (k = 10).

A081064gf := proc(n,x)
    local m,a ;
    option remember;
    if n = 0 then
        1;
    else
        a := 0 ;
        for m from 1 to n do
            a := a+(-1)^(m-1)*binomial(n,m)*(1+x)^(m*(n-m)) *procname(n-m,x) ;
        end do:
        expand(a) ;
    end if;
end proc:
A081064 := proc(n,k)
    coeff(A081064gf(n,x),x,k) ;
end proc:
for n from 0 to 8 do
    for k from 0 do
        tnk := A081064(n,k) ;
        if tnk =0 then
            break;
        end if;
        printf("%d ",tnk) ;
    end do:
    printf("\n") ;
end do: # R. J. Mathar, Mar 21 2019

nn = 6; a[n_] := a[n] = Sum[(-1)^(k + 1) Binomial[n, k] (1 + x)^(k (n - k)) a[   n - k], {k, 1, n}]; a[0] = 1; Table[CoefficientList[a[n], x], {n, 0, nn}] // Grid (* Geoffrey Critzer, Mar 11 2023 *)

B(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, (1+'y)^(i*(#u-j))*((1+'y)^i-1)^j * binomial(n,i) * u[j])))); v}
T(n)={my(v=B(n)); vector(#v+1, n, if(n==1, [1], Vecrev(vecsum(v[n-1]))))}
{ my(A=T(5)); for(i=1, #A, print(A[i])) } \\ Andrew Howroyd, Dec 27 2021

1 = 1*exp(-x) + 1*exp(-(1+y)*x)*x/1! + (2*y+1)*exp(-(1+y)^2*x)*x^2/2! + (6*y^3 + 12*y^2 + 6*y + 1)*exp(-(1+y)^3*x)*x^3/3! + (24*y^6 + 108*y^5 + 186*y^4 + 152*y^3 + 60*y^2 + 12*y + 1)*exp(-(1+y)^4*x)*x^4/4! + (120*y^10 + 960*y^9 + 3330*y^8 + 6540*y^7 + 7960*y^6 + 6180*y^5 + 3050*y^4 + 940*y^3 + 180*y^2 + 20*y + 1)*exp(-(1+y)^5*x)*x^5/5! + ... - Vladeta Jovovic, Jun 07 2005
We explain Vladeta Jovovic's functional equation above. If F_n(y) = Sum_{k = 0..n*(n-1)/2) T(n,k) * y^k for n >= 0, then Sum_{n >= 0} F_n(y) * exp(-(1 + y)^n * x) * x^n/n! = 1. - Petros Hadjicostas, Apr 11 2020
From Petros Hadjicostas, Apr 10 2020: (Start)
If A_n(x) = Sum_{k >= 0} T(n,k)*x^k (with T(n,k) = 0 for k > n*(n-1)/2)), then Sum_{m=1..n} (-1)^(m-1) * binomial(n,m) * (1 + x)^(m*(n-m)) * A_m(x) = 1.
T(n,0) = 1, T(n,1) = n*(n-1), T(n,2) = 12*binomial(n+1,4), and T(n,3) = binomial(n,3)*(n^3 - 5*n - 6).
Also, T(n, n*(n-1)/2 - 1) = A055533(n) = n!*(n-1)^2/2 for n > 1. (End)

T(0,0) = 1 prepended by Petros Hadjicostas, Apr 11 2020

A152818 Array read by antidiagonals: A(n,k) = (k+1)^n*(n+k)!/n!.

Original entry on oeis.org

1, 1, 1, 1, 4, 2, 1, 12, 18, 6, 1, 32, 108, 96, 24, 1, 80, 540, 960, 600, 120, 1, 192, 2430, 7680, 9000, 4320, 720, 1, 448, 10206, 53760, 105000, 90720, 35280, 5040, 1, 1024, 40824, 344064, 1050000, 1451520, 987840, 322560, 40320

Offset: 0

Paul Curtz, Dec 13 2008

A009998/A119502 gives triangle of unreduced coefficients of polynomials defined by A152650/A152656. a(n) gives numerators with denominators n! for each row.

Row 0 is A000142. Row 1 is formed from positive members of A001563. Row 2 is A055533. Column 0 is A000012. Column 1 is formed from positive members of A001787. Column 2 is A006043. Column 3 is A006044. - Omar E. Pol, Jan 06 2009

			From _Omar E. Pol_, Jan 06 2009: (Start)
Array begins:
  1,    1,      2,        6,         24,          120, ...
  1,    4,     18,       96,        600,         4320, ...
  1,   12,    108,      960,       9000,        90720, ...
  1,   32,    540,     7680,     105000,      1451520, ...
  1,   80,   2430,    53760,    1050000,     19595520, ...
  1,  192,  10206,   344064,    9450000,    235146240, ...
  1,  448,  40824,  2064384,   78750000,   2586608640, ...
  1, 1024, 157464, 11796480,  618750000,  26605117440, ...
  1, 2304, 590490, 64880640, 4640625000, 259399895040, ... (End)
Antidiagonal triangle:
  1;
  1,   1;
  1,   4,     2;
  1,  12,    18,     6;
  1,  32,   108,    96,     24;
  1,  80,   540,   960,    600,   120;
  1, 192,  2430,  7680,   9000,  4320,   720;
  1, 448, 10206, 53760, 105000, 90720, 35280, 5040;

G. C. Greubel, Antidiagonals n = 0..50, flattened
F. A. Haight, Overflow at a traffic light, Biometrika, 46 (1959), 420-424. See page 422.
F. A. Haight, Overflow at a traffic light, Biometrika, 46 (1959), 420-424. (Annotated scanned copy)
F. A. Haight, Letter to N. J. A. Sloane, n.d.

Cf. A000012, A000142, A001563, A001787, A006043, A006044, A009998.
Cf. A055533, A072597 (antidiagonal sums), A089148, A119502, A152650.
Cf. A152656, A154372.

A152818:= func< n,k | (k+1)^(n-k)*Factorial(k)*Binomial(n,k) >;
[A152818(n,k): k in [0..n], n in [0..12]]; // G. C. Greubel, Apr 10 2023

len= 45; m= 1 + Ceiling[Sqrt[len]]; Sort[Flatten[#, 1] &[MapIndexed[ {(2 +#2[[1]]^2 +(#2[[2]] -1)*#2[[2]] +#2[[1]]*(2*#2[[2]] -3))/ 2, #1}&, Table[(k+1)^n*(n+k)!/n!, {n,0,m}, {k,0,m}], {2}]]][[All, 2]][[1 ;; len]] (* From Jean-François Alcover, May 27 2011 *)
T[n_, k_]:= (k+1)^(n-k)*k!*Binomial[n, k];
Table[T[n,k], {n,0,15}, {k,0,n}]//Flatten (* G. C. Greubel, Apr 10 2023 *)

A(n,k) = (k+1)^n*(n+k)!/n! \\ Charles R Greathouse IV, Sep 10 2016

def A152818_row(n):
    R. = ZZ[]
    P = add((n-k+1)^k*x^(n-k+1)*factorial(n)/factorial(k) for k in (0..n))
    return P.coefficients()
for n in (0..12): print(A152818_row(n))  # Peter Luschny, May 03 2013

E.g.f. for array as a triangle: exp(x)/(1-t*x*exp(x)) = 1+(1+t)*x+(1+4*t+2*t^2)*x^2/2! + (1+12*t+18*t^2+6*t^3)*x^3/3! + .... E.g.f. is int {z = 0..inf} exp(-z)*F(x,t*z), (x and t chosen sufficiently small for the integral to converge), where F(x,t) = exp(x*(1+t*exp(x))) is the e.g.f. for A154372. - Peter Bala, Oct 09 2011
From Peter Bala, Oct 09 2011: (Start)
From the e.g.f., the row polynomials R(n,t) satisfy the recursion R(n,t) = 1 + t*sum {k = 0..n-1} n!/(k!*(n-k-1)!)*R(n-k-1,t). The polynomials 1/n!*R(n,x) are the polynomials P(n,x) of A152650.
Sum_{k=0..n} T(n, k) = A072597(n) (antidiagonal sums). (End)
From G. C. Greubel, Apr 10 2023: (Start)
T(n, k) = (k+1)^(n-k) * k! * binomial(n, k) (antidiagonal triangle).
Sum_{k=0..n} (-1)^k*T(n, k) = A089148(n). (End)

Better definition, extended and edited by Omar E. Pol and N. J. A. Sloane, Jan 05 2009

A342587 Triangle, read by rows: T(n,k) is the number of labeled order relations on n nodes in which the longest chain has k nodes (n>=1, 1<=k<=n).

Original entry on oeis.org

1, 1, 2, 1, 12, 6, 1, 86, 108, 24, 1, 840, 2310, 960, 120, 1, 11642, 65700, 42960, 9000, 720, 1, 227892, 2583126, 2510760, 712320, 90720, 5040, 1, 6285806, 142259628, 199357704, 71310960, 11481120, 987840, 40320, 1, 243593040, 11012710470, 21774014640, 9501062760, 1781015040

Offset: 1

R. J. Mathar and Brendan McKay, Mar 16 2021

Corrects Comtet's table for k=4 and 5 in row n=8.

			Triangle T(n,k) (with n >= 1 and 1 <= k <= n) begins as follows:
  1;
  1,      2;
  1,     12,       6;
  1,     86,     108,      24;
  1,    840,    2310,     960,    120;
  1,  11642,   65700,   42960,   9000,   720;
  1, 227892, 2583126, 2510760, 712320, 90720, 5040;
  ...

Brendan McKay, Table of T(n,k) for n = 1..13
L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 60.

Cf. A000142 (diagonal), A001035 (row sums), A055531 (k=2), A055532 (k=3), A055533 (subdiagonal), A055534 (subdiagonal), A081064, A342501 (connected).

A154306 a(n) = (n+1)^3*(3+n)!/6.

Original entry on oeis.org

1, 32, 540, 7680, 105000, 1451520, 20744640, 309657600, 4849891200, 79833600000, 1381360780800, 25107347865600, 478826764416000, 9568689242112000, 200074178304000000, 4370687116443648000, 99607063051431936000

Offset: 0

Omar E. Pol, Jan 06 2009

Row 3 of square array A152818.

Vincenzo Librandi, Table of n, a(n) for n = 0..200

Cf. A000142, A001563, A055533, A152818, A154307, A154308.

[(n+1)^3*Factorial(3+n)/6: n in [0..20]]; // Vincenzo Librandi, Mar 27 2012

Table[(n+1)^3*(3+n)!/6,{n,0,20}] (* Vincenzo Librandi, Mar 27 2012 *)

a(n) = (n+1)^3*(n+3)!/6 \\ Charles R Greathouse IV, Sep 10 2016

E.g.f.: (1 + 25*x + 67*x^2 + 27*x^3)/(1-x)^7. - R. J. Mathar, Dec 21 2011

More terms from Sean A. Irvine, Dec 01 2009

A154307 a(n) = (n+1)^4*(4+n)!/24.

Original entry on oeis.org

1, 80, 2430, 53760, 1050000, 19595520, 363031200, 6812467200, 130947062400, 2594592000000, 53182390060800, 1129830653952000, 24898991749632000, 569337009905664000, 13505007035520000000, 332172220849717248000

Offset: 0

Omar E. Pol, Jan 06 2009

nonn

Row 4 of square array A152818.

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

Cf. A000142, A001563, A055533, A152818, A154306, A154308.

[(n+1)^4*Factorial(4+n)/24: n in [0..20]]; // Vincenzo Librandi, Sep 11 2016

Table[(n + 1)^4*(4 + n)!/24, {n, 0, 25}] (* G. C. Greubel, Sep 10 2016 *)

E.g.f.: (1 + 71*x + 531*x^2 + 821*x^3 + 256*x^4)/(1-x)^9. - R. J. Mathar, Dec 21 2011

Extended by Max Alekseyev, Apr 13 2009

A154308 a(n) = (n+1)^5*(5+n)!/120.

Original entry on oeis.org

1, 192, 10206, 344064, 9450000, 235146240, 5590680480, 130799370240, 3064161260160, 72648576000000, 1755018872006400, 43385497111756800, 1100535435333734400, 28694585299245465600, 769785401024640000000, 21259022134381903872000, 604515265659140419584000, 17698965059877321572352000

Offset: 0

Omar E. Pol, Jan 06 2009

nonn

Row 5 of square array A152818.

G. C. Greubel, Table of n, a(n) for n = 0..250
Clark Kimberling, Polynomials associated with reciprocation, JIS 12 (2009) 09.3.4 section 6.

Cf. A000142, A001563, A055533, A152818, A154306, A154307.

[(n+1)^5*Factorial(5+n)/120: n in [0..20]]; // Vincenzo Librandi, Sep 11 2016

Table[(n + 1)^5*(5 + n)!/120, {n, 0, 25}] (* G. C. Greubel, Sep 10 2016 *)

for(n=0,25, print1((n+1)^5*(5+n)!/120, ", ")) \\ G. C. Greubel, Nov 24 2017

a(n) = A000142(n+1)*A000583(n+1)*A000389(n+5). - R. J. Mathar, Jan 17 2009

E.g.f.: (1 + 181*x + 3046*x^2 + 11606*x^3 + 12281*x^4 + 3125*x^5)/(1-x)^11. - R. J. Mathar, Dec 21 2011

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

A280556 a(n) = Sum_{k=1..n} k^2 * (k+1)!.

Original entry on oeis.org

0, 2, 26, 242, 2162, 20162, 201602, 2177282, 25401602, 319334402, 4311014402, 62270208002, 958961203202, 15692092416002, 271996268544002, 4979623993344002, 96035605585920002, 1946321606541312002, 41359334139002880002, 919636959090769920002, 21356013827774545920002

Offset: 0

Michel Marcus, Jan 05 2017

nonn

Partial sums of 2*A055533.

Seiichi Manyama, Table of n, a(n) for n = 0..446
Mathematical Reflections, Problem J256, Issue 1, 2013, p 4.
Mathematical Reflections, Solution to Problem J256, Issue 2, 2013, p 4.

Cf. A052520, A055533.

A280556:=n->add(k^2*(k+1)!, k=1..n): seq(A280556(n), n=0..30); # Wesley Ivan Hurt, Jan 05 2017

Table[Sum[k^2 (k+1)!,{k,n}],{n,0,20}] (* Harvey P. Dale, Jun 05 2017 *)

PARI
```
a(n) = sum(k=1, n, k^2*(k+1)!)
```

a(n) = (n - 1)*(n + 2)! + 2 (see 2nd Mathematical Reflections link). Cf. A052520.

E.g.f.: 2*exp(x) - 2*(1 - 4*x)/(1 - x)^4. - Ilya Gutkovskiy, Jan 05 2017

A008285 Erroneous version of A342587.

Original entry on oeis.org

1, 1, 2, 1, 12, 6, 1, 86, 108, 24, 1, 840, 2310, 960, 120, 1, 11642, 65700, 42960, 9000, 720, 1, 227892, 2583126, 2510760, 712320, 90720, 5040, 1, 6285806, 142259628, 199424904, 71243760, 11481120, 987840, 40320

Offset: 1

N. J. A. Sloane

dead

			Triangle T(n,k) (with n >= 1 and 1 <= k <= n) begins as follows:
  1;
  1,      2;
  1,     12,       6;
  1,     86,     108,      24;
  1,    840,    2310,     960,    120;
  1,  11642,   65700,   42960,   9000,   720;
  1, 227892, 2583126, 2510760, 712320, 90720, 5040;
  ...

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 60.

Cf. A000142 (diagonal), A001035 (row sums), A055531 (k=2), A055532 (k=3), A055533 (subdiagonal), A081064, A342501 (connected).

cp's OEIS Frontend

A081064 Irregular array, read by rows: T(n,k) is the number of labeled acyclic digraphs with n nodes and k arcs (n >= 0, 0 <= k <= n*(n-1)/2).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A152818 Array read by antidiagonals: A(n,k) = (k+1)^n*(n+k)!/n!.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Sage

Formula

Extensions

A342587 Triangle, read by rows: T(n,k) is the number of labeled order relations on n nodes in which the longest chain has k nodes (n>=1, 1<=k<=n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A154306 a(n) = (n+1)^3*(3+n)!/6.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

Extensions

A154307 a(n) = (n+1)^4*(4+n)!/24.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

Formula

Extensions

A154308 a(n) = (n+1)^5*(5+n)!/120.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

Extensions

A280556 a(n) = Sum_{k=1..n} k^2 * (k+1)!.

Views

Author

Keywords

Comments