login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A247009 Number of permutations on [n] that are the n-th power of a permutation. 2
1, 1, 1, 4, 9, 96, 190, 4320, 11025, 179200, 805896, 36288000, 63155400, 5748019200, 18861448320, 380872267776, 4108830350625, 334764638208000, 778062273788800, 115242726703104000, 310526396168644656, 15009607805018112000, 208853182616336294400 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,4

COMMENTS

Number of permutations p on [n] such that a permutation q on [n] exists with p=q^n.

LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..200

H. S. Wilf, Generatingfunctionology, 2nd edn., Academic Press, NY, 1994, Theorem 4.8.2.

EXAMPLE

a(0) = 1: (), the empty permutation.

a(1) = 1: (1).

a(2) = 1: (1,2).

a(3) = 4: (1,2,3), (1,3,2), (2,1,3), (3,2,1).

a(4) = 9: (1,2,3,4), (1,3,4,2), (1,4,2,3), (2,3,1,4), (2,4,3,1), (3,1,2,4), (3,2,4,1), (4,1,3,2), (4,2,1,3).

MAPLE

with(combinat): with(numtheory): with(padic):

b:= proc(n, i, k) option remember; `if`(n=0, 1, `if`(i<1, 0, add(

      `if`(irem(j, mul(p^ordp(k, p), p=factorset(i)))=0, (i-1)!^j*

      multinomial(n, n-i*j, i$j)/j!*b(n-i*j, i-1, k), 0), j=0..n/i)))

    end:

a:= n-> b(n$3):

seq(a(n), n=0..25);

MATHEMATICA

multinomial[n_, k_List] := n!/Times @@ (k!); b[_, 1, _] = 1;

b[n_, i_, k_] := b[n, i, k] = If[n == 0, 1, If[i < 1, 0, Sum[If[Mod[j, Product[p^IntegerExponent[k, p], {p, FactorInteger[i][[All, 1]]}]] == 0, (i-1)!^j*multinomial[n, Join[{n-i*j}, Array[i&, j]]]/j!*b[n-i*j, i-1, k], 0], {j, 0, n/i}]]];

a[n_] := b[n, n, n];

Table[a[n], {n, 0, 25}] (* Jean-Fran├žois Alcover, Mar 25 2017, translated from Maple *)

CROSSREFS

Main diagonal of A247005.

Sequence in context: A227419 A242097 A220972 * A245241 A115690 A115689

Adjacent sequences:  A247006 A247007 A247008 * A247010 A247011 A247012

KEYWORD

nonn

AUTHOR

Alois P. Heinz, Sep 09 2014

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 February 29 09:35 EST 2020. Contains 332355 sequences. (Running on oeis4.)