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,2

Comments

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

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.

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

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 *)

Crossrefs

Cf. A006128, A028417, A060014, A126074.

Column k=1 of A322384.

Sequence in context: A367919 A350855 A295226 * A180191 A080832 A194019

Adjacent sequences: A028415 A028416 A028417 * A028419 A028420 A028421

Keyword

nonn

Author

Joe Keane (jgk(AT)jgk.org)

Extensions

More terms from Vladeta Jovovic, Sep 19 2002

More terms from Thomas Dybdahl Ahle, Aug 15 2011

Status

approved