A284417 Triangular array read by rows. T(n,k) is the number of rooted labeled trees on n nodes with exactly k vertices whose unique descendent is a leaf, n >= 1, 0 <= k <= floor((n-1)/2) + delta_{2,n}.

1, 0, 2, 3, 6, 16, 48, 145, 420, 60, 1536, 4800, 1440, 19579, 65730, 31500, 840, 290816, 1053696, 698880, 53760, 4942305, 19332936, 16367400, 2388960, 15120, 94689280, 399052800, 410296320, 93542400, 2419200, 2020278931, 9146127870, 11044008360, 3526261200, 200415600, 332640, 47523053568, 230339788800, 319018106880, 133013422080, 12986265600, 127733760

Offset

1,3

Comments

Column k=0 is A052318(n) for n>2.

Row sums = n^(n-1) = A000169(n).

Links

Table of n, a(n) for n=1..43.

Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, Cambridge Univ. Press, 2009, page 183.

Formula

E.g.f. satisfies: A(x,y) = x exp(A(x,y)) - x^2 + y x^2.

Example

Triangle begins
       1,
       0,       2,
       3,       6,
      16,      48,
     145,     420,     60,
    1536,    4800,   1440,
   19579,   65730,  31500,   840,
  290816, 1053696, 698880, 53760,
  ...
T(3,1)=6 because there are 6 labeled rooted trees (paths) o-o-o and these 6 trees have 1 vertex whose only descendent is a leaf. T(3,0) = 3 because there are 3 labeled trees of the form
    o
   / \
  o   o
and these 3 trees have no such vertices.

Mathematica

nn = 10; Range[0, nn]! CoefficientList[Series[-z^2 + u z^2 - ProductLog[-E^((-1 + u) z^2) z], {z, 0, nn}], {z, u}] // Grid

Crossrefs

Cf. A055302.

Sequence in context: A159342 A089872 A006402 * A219024 A145860 A305190

Adjacent sequences: A284414 A284415 A284416 * A284418 A284419 A284420

Keyword

nonn,tabf

Author

Geoffrey Critzer, Mar 26 2017

Status

approved