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

Links

Alois P. Heinz, Rows n = 0..140, flattened

Wikipedia, Permutation

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

Example

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

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

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.

Sequence in context: A324815 A019200 A324820 * A337996 A087604 A090538

Adjacent sequences: A346082 A346083 A346084 * A346086 A346087 A346088

Keyword

nonn,tabl

Author

Alois P. Heinz, Jul 04 2021

Status

approved