login
Triangle read by rows: T(n,k) (n>=1, 1 <= k <= n) = number of permutations of [1..n] in which all cycle lengths are divisible by k.
2

%I #25 May 24 2016 14:56:30

%S 1,2,1,6,0,2,24,9,0,6,120,0,0,0,24,720,225,160,0,0,120,5040,0,0,0,0,0,

%T 720,40320,11025,0,6300,0,0,0,5040,362880,0,62720,0,0,0,0,0,40320,

%U 3628800,893025,0,0,435456,0,0,0,0,362880,39916800,0,0,0,0,0,0,0,0,0,3628800

%N Triangle read by rows: T(n,k) (n>=1, 1 <= k <= n) = number of permutations of [1..n] in which all cycle lengths are divisible by k.

%H Alois P. Heinz, <a href="/A213279/b213279.txt">Rows n = 1..141, flattened</a>

%H E. D. Bolker and A. M. Gleason, <a href="http://dx.doi.org/10.1016/0097-3165(80)90012-6">Counting permutations</a>, J. Combin. Thy., A 29 (1980), 236-242.

%e Triangle begins

%e [1],

%e [2, 1],

%e [6, 0, 2],

%e [24, 9, 0, 6],

%e [120, 0, 0, 0, 24],

%e [720, 225, 160, 0, 0, 120],

%e [5040, 0, 0, 0, 0, 0, 720],

%e [40320, 11025, 0, 6300, 0, 0, 0, 5040],

%e [362880, 0, 62720, 0, 0, 0, 0, 0, 40320],

%e [3628800, 893025, 0, 0, 435456, 0, 0, 0, 0, 362880],

%e [39916800, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3628800],

%e [479001600, 108056025, 68992000, 56133000, 0, 46569600, 0, 0, 0, 0, 0, 39916800],

%e ...

%p read transforms;

%p f:=(n,d)->mul(n-j+did(j,d),j=1..n); # did(d,j) = 1 iff j divides d, otherwise 0

%p g:=n->[seq(f(n,d),d=1..n)];

%p [seq(g(n),n=1..14)];

%p # second Maple program:

%p T:= proc(n, k) option remember; `if`(n=0, 1, add(

%p `if`(irem(j, k)=0, binomial(n-1, j-1)*(j-1)!*

%p T(n-j, k), 0), j=1..n))

%p end:

%p seq(seq(T(n, k), k=1..n), n=1..12); # _Alois P. Heinz_, May 14 2016

%t T[n_, k_] := T[n, k] = If[n == 0, 1, Sum[If[Mod[j, k] == 0, Binomial[n-1, j -1] * (j-1)! * T[n-j, k], 0], {j, 1, n}]];

%t Table[T[n, k], {n, 1, 12}, {k, 1, n}] // Flatten (* _Jean-François Alcover_, May 24 2016, after _Alois P. Heinz_ *)

%Y Cf. A213280.

%K nonn,tabl

%O 1,2

%A _N. J. A. Sloane_, Jun 08 2012