A368213 Triangular array read by rows: Number of permutations of [n] that factor into exactly k-cycles, ordered by n (rows) and divisors k of n (columns).

1, 1, 1, 1, 0, 2, 1, 3, 0, 6, 1, 0, 0, 0, 24, 1, 15, 40, 0, 0, 120, 1, 0, 0, 0, 0, 0, 720, 1, 105, 0, 1260, 0, 0, 0, 5040, 1, 0, 2240, 0, 0, 0, 0, 0, 40320, 1, 945, 0, 0, 72576, 0, 0, 0, 0, 362880, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3628800, 1, 10395, 246400, 1247400, 0, 6652800, 0, 0, 0, 0, 0, 39916800

Offset

1,6

References

P. Flajolet and R. Sedgewick, Analytic Combinatorics, Cambridge University Press, 2009, pages 120-122.

Links

Table of n, a(n) for n=1..78.

Marko Riedel, math.stackexchange.com, Number of permutations in the symmetric group.

Marko Riedel, Computing the number of permutations of [n] with k m-cycles with analytic combinatorics.

Marko Riedel, Computing the number of permutations of [n] with k m-cycles using the principle of inclusion-exclusion.

Formula

T(n, k) = n! / ( k^(n/k) * (n/k)! ) if k divides n otherwise 0.

Example

Row n=6 is 1, 15, 40, 120 because there is one permutation of [6] consisting of six fixed points, there are 15 permutations consisting of three transpositions, there are forty permutations consisting of two three-cycles and there are one hundred and twenty permutations consisting of just one six-cycle (6!/6).
Triangular array starts:
[ 1] 1;
[ 2] 1,   1;
[ 3] 1,   0,    2;
[ 4] 1,   3,    0,    6;
[ 5] 1,   0,    0,    0,    24;
[ 6] 1,  15,   40,    0,     0, 120;
[ 7] 1,   0,    0,    0,     0,   0, 720;
[ 8] 1, 105,    0, 1260,     0,   0,   0, 5040;
[ 9] 1,   0, 2240,    0,     0,   0,   0,    0, 40320;
[10] 1, 945,    0,    0, 72576,   0,   0,    0,     0, 362880;

Maple

T:= (n, m)-> `if`(irem(n, m)=0, n!/m^(n/m)/(n/m)!, 0):
seq(seq(T(n, m), m = 1..n), n=1..15);

Mathematica

A368213[n_, k_]:=If[Divisible[n, k], n!/(k^(n/k)(n/k)!), 0];
Table[A368213[n, k], {n, 15}, {k, n}] (* Paolo Xausa, Dec 18 2023 *)

Prog

(SageMath)
def T(n, d): return factorial(n) // (d ** (n//d) * factorial(n//d))
for n in range(1, 19):
    print([T(n, d) if n % d == 0 else 0 for d in range(1, n+1)])
# Peter Luschny, Dec 17 2023

Crossrefs

Cf. A005225 (row sums), A008290.

Cf. A123023 (column 2), A052502 (column 3), A060706 (column 4).

Sequence in context: A078024 A112469 A330502 * A249455 A248967 A331094

Adjacent sequences: A368210 A368211 A368212 * A368214 A368215 A368216

Keyword

nonn,tabl

Author

Marko Riedel, Dec 17 2023

Status

approved