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
Examples
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;
References
- P. Flajolet and R. Sedgewick, Analytic Combinatorics, Cambridge University Press, 2009, pages 120-122.
Links
- 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.
Crossrefs
Programs
-
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 *)
-
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
Formula
T(n, k) = n! / ( k^(n/k) * (n/k)! ) if k divides n otherwise 0.