A028418 - OEIS

%I #41 Dec 08 2018 20:02:57

%S 1,3,13,67,411,2911,23563,213543,2149927,23759791,286370151,

%T 3734929903,52455166063,788704078527,12648867695311,215433088624351,

%U 3884791172487903,73919882720901823,1480542628345939807,31128584449987511871,685635398619169059391

%N Sum over all n! permutations of n letters of maximum cycle length.

%C Sum the n-permutations having at least 1 cycle of length >= i for all i >= 1. A000142 + A033312 + A066052 + A202364 + ... The summation is precisely that indicated in the title since each permutation whose longest cycle = i is counted i times. - _Geoffrey Critzer_, Jan 09 2013

%D S. W. Golomb, Shift-Register Sequences, Holden-Day, San Francisco, 1967, p. 183.

%D R. Sedgewick and P. Flajolet, Analysis of Algorithms, Addison Wesley, 1996, page 358.

%H Alois P. Heinz, <a href="/A028418/b028418.txt">Table of n, a(n) for n = 1..450</a> (first 142 terms from Thomas Dybdahl Ahle)

%H Ph. Flajolet and A. Odlyzko, <a href="http://algo.inria.fr/flajolet/Publications/FlOd90b.pdf">Singularity analysis of generating functions</a>, p. 22.

%F E.g.f.: Sum_{k>=0} (1/(1-x) - exp(Sum_{j=1..k} x^j/j)).

%F a(n) = f(n, 0, n, n!) where f(L, r, n, m) = m*r if r >= l, otherwise Sum_{k=0..L-1} (f(k, max(L-k,r), n-1, m/n) + (n-L)*f(L, r, n-1, m/n)). - _Thomas Dybdahl Ahle_, Aug 15 2011

%F a(n) = Sum_{k=1..n} k * A126074(n,k). - _Alois P. Heinz_, May 17 2016

%p b:= proc(n, m) option remember; `if`(n=0, m, add((j-1)!*

%p       b(n-j, max(m,j))*binomial(n-1, j-1), j=1..n))

%p     end:

%p a:= n-> b(n, 0):

%p seq(a(n), n=1..25);  # _Alois P. Heinz_, May 14 2016

%t kmax = 19; gf[x_] = Sum[ 1/(1-x) - 1/(E^((x^(1+k)*Hypergeometric2F1[1+k, 1, 2+k, x])/ (1+k))*(1-x)), {k, 0, kmax}];

%t a[n_] := n!*Coefficient[Series[gf[x], {x, 0, kmax}], x^n]; Array[a, kmax]

%t (* _Jean-François Alcover_, Jun 22 2011, after e.g.f. *)

%t a[ n_] := If[ n < 1, 0, 1 + Total @ Apply[ Max, Map[ Length, First /@ PermutationCycles /@ Drop[ Permutations @ Range @ n, 1], {2}], 1]]; (* _Michael Somos_, Aug 19 2018 *)

%Y Cf. A006128, A028417, A060014, A126074.

%Y Column k=1 of A322384.

%K nonn

%O 1,2

%A Joe Keane (jgk(AT)jgk.org)

%E More terms from _Vladeta Jovovic_, Sep 19 2002

%E More terms from _Thomas Dybdahl Ahle_, Aug 15 2011