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

0, 0, 1, 0, 3, 4, 0, 9, 16, 18, 0, 45, 80, 90, 96, 0, 225, 400, 540, 576, 600, 0, 1575, 2800, 3780, 4032, 4200, 4320, 0, 11025, 22400, 26460, 32256, 33600, 34560, 35280, 0, 99225, 179200, 238140, 290304, 302400, 311040, 317520, 322560, 0, 893025, 1792000, 2381400, 2612736, 3024000, 3110400, 3175200, 3225600, 3265920

Offset

1,5

Links

Alois P. Heinz, Rows n = 1..141, flattened

E. D. Bolker and A. M. Gleason, Counting permutations, J. Combin. Thy., A 29 (1980), 236-242.

Example

Triangle begins
[0],
[0, 1],
[0, 3, 4],
[0, 9, 16, 18],
[0, 45, 80, 90, 96],
[0, 225, 400, 540, 576, 600],
[0, 1575, 2800, 3780, 4032, 4200, 4320],
[0, 11025, 22400, 26460, 32256, 33600, 34560, 35280],
[0, 99225, 179200, 238140, 290304, 302400, 311040, 317520, 322560],
[0, 893025, 1792000, 2381400, 2612736, 3024000, 3110400, 3175200, 3225600, 3265920],
[0, 9823275, 19712000, 26195400, 28740096, 33264000, 34214400, 34927200, 35481600, 35925120, 36288000],
[0, 108056025, 216832000, 288149400, 344881152, 365904000, 410572800, 419126400, 425779200, 431101440, 435456000, 439084800],
...

Maple

read transforms;
f:=(n, d)->mul(j-did(j, d), j=1..n); # did(d, j) = 1 iff j divides d, otherwise 0
g:=n->[seq(f(n, d), d=1..n)];
[seq(g(n), n=1..14)];
# second Maple program:
T:= proc(n, k) option remember; `if`(n=0, 1, add(
      `if`(irem(j, k)=0, 0, binomial(n-1, j-1)*(j-1)!*
       T(n-j, k)), j=1..n))
    end:
seq(seq(T(n, k), k=1..n), n=1..12);  # Alois P. Heinz, May 14 2016

Mathematica

T[n_, k_] := T[n, k] = If[n == 0, 1, Sum[If[Mod[j, k] == 0, 0, Binomial[n - 1, j - 1]*(j - 1)!*T[n - j, k]], {j, 1, n}]];
Table[T[n, k], {n, 1, 12}, {k, 1, n}] // Flatten (* Jean-François Alcover, May 26 2016, after Alois P. Heinz *)

Crossrefs

Cf. A001563 (diagonal of triangle), A213279.

Sequence in context: A308642 A158674 A077628 * A056862 A113035 A374195

Adjacent sequences: A213277 A213278 A213279 * A213281 A213282 A213283

Keyword

nonn,tabl

Author

N. J. A. Sloane, Jun 08 2012

Status

approved