A346085 Number T(n,k) of permutations of [n] such that k is the GCD of the cycle lengths; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

1, 0, 1, 0, 1, 1, 0, 4, 0, 2, 0, 15, 3, 0, 6, 0, 96, 0, 0, 0, 24, 0, 455, 105, 40, 0, 0, 120, 0, 4320, 0, 0, 0, 0, 0, 720, 0, 29295, 4725, 0, 1260, 0, 0, 0, 5040, 0, 300160, 0, 22400, 0, 0, 0, 0, 0, 40320, 0, 2663199, 530145, 0, 0, 72576, 0, 0, 0, 0, 362880

Offset: 0

Author

Alois P. Heinz, Jul 04 2021

Keywords

• nonn
• tabl

Examples

			T(3,1) = 4: (1)(23), (13)(2), (12)(3), (1)(2)(3).
T(4,4) = 6: (1234), (1243), (1324), (1342), (1423), (1432).
Triangle T(n,k) begins:
  1;
  0,       1;
  0,       1,      1;
  0,       4,      0,     2;
  0,      15,      3,     0,    6;
  0,      96,      0,     0,    0,    24;
  0,     455,    105,    40,    0,     0, 120;
  0,    4320,      0,     0,    0,     0,   0, 720;
  0,   29295,   4725,     0, 1260,     0,   0,   0, 5040;
  0,  300160,      0, 22400,    0,     0,   0,   0,    0, 40320;
  0, 2663199, 530145,     0,    0, 72576,   0,   0,    0,     0, 362880;
  ...
		

Links

• Alois P. Heinz, Rows n = 0..140, flattened
• Wikipedia, Permutation

Crossrefs

Columns k=0-1 give: A000007, A079128.

Even bisection of column k=2 gives A346086.

Row sums give A000142.

T(2n,n) gives A110468(n-1) for n >= 1.

Cf. A057731, A145877, A346066, A359951.

Programs

Maple

b:= proc(n, g) option remember; `if`(n=0, x^g, add((j-1)!
      *b(n-j, igcd(g, j))*binomial(n-1, j-1), j=1..n))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..n))(b(n, 0)):
seq(T(n), n=0..12);

Mathematica

b[n_, g_] := b[n, g] = If[n == 0, x^g, Sum[(j - 1)!*
     b[n - j, GCD[g, j]] Binomial[n - 1, j - 1], {j, n}]];
T[n_] := CoefficientList[b[n, 0], x];
Table[T[n], {n, 0, 12}] // Flatten (* Jean-François Alcover, Aug 30 2021, after Alois P. Heinz *)

Formula

Sum_{k=1..n} k * T(n,k) = A346066(n).

Sum_{prime p <= n} T(n,p) = A359951(n). - Alois P. Heinz, Jan 20 2023