A036360 a(n) = Sum_{k=1..n} n! * n^(n-k+1) / (n-k)!.

0, 1, 12, 153, 2272, 39225, 776736, 17398969, 435538944, 12058401393, 366021568000, 12090393761721, 431832459644928, 16585599200808937, 681703972229640192, 29858718555221585625, 1388451967046195347456, 68316647610168842824161, 3546179063131198669848576, 193670918442059606406896473

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy

Comments

This formula is given as a solution to Exercise 1.15a in the Harary and Palmer reference on page 30. However, the formula may not be correct and could be a misprint for Sum_{k=2..n} n! * n^(n-k-1) / (n-k)! which is a formula for A000435(n). - Andrew Howroyd, Feb 06 2024

It appears that a(n) * n^-(n+1) is the mean position of the first duplicate in sequences of n elements randomly drawn with replacement. - Brian P Hawkins, Jan 06 2024

Total count over all mappings from [n] to [n] of tail length plus cycle size of all nodes, where mappings are sets of cycles of trees and tail length is the distance to the cycle that eventually traps the iterates of a node of the mapping; cycle size is the size of that cycle. Alternatively, number of elements on the trajectory of iterates of a node until a repeat is seen, summed over all nodes and mappings. - Marko Riedel, Jul 20 2024

Examples

			Example: Consider the map [1,2,3,4] -> [2,3,4,4]. The trajectory of node one is [1,2,3,4]. Hence the tail length is three and the cycle size is one, a fixed point.
		

References

• F. Harary and E. Palmer, Graphical Enumeration, (1973), p. 30, Exercise 1.15a.
• P. Flajolet and A. Odlyzko, Random Mapping Statistics, INRIA RR 1114.

Links

• N. J. A. Sloane, Table of n, a(n) for n = 0..100
• Marko Riedel, Pusieux series of the tree function and random mapping statistics.

Crossrefs

Cf. A000435, A001373, A007778, A262970.

Programs

Maple

a := proc(n) local k; add(n!*n^(n-k+1)/(n-k)!, k=0..n); end;
# Alternative, e.g.f.:
T := -LambertW(-x): egf := (T + T^2)/(1 - T)^4: ser := series(egf, x, 22):
seq(n!*coeff(ser, x, n), n = 0..19);  # Peter Luschny, Jul 20 2024

Mathematica

Table[Sum[n!*n^(n-k+1)/(n-k)!, {k, 1, n}], {n, 0, 19}] (* James C. McMahon, Feb 07 2024 *)
a[n_] := n E^n Gamma[n + 1, n] - n^(n + 1);
Table[a[n], {n, 0, 19}]  (* Peter Luschny, Jul 20 2024 *)

PARI

a(n) = sum(k=1, n, n! * n^(n-k+1) / (n-k)!) \\ Andrew Howroyd, Jan 06 2024

Python

def a(n):
    total_sum = 0
    for k in range(1, n + 1):
        term = (math.factorial(n) / math.factorial(n - k))*(k**2)*(n**(n - k))
        total_sum += term
    return total_sum
# Brian P Hawkins, Jan 06 2024

Formula

a(n) = n^2 * A001865(n). - Gerald McGarvey, Apr 17 2008

a(n) = Sum_{k=1..n} n! * k^2 * n^(n-k) / (n-k)!. - Brian P Hawkins, Jan 06 2024

a(n) = n! * [z^n] (T+T^2)/(1-T)^4 where T is Cayley's tree function T(z) = Sum_{n >= 1} n^(n-1) * z^n/n!. - Marko Riedel, Jul 20 2024

a(n) ~ n^n * ((1/2) * n * sqrt(2 * Pi * n) - (1/3) * n) - Marko Riedel, Jul 20 2024

a(n) = n * e^n * Gamma(n + 1, n) - n^(n + 1) = 2*A262970(n) - A007778(n). - Peter Luschny, Jul 20 2024

Extensions

Offset corrected by Brian P Hawkins, Jan 06 2024

Name edited by Andrew Howroyd, Feb 06 2024

Offset set to 0 and a(0) = 0 prepended by Marko Riedel, Jul 20 2024