A052296 Triangle read by rows: T(n,k) = number of labeled digraphs with n nodes and k arcs and without directed paths of length >=2, with 0 <= k <= floor(n^2/4).

1, 1, 1, 2, 1, 6, 6, 1, 12, 36, 32, 6, 1, 20, 120, 280, 280, 120, 20, 1, 30, 300, 1320, 2910, 3492, 2400, 960, 210, 20, 1, 42, 630, 4480, 17220, 39144, 56294, 53760, 35070, 15680, 4662, 840, 70, 1, 56, 1176, 12320, 73220, 269136, 654304, 1108928, 1362900

Offset

0,4

Links

Table of n, a(n) for n=0..50.

Formula

G.f. for n-th row: Sum_{k=0..n} binomial(n, k)*((1+x)^k-1)^(n-k). - Vladeta Jovovic, Apr 04 2003

E.g.f.: Sum_{n>=0} exp(y*((1+x)^n-1))*y^n/n!. - Vladeta Jovovic, May 28 2004

T(n,3) = n*(n-1)*(n-2)*(n-3)*(n^2-3*n+4)/6, n>=4. - R. J. Mathar, Mar 16 2021

Example

  1;
  1;
  1,  2;
  1,  6,   6;
  1, 12,  36,   32,    6;
  1, 20, 120,  280,  280,  120,   20;
  1, 30, 300, 1320, 2910, 3492, 2400, 960, 210, 20;
  ...

Maple

A052296 := proc(n, k)
    local x, l ;
    add(binomial(n, l)*((1+x)^l-1)^(n-l), l=0..n) ;
    expand(%) ;
    coeftayl(%, x=0, k) ;
end proc: # R. J. Mathar, Mar 16 2021

Crossrefs

Row sums give A001831.

Cf. A002378 (k=1), A083374 (k=2).

Sequence in context: A347678 A202190 A089231 * A019538 A269646 A269336

Adjacent sequences: A052293 A052294 A052295 * A052297 A052298 A052299

Keyword

nonn,tabf

Author

Vladeta Jovovic, Feb 08 2000

Status

approved