login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A066324 Number of endofunctions on n labeled points constructed from k rooted trees. 7
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 (list; table; graph; refs; listen; history; text; internal format)
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)

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. A021010, A122525, A144084, A243203.

Sequence in context: A002880 A225465 A248665 * A143146 A298663 A185755

Adjacent sequences:  A066321 A066322 A066323 * A066325 A066326 A066327

KEYWORD

nonn,tabl

AUTHOR

Christian G. Bower, Dec 14 2001

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified February 19 16:28 EST 2018. Contains 299356 sequences. (Running on oeis4.)