A122974 Triangle T(n,k), the number of permutations on n elements that have no cycles of length k.

0, 1, 1, 2, 3, 4, 9, 15, 16, 18, 44, 75, 80, 90, 96, 265, 435, 520, 540, 576, 600, 1854, 3045, 3640, 3780, 4032, 4200, 4320, 14833, 24465, 29120, 31500, 32256, 33600, 34560, 35280, 133496, 220185, 259840, 283500, 290304, 302400, 311040, 317520, 322560

Offset: 1

Author

Dennis P. Walsh, Oct 27 2006

Keywords

• easy
• tabl
• nonn

Comments

Read as sequence, a(n) is the number of permutations on j elements with no cycles of length i where j=round((2*n)^.5) and i=n-C(j,2).

T(n,k) generalizes several sequences already in the On-Line Encyclopedia, such as A000166, the number of permutations on n elements with no fixed points and A000266, the number of permutations on n elements with no transpositions (i.e., no 2-cycles). See the cross references for further examples.

Examples

			T(3,2)=3 since there are exactly 3 permutations of 1,2,3 that have no cycles of length 2, namely, (1)(2)(3),(1 2 3) and (2 1 3).
Triangle T(n,k) begins:
      0;
      1,     1;
      2,     3,     4;
      9,    15,    16,    18;
     44,    75,    80,    90,    96;
    265,   435,   520,   540,   576,   600;
   1854,  3045,  3640,  3780,  4032,  4200,  4320;
  14833, 24465, 29120, 31500, 32256, 33600, 34560, 35280;
  ...
		

Links

• Alois P. Heinz, Rows for n = 1..141, flattened
• Dennis P. Walsh, The Number of Permutations with No k-Cycles.

Crossrefs

Cf. T(n, 1)=A000166 for n=>1 T(n, 2)=A000266 for n=>2 T(n, 3)=A000090 for n=>3 T(n, 4)=A000138 for n=>4 T(n, 5)=A060725 for n=>5 T(n, 6)=A060726 for n=>6 T(n, 7)=A060727 for n=>7.

T(n,n) gives A094304(n+1).

Programs

Maple

seq((round((2*n)^.5))!*sum((-1/(n-binomial(round((2*n)^.5),2)))^r/r!,r=0..floor(round((2*n)^.5)/(n-binomial(round((2*n)^.5),2)))),n=1..66);
# second Maple program:
T:= proc(n, k) option remember; `if`(n=0, 1, add(`if`(j=k, 0,
      T(n-j, k)*binomial(n-1, j-1)*(j-1)!), j=1..n))
    end:
seq(seq(T(n, k), k=1..n), n=1..12);  # Alois P. Heinz, Nov 24 2019

Mathematica

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

Formula

T(n,k)=n!*sum r=0..floor(n/k)((-1/k)^r/r!) E.G.F: exp(-x^k/k)/(1-x) a(n)=(round((2*n)^.5))!*sum((-1/(n-binomial(round((2*n)^.5),2)))^r/r!,r=0..floor(round((2*n)^.5)/(n-binomial(round((2*n)^.5),2)))).

T(n,k) = n! - A293211(n,k). - Alois P. Heinz, Nov 24 2019