A028418 Sum over all n! permutations of n letters of maximum cycle length.
1, 3, 13, 67, 411, 2911, 23563, 213543, 2149927, 23759791, 286370151, 3734929903, 52455166063, 788704078527, 12648867695311, 215433088624351, 3884791172487903, 73919882720901823, 1480542628345939807, 31128584449987511871, 685635398619169059391
Offset: 1
Keywords
References
- S. W. Golomb, Shift-Register Sequences, Holden-Day, San Francisco, 1967, p. 183.
- R. Sedgewick and P. Flajolet, Analysis of Algorithms, Addison Wesley, 1996, page 358.
Links
- Alois P. Heinz, Table of n, a(n) for n = 1..450 (first 142 terms from Thomas Dybdahl Ahle)
- Ph. Flajolet and A. Odlyzko, Singularity analysis of generating functions, p. 22.
Programs
-
Maple
b:= proc(n, m) option remember; `if`(n=0, m, add((j-1)!* b(n-j, max(m,j))*binomial(n-1, j-1), j=1..n)) end: a:= n-> b(n, 0): seq(a(n), n=1..25); # Alois P. Heinz, May 14 2016 -
Mathematica
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}]; a[n_] := n!*Coefficient[Series[gf[x], {x, 0, kmax}], x^n]; Array[a, kmax] (* Jean-François Alcover, Jun 22 2011, after e.g.f. *) 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 *)
Formula
E.g.f.: Sum_{k>=0} (1/(1-x) - exp(Sum_{j=1..k} x^j/j)).
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
a(n) = Sum_{k=1..n} k * A126074(n,k). - Alois P. Heinz, May 17 2016
Extensions
More terms from Vladeta Jovovic, Sep 19 2002
More terms from Thomas Dybdahl Ahle, Aug 15 2011
Comments