Voozh

A293211

Triangle T(n,k) is the number of permutations on n elements with at least one k-cycle for 1 <= k <= n.

1, 1, 1, 4, 3, 2, 15, 9, 8, 6, 76, 45, 40, 30, 24, 455, 285, 200, 180, 144, 120, 3186, 1995, 1400, 1260, 1008, 840, 720, 25487, 15855, 11200, 8820, 8064, 6720, 5760, 5040, 229384, 142695, 103040, 79380, 72576, 60480, 51840, 45360, 40320, 2293839, 1427895, 1030400, 793800, 653184, 604800, 518400, 453600, 403200, 362880

(list; table; graph; refs; listen; history; text; internal format)

OFFSET

1,4

COMMENTS

T(n,k) is equivalent to n! minus the number of permutations on n elements with zero k-cycles (sequence A122974).

LINKS

Table of n, a(n) for n=1..55.

Dennis P. Walsh, The number of permutations with no k-cycles

FORMULA

T(n,k) = n! * Sum_{j=1..floor(n/k)} (-1)^(j+1)*(1/k)^j/j!.

T(n,k) = n! - A122974(n,k).

E.g.f. of column k: (1-exp(-x^k/k))/(1-x). - Alois P. Heinz, Oct 11 2017

EXAMPLE

T(n,k) (the first 8 rows):

: 1;

: 1, 1;

: 4, 3, 2;

: 15, 9, 8, 6;

: 76, 45, 40, 30, 24;

: 455, 285, 200, 180, 144, 120;

: 3186, 1995, 1400, 1260, 1008, 840, 720;

: 25487, 15855, 11200, 8820, 8064, 6720, 5760, 5040;

...

T(4,3)=8 since there are exactly 8 permutations on {1,2,3,4} with at least one 3-cycle: (1)(234), (1)(243), (2)(134), (2)(143), (3)(124), (3)(142), (4)(123), and (4)(132).

MAPLE

T:=(n, k)->n!*sum((-1)^(j+1)*(1/k)^j/j!, j=1..floor(n/k)); seq(seq(T(n, k), k=1..n), n=1..10);

MATHEMATICA

Table[n!*Sum[(-1)^(j + 1)*(1/k)^j/j!, {j, Floor[n/k]}], {n, 10}, {k, n}] // Flatten (* Michael De Vlieger, Oct 02 2017 *)

CROSSREFS

Columns k=1-10 give: A002467, A027616, A027617, A029571, A029572, A029573, A029574, A029575, A029576, A029577.

Row sums give A132961.

T(n,n) gives A000142(n-1) for n>0.

T(2n,n) gives A052145.

Cf. A122974, A126074.

Sequence in context: A202696 A319541 A239020 * A330778 A061312 A019130

Adjacent sequences: A293208 A293209 A293210 * A293212 A293213 A293214