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
KEYWORD
nonn,tabl
AUTHOR
Alois P. Heinz, Sep 09 2014
STATUS
approved