A346085 - OEIS

%I #23 Mar 01 2024 14:57:42

%S 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,

%T 4320,0,0,0,0,0,720,0,29295,4725,0,1260,0,0,0,5040,0,300160,0,22400,0,

%U 0,0,0,0,40320,0,2663199,530145,0,0,72576,0,0,0,0,362880

%N 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.

%H Alois P. Heinz, <a href="/A346085/b346085.txt">Rows n = 0..140, flattened</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Permutation">Permutation</a>

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

%F Sum_{prime p <= n} T(n,p) = A359951(n). - _Alois P. Heinz_, Jan 20 2023

%e T(3,1) = 4: (1)(23), (13)(2), (12)(3), (1)(2)(3).

%e T(4,4) = 6: (1234), (1243), (1324), (1342), (1423), (1432).

%e Triangle T(n,k) begins:

%e   1;

%e   0,       1;

%e   0,       1,      1;

%e   0,       4,      0,     2;

%e   0,      15,      3,     0,    6;

%e   0,      96,      0,     0,    0,    24;

%e   0,     455,    105,    40,    0,     0, 120;

%e   0,    4320,      0,     0,    0,     0,   0, 720;

%e   0,   29295,   4725,     0, 1260,     0,   0,   0, 5040;

%e   0,  300160,      0, 22400,    0,     0,   0,   0,    0, 40320;

%e   0, 2663199, 530145,     0,    0, 72576,   0,   0,    0,     0, 362880;

%e   ...

%p b:= proc(n, g) option remember; `if`(n=0, x^g, add((j-1)!

%p       *b(n-j, igcd(g, j))*binomial(n-1, j-1), j=1..n))

%p     end:

%p T:= n-> (p-> seq(coeff(p, x, i), i=0..n))(b(n, 0)):

%p seq(T(n), n=0..12);

%t b[n_, g_] := b[n, g] = If[n == 0, x^g, Sum[(j - 1)!*

%t      b[n - j, GCD[g, j]] Binomial[n - 1, j - 1], {j, n}]];

%t T[n_] := CoefficientList[b[n, 0], x];

%t Table[T[n], {n, 0, 12}] // Flatten (* _Jean-François Alcover_, Aug 30 2021, after _Alois P. Heinz_ *)

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

%Y Even bisection of column k=2 gives A346086.

%Y Row sums give A000142.

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

%Y Cf. A057731, A145877, A346066, A359951.

%K nonn,tabl

%O 0,8

%A _Alois P. Heinz_, Jul 04 2021