A071208 Triangular array T(n,k) read by rows, giving number of labeled free trees such that the root is smaller than all its children, with respect to the number n of vertices and to the number k of decreasing edges.

1, 2, 2, 6, 15, 6, 24, 104, 104, 24, 120, 770, 1345, 770, 120, 720, 6264, 16344, 16344, 6264, 720, 5040, 56196, 200452, 300167, 200452, 56196, 5040, 40320, 554112, 2552192, 5241984, 5241984, 2552192, 554112, 40320, 362880, 5973264, 34138908, 90857052, 124756281, 90857052, 34138908, 5973264, 362880

Offset

1,2

Links

Alois P. Heinz, Rows n = 1..141, flattened

Cedric Chauve, S. Dulucq and O. Guibert, Enumeration of some labeled trees, Proceedings of FPSAC/SFCA 2000 (Moscow), Springer, pp. 146-157.

Yen-Jen Cheng, Sen-Peng Eu, Tung-Shan Fu, and Jyun-Cheng Yao, On q-Counting of Noncrossing Chains and Parking Functions, arXiv:2312.07351 [math.CO], 2023.

A. M. Khidr and B. S. El-Desouky, A symmetric sum involving the Stirling numbers of the first kind, European J. Combin., 5 (1984), 51-54. See Table 1.

Formula

T(n,k) = Sum_{m=k+1..n} (-1)^(k+1)*binomial(m,k+1)*Stirling1(n+1,n+1-m)*n^(n-m) with 0 <= k < n.

Example

Triangle begins:
   1
   2    2
   6   15     6
  24  104   104    24
 120  770  1345   770   120
 720 6264 16344 16344  6264  720
 ...

Maple

T:= (n, k)-> add((-1)^(k+1)*binomial(m, k+1)*
             Stirling1(n+1, n+1-m)*n^(n-m), m=k+1..n):
seq(seq(T(n, k), k=0..n-1), n=1..9);

Mathematica

A071208[n_, k_] := Sum[(-1)^(k+1)*Binomial[m, k+1]*StirlingS1[n+1, n+1-m]*n^(n-m), {m, k+1, n}];
Table[A071208[n, k], {n, 10}, {k, 0, n-1}] (* Paolo Xausa, Jun 28 2024 *)

Crossrefs

Row sums give A000312.

Cf. A000142.

Sequence in context: A259810 A142471 A323233 * A231536 A216242 A330798

Adjacent sequences: A071205 A071206 A071207 * A071209 A071210 A071211

Keyword

easy,nonn,tabl,changed

Author

Cedric Chauve (chauve(AT)lacim.uqam.ca), May 16 2002

Extensions

Offset 1 from Alois P. Heinz, Jun 26 2024

Status

approved