A247007 -id:A247007 - 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.

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

Offset: 0

Alois P. Heinz, Sep 09 2014

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

			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, ...

Alois P. Heinz, Antidiagonals n = 0..140, flattened
William Y. C. Chen and Elena L. Wang, r-Enriched Permutations and an Inequality of Bóna-McLennan-White, arXiv:2502.04136 [math.CO], 2025. See pp. 3, 14.
H. S. Wilf, Generatingfunctionology, 2nd edn., Academic Press, NY, 1994, Theorem 4.8.2.

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), A155510.

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);

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 *)

A102736 Number of permutations of n elements without cycles whose length is a multiple of 3.

Original entry on oeis.org

1, 1, 2, 4, 16, 80, 400, 2800, 22400, 179200, 1792000, 19712000, 216832000, 2818816000, 39463424000, 552487936000, 8839806976000, 150276718592000, 2554704216064000, 48539380105216000, 970787602104320000, 19415752042086400000, 427146544925900800000, 9824370533295718400000, 225960522265801523200000, 5649013056645038080000000, 146874339472770990080000000, 3818732826292045742080000000

Offset: 0

Vladeta Jovovic, Feb 08 2005

Differs from A247007 first at n=27. - Alois P. Heinz, Sep 09 2014

			G.f. = 1 + x + 2*x^2 + 4*x^3 + 16*x^4 + 80*x^5 + 400*x^6 + 2800*x^7 + ...

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

Cf. A000090, A000246.

a:= proc(n) option remember; `if`(n=0, 1, add(`if`(
      irem(j, 3)=0, 0, a(n-j)*(j-1)!*binomial(n-1, j-1)), j=1..n))
    end:
seq(a(n), n=0..27);  # Alois P. Heinz, Jul 31 2017

nn=21;a=Sum[x^n/n,{n,3,nn,3}];Range[0,nn]!CoefficientList[Series[Exp[Log[1/(1-x)]-a],{x,0,nn}],x]  (* Geoffrey Critzer, Nov 11 2012 *)
a[ n_] := If[ n < 0, 0, n! With[{m = Quotient[n, 3]}, (-1)^m Binomial[-2/3, m]]]; (* Michael Somos, Aug 05 2016 *)

{a(n) = my(m); if( n<0, 0, m = n\3; n! * (-1)^m * binomial(-2/3, m))}; /* Michael Somos, Aug 05 2016 */

E.g.f.: (1-x^3)^(1/3)/(1-x).

a(n) ~ n! * 3^(1/3) / (GAMMA(2/3) * n^(1/3)). - Vaclav Kotesovec, Mar 15 2014

A155510 Possible cardinalities of the set of all k-th powers of the order n permutations, where k and n are some positive integers.

Original entry on oeis.org

1, 2, 3, 4, 6, 9, 12, 16, 21, 24, 25, 36, 40, 45, 46, 56, 60, 80, 81, 96, 106, 120, 126, 145, 190, 225, 256, 270, 351, 400, 505, 576, 610, 666, 720, 721, 826, 855, 946, 1071, 1072, 1170, 1225, 1233, 1330, 1338, 1345, 1386, 1450, 1575, 1576, 1792, 1890, 2080, 2241

Offset: 1

Vladimir Letsko, Jan 23 2009

nonn

			80 is in the sequence because the set {a^3|a in S_5} has 80 elements.

Vladimir Letsko, Mathematical Marathon at VSPU, Problem 100 (in Russian)
Vladimir Letsko, Mathematical Marathon at dxdy (in Russian)

Set of elements of A247005.

Cf. A000012, A000142, A003483, A103619, A103620, A215716, A215717, A215718, A247006, A247007, A247008, A247009.

Corrected and extended by Max Alekseyev, Feb 08 2009

Some missing terms added by Max Alekseyev, Jan 24 2010

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A102736 Number of permutations of n elements without cycles whose length is a multiple of 3.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A155510 Possible cardinalities of the set of all k-th powers of the order n permutations, where k and n are some positive integers.

Views

Author

Keywords

Examples

Links

Crossrefs

Extensions