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

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

Keyword

easy,nonn,tabl

Author

Dennis P. Walsh, Oct 02 2017

Status

approved