login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A028418 Sum over all n! permutations of n letters of maximum cycle length. 12
1, 3, 13, 67, 411, 2911, 23563, 213543, 2149927, 23759791, 286370151, 3734929903, 52455166063, 788704078527, 12648867695311, 215433088624351, 3884791172487903, 73919882720901823, 1480542628345939807, 31128584449987511871, 685635398619169059391 (list; graph; refs; listen; history; text; internal format)
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: A107592 A215257 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 24 10:24 EDT 2019. Contains 322422 sequences. (Running on oeis4.)