cp's OEIS Frontend

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.

%I A247005 #27 Feb 10 2025 11:18:00
%S A247005 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,
%T A247005 16,60,720,1,1,1,1,6,9,80,270,5040,1,1,1,2,1,24,45,400,1890,40320,1,1,
%U A247005 1,1,6,4,96,225,2800,14280,362880,1,1,1,2,3,24,40,576,1575,22400,128520,3628800,1
%N 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.
%C A247005 Number of permutations p on [n] such that a permutation q on [n] exists with p=q^k.
%H A247005 Alois P. Heinz, <a href="/A247005/b247005.txt">Antidiagonals n = 0..140, flattened</a>
%H A247005 William Y. C. Chen and Elena L. Wang, <a href="https://arxiv.org/abs/2502.04136">r-Enriched Permutations and an Inequality of Bóna-McLennan-White</a>, arXiv:2502.04136 [math.CO], 2025. See pp. 3, 14.
%H A247005 H. S. Wilf, <a href="http://www.math.upenn.edu/~wilf/DownldGF.html">Generatingfunctionology</a>, 2nd edn., Academic Press, NY, 1994, Theorem 4.8.2.
%e A247005 A(3,0) = 1: (1,2,3).
%e A247005 A(3,1) = 6: (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1).
%e A247005 A(3,2) = 3: (1,2,3), (2,3,1), (3,1,2).
%e A247005 A(3,3) = 4: (1,2,3), (1,3,2), (2,1,3), (3,2,1).
%e A247005 Square array A(n,k) begins:
%e A247005   1,    1,    1,    1,    1,    1,    1,    1,    1, ...
%e A247005   1,    1,    1,    1,    1,    1,    1,    1,    1, ...
%e A247005   1,    2,    1,    2,    1,    2,    1,    2,    1, ...
%e A247005   1,    6,    3,    4,    3,    6,    1,    6,    3, ...
%e A247005   1,   24,   12,   16,    9,   24,    4,   24,    9, ...
%e A247005   1,  120,   60,   80,   45,   96,   40,  120,   45, ...
%e A247005   1,  720,  270,  400,  225,  576,  190,  720,  225, ...
%e A247005   1, 5040, 1890, 2800, 1575, 4032, 1330, 4320, 1575, ...
%p A247005 with(combinat): with(numtheory): with(padic):
%p A247005 b:= proc(n, i, k) option remember; `if`(n=0, 1, `if`(i<1, 0, add(
%p A247005       `if`(irem(j, mul(p^ordp(k, p), p=factorset(i)))=0, (i-1)!^j*
%p A247005       multinomial(n, n-i*j, i$j)/j!*b(n-i*j, i-1, k), 0), j=0..n/i)))
%p A247005     end:
%p A247005 A:= (n, k)-> `if`(k=0, 1, b(n$2, k)):
%p A247005 seq(seq(A(n, d-n), n=0..d), d=0..14);
%t A247005 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_ *)
%Y A247005 Columns k=0-10 give: A000012, A000142, A003483, A103619, A103620, A215716, A215717, A215718, A247006, A247007, A247008.
%Y A247005 Main diagonal gives A247009.
%Y A247005 Cf. A247026 (the same for endofunctions), A155510.
%K A247005 nonn,tabl
%O A247005 0,9
%A A247005 _Alois P. Heinz_, Sep 09 2014