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

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A247005 Number A(n,k) of permutations on [n] that are the k-th power of a permutation; square array A(n,k), n>=0, k>=0, read by antidiagonals. 12
 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 6, 1, 1, 1, 2, 3, 24, 1, 1, 1, 1, 4, 12, 120, 1, 1, 1, 2, 3, 16, 60, 720, 1, 1, 1, 1, 6, 9, 80, 270, 5040, 1, 1, 1, 2, 1, 24, 45, 400, 1890, 40320, 1, 1, 1, 1, 6, 4, 96, 225, 2800, 14280, 362880, 1, 1, 1, 2, 3, 24, 40, 576, 1575, 22400, 128520, 3628800, 1 (list; table; graph; refs; listen; history; text; internal format)
 OFFSET 0,9 COMMENTS Number of permutations p on [n] such that a permutation q on [n] exists with p=q^k. LINKS Alois P. Heinz, Antidiagonals n = 0..140, flattened H. S. Wilf, Generatingfunctionology, 2nd edn., Academic Press, NY, 1994, Theorem 4.8.2. EXAMPLE A(3,0) = 1: (1,2,3). A(3,1) = 6: (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1). A(3,2) = 3: (1,2,3), (2,3,1), (3,1,2). A(3,3) = 4: (1,2,3), (1,3,2), (2,1,3), (3,2,1). Square array A(n,k) begins:   1,    1,    1,    1,    1,    1,    1,    1,    1, ...   1,    1,    1,    1,    1,    1,    1,    1,    1, ...   1,    2,    1,    2,    1,    2,    1,    2,    1, ...   1,    6,    3,    4,    3,    6,    1,    6,    3, ...   1,   24,   12,   16,    9,   24,    4,   24,    9, ...   1,  120,   60,   80,   45,   96,   40,  120,   45, ...   1,  720,  270,  400,  225,  576,  190,  720,  225, ...   1, 5040, 1890, 2800, 1575, 4032, 1330, 4320, 1575, ... 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, k)-> `if`(k=0, 1, b(n\$2, k)): seq(seq(A(n, d-n), n=0..d), d=0..14); 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_, k_] := If[k == 0, 1, b[n, n, k]]; Table[A[n, d - n], {d, 0, 14}, {n, 0, d}] // Flatten (* Jean-François Alcover, Jan 14 2017, after Alois P. Heinz *) CROSSREFS Columns k=0-10 give: A000012, A000142, A003483, A103619, A103620, A215716, A215717, A215718, A247006, A247007, A247008. Main diagonal gives A247009. Cf. A247026 (the same for endofunctions). Sequence in context: A202480 A124341 A275062 * A174215 A305567 A134744 Adjacent sequences:  A247002 A247003 A247004 * A247006 A247007 A247008 KEYWORD nonn,tabl 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.

Last modified June 5 03:12 EDT 2020. Contains 334828 sequences. (Running on oeis4.)