cp's OEIS Frontend

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

%I A036360 #78 Jul 20 2024 16:01:23
%S A036360 0,1,12,153,2272,39225,776736,17398969,435538944,12058401393,
%T A036360 366021568000,12090393761721,431832459644928,16585599200808937,
%U A036360 681703972229640192,29858718555221585625,1388451967046195347456,68316647610168842824161,3546179063131198669848576,193670918442059606406896473
%N A036360 a(n) = Sum_{k=1..n} n! * n^(n-k+1) / (n-k)!.
%C A036360 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
%C A036360 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
%C A036360 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
%D A036360 F. Harary and E. Palmer, Graphical Enumeration, (1973), p. 30, Exercise 1.15a.
%D A036360 P. Flajolet and A. Odlyzko, Random Mapping Statistics, INRIA RR 1114.
%H A036360 N. J. A. Sloane, <a href="/A036360/b036360.txt">Table of n, a(n) for n = 0..100</a>
%H A036360 Marko Riedel, <a href="https://math.stackexchange.com/questions/4947985/">Pusieux series of the tree function and random mapping statistics</a>.
%F A036360 a(n) = n^2 * A001865(n). - _Gerald McGarvey_, Apr 17 2008
%F A036360 a(n) = Sum_{k=1..n} n! * k^2 * n^(n-k) / (n-k)!. - _Brian P Hawkins_, Jan 06 2024
%F A036360 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
%F A036360 a(n) ~ n^n * ((1/2) * n * sqrt(2 * Pi * n) - (1/3) * n) - _Marko Riedel_, Jul 20 2024
%F A036360 a(n) = n * e^n * Gamma(n + 1, n) - n^(n + 1) = 2*A262970(n) - A007778(n). - _Peter Luschny_, Jul 20 2024
%e A036360 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.
%p A036360 a := proc(n) local k; add(n!*n^(n-k+1)/(n-k)!, k=0..n); end;
%p A036360 # Alternative, e.g.f.:
%p A036360 T := -LambertW(-x): egf := (T + T^2)/(1 - T)^4: ser := series(egf, x, 22):
%p A036360 seq(n!*coeff(ser, x, n), n = 0..19);  # _Peter Luschny_, Jul 20 2024
%t A036360 Table[Sum[n!*n^(n-k+1)/(n-k)!, {k, 1, n}], {n, 0, 19}] (* _James C. McMahon_, Feb 07 2024 *)
%t A036360 a[n_] := n E^n Gamma[n + 1, n] - n^(n + 1);
%t A036360 Table[a[n], {n, 0, 19}]  (* _Peter Luschny_, Jul 20 2024 *)
%o A036360 (Python)
%o A036360 def a(n):
%o A036360     total_sum = 0
%o A036360     for k in range(1, n + 1):
%o A036360         term = (math.factorial(n) / math.factorial(n - k))*(k**2)*(n**(n - k))
%o A036360         total_sum += term
%o A036360     return total_sum
%o A036360 # _Brian P Hawkins_, Jan 06 2024
%o A036360 (PARI) a(n) = sum(k=1, n, n! * n^(n-k+1) / (n-k)!) \\ _Andrew Howroyd_, Jan 06 2024
%Y A036360 Cf. A000435, A001373, A007778, A262970.
%K A036360 nonn,easy
%O A036360 0,3
%A A036360 _N. J. A. Sloane_
%E A036360 Offset corrected by _Brian P Hawkins_, Jan 06 2024
%E A036360 Name edited by _Andrew Howroyd_, Feb 06 2024
%E A036360 Offset set to 0 and a(0) = 0 prepended by _Marko Riedel_, Jul 20 2024