# Greetings from The On-Line Encyclopedia of Integer Sequences! http://oeis.org/

Search: id:a028418
Showing 1-1 of 1

%I A028418 #41 Dec 08 2018 20:02:57
%S A028418 1,3,13,67,411,2911,23563,213543,2149927,23759791,286370151,
%T A028418 3734929903,52455166063,788704078527,12648867695311,215433088624351,
%U A028418 3884791172487903,73919882720901823,1480542628345939807,31128584449987511871,685635398619169059391
%N A028418 Sum over all n! permutations of n letters of maximum cycle length.
%C A028418 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 A028418 S. W. Golomb, Shift-Register Sequences, Holden-Day, San Francisco, 1967, p. 183.
%D A028418 R. Sedgewick and P. Flajolet, Analysis of Algorithms, Addison Wesley, 1996, page 358.
%H A028418 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 A028418 Ph. Flajolet and A. Odlyzko, <a href="http://algo.inria.fr/flajolet/Publications/FlOd90b.pdf">Singularity analysis of generating functions</a>, p. 22.
%F A028418 E.g.f.: Sum_{k>=0} (1/(1-x) - exp(Sum_{j=1..k} x^j/j)).
%F A028418 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 A028418 a(n) = Sum_{k=1..n} k * A126074(n,k). - _Alois P. Heinz_, May 17 2016
%p A028418 b:= proc(n, m) option remember; `if`(n=0, m, add((j-1)!*
%p A028418       b(n-j, max(m,j))*binomial(n-1, j-1), j=1..n))
%p A028418     end:
%p A028418 a:= n-> b(n, 0):
%p A028418 seq(a(n), n=1..25);  # _Alois P. Heinz_, May 14 2016
%t A028418 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 A028418 a[n_] := n!*Coefficient[Series[gf[x], {x, 0, kmax}], x^n]; Array[a, kmax]
%t A028418 (* _Jean-François Alcover_, Jun 22 2011, after e.g.f. *)
%t A028418 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 A028418 Cf. A006128, A028417, A060014, A126074.
%Y A028418 Column k=1 of A322384.
%K A028418 nonn
%O A028418 1,2
%A A028418 Joe Keane (jgk(AT)jgk.org)
%E A028418 More terms from _Vladeta Jovovic_, Sep 19 2002
%E A028418 More terms from _Thomas Dybdahl Ahle_, Aug 15 2011

# Content is available under The OEIS End-User License Agreement: http://oeis.org/LICENSE