The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A122974 Triangle T(n,k), the number of permutations on n elements that have no cycles of length k. 3
 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 (list; table; graph; refs; listen; history; text; internal format)
 OFFSET 1,4 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. LINKS Alois P. Heinz, Rows for n = 1..141, flattened Dennis P. Walsh, The Number of Permutations with No k-Cycles. 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 EXAMPLE 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;   ... 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 *) 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). Sequence in context: A342532 A133993 A341824 * A032982 A288856 A033076 Adjacent sequences:  A122971 A122972 A122973 * A122975 A122976 A122977 KEYWORD easy,tabl,nonn AUTHOR Dennis P. Walsh, Oct 27 2006 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified June 21 07:27 EDT 2021. Contains 345358 sequences. (Running on oeis4.)