A066324 Number of endofunctions on n labeled points constructed from k rooted trees.

1, 2, 2, 9, 12, 6, 64, 96, 72, 24, 625, 1000, 900, 480, 120, 7776, 12960, 12960, 8640, 3600, 720, 117649, 201684, 216090, 164640, 88200, 30240, 5040, 2097152, 3670016, 4128768, 3440640, 2150400, 967680, 282240, 40320, 43046721

Offset

1,2

Comments

T(n,k) = number of endofunctions with k recurrent elements. - Mitch Harris, Jul 06 2006

The sum of row n is n^n, for any n. Basically the same sequence arises when studying random mappings (see A243203, A203202). - Stanislav Sykora, Jun 01 2014

References

F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Cambridge, 1998, p. 87, see (2.3.28).

I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, John Wiley and Sons, N.Y., 1983, ex. 3.3.32.

Links

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

Formula

T(n,k) = k*n^(n-k)*(n-1)!/(n-k)!.

E.g.f. (relative to x): A(x, y)=1/(1-y*B(x)) - 1 = y*x +(2*y+2*y^2)*x^2/2! + (9*y+12*y^2+6*y^3)*x^3/3! + ..., where B(x) is e.g.f. A000169.

From Peter Bala, Sep 30 2011: (Start)

Let F(x,t) = x/(1+t*x)*exp(-x/(1+t*x)) = x*(1 - (1+t)*x + (1+4*t+2*t^2)*x^2/2! - ...). F is essentially the e.g.f. for A144084 (see also A021010). Then the e.g.f. for the present table is t*F(x,t)^(-1), where the compositional inverse is taken with respect to x.

Removing a factor of n from the n-th row entries results in A122525 in row reversed form.

(End)

Sum_{k=2..n} (k-1) * T(n,k) = A001864(n). - Geoffrey Critzer, Aug 19 2013

Sum_{k=1..n} k * T(n,k) = A063169(n). - Alois P. Heinz, Dec 15 2021

Example

Triangle T(n,k) begins:
       1;
       2,      2;
       9,     12,      6;
      64,     96,     72,     24;
     625,   1000,    900,    480,   120;
    7776,  12960,  12960,   8640,  3600,   720;
  117649, 201684, 216090, 164640, 88200, 30240, 5040;
  ...

Maple

T:= (n, k)-> k*n^(n-k)*(n-1)!/(n-k)!:
seq(seq(T(n, k), k=1..n), n=1..5);  # Alois P. Heinz, Aug 22 2012

Mathematica

f[list_] := Select[list, # > 0 &]; t = Sum[n^(n - 1) x^n/n!, {n, 1, 20}]; Flatten[Map[f, Drop[Range[0, 10]! CoefficientList[Series[1/(1 - y*t), {x, 0, 10}], {x, y}], 1]]] (* Geoffrey Critzer, Dec 05 2011 *)

Prog

(PARI) T(n, k)=k*n^(n-k)*(n-1)!/(n-k)! \\ Charles R Greathouse IV, Dec 05 2011

Crossrefs

Column 1: A000169.

Main diagonal: A000142.

T(n, n-1): A062119.

Row sums give A000312.

Cf. A001864, A021010, A063169, A122525, A144084, A243203.

Sequence in context: A002880 A225465 A248665 * A143146 A298663 A325936

Adjacent sequences: A066321 A066322 A066323 * A066325 A066326 A066327

Keyword

nonn,tabl

Author

Christian G. Bower, Dec 14 2001

Status

approved