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

 

Logo


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.

License Agreements, Terms of Use, Privacy Policy. .

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