login
The OEIS is supported by the many generous donors to the OEIS 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
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
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 | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 05:39 EDT 2024. Contains 371235 sequences. (Running on oeis4.)