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

Author

Christian G. Bower, Dec 14 2001

Keywords

• nonn
• tabl

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, A243202). - Stanislav Sykora, Jun 01 2014

Examples

			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;
  ...
		

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

Crossrefs

Column 1: A000169.

Main diagonal: A000142.

T(n, n-1): A062119.

Row sums give A000312.

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

Programs

Maple

T:= (n, k)-> k*n^(n-k)*(n-1)!/(n-k)!:
seq(seq(T(n, k), k=1..n), n=1..10);  # 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 *)

PARI

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

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