cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

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

This page as a plain text file.
%I A122974 #16 Dec 08 2019 07:40:23
%S A122974 0,1,1,2,3,4,9,15,16,18,44,75,80,90,96,265,435,520,540,576,600,1854,
%T A122974 3045,3640,3780,4032,4200,4320,14833,24465,29120,31500,32256,33600,
%U A122974 34560,35280,133496,220185,259840,283500,290304,302400,311040,317520,322560
%N A122974 Triangle T(n,k), the number of permutations on n elements that have no cycles of length k.
%C A122974 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).
%C A122974 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.
%H A122974 Alois P. Heinz, <a href="/A122974/b122974.txt">Rows for n = 1..141, flattened</a>
%H A122974 Dennis P. Walsh, <a href="http://www.mtsu.edu/~dwalsh/NOKCYCLB.pdf">The Number of Permutations with No k-Cycles</a>.
%F A122974 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)))).
%F A122974 T(n,k) = n! - A293211(n,k). - _Alois P. Heinz_, Nov 24 2019
%e A122974 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).
%e A122974 Triangle T(n,k) begins:
%e A122974       0;
%e A122974       1,     1;
%e A122974       2,     3,     4;
%e A122974       9,    15,    16,    18;
%e A122974      44,    75,    80,    90,    96;
%e A122974     265,   435,   520,   540,   576,   600;
%e A122974    1854,  3045,  3640,  3780,  4032,  4200,  4320;
%e A122974   14833, 24465, 29120, 31500, 32256, 33600, 34560, 35280;
%e A122974   ...
%p A122974 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);
%p A122974 # second Maple program:
%p A122974 T:= proc(n, k) option remember; `if`(n=0, 1, add(`if`(j=k, 0,
%p A122974       T(n-j, k)*binomial(n-1, j-1)*(j-1)!), j=1..n))
%p A122974     end:
%p A122974 seq(seq(T(n, k), k=1..n), n=1..12);  # _Alois P. Heinz_, Nov 24 2019
%t A122974 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}]];
%t A122974 Table[Table[T[n, k], {k, 1, n}], {n, 1, 12}] // Flatten (* _Jean-François Alcover_, Dec 08 2019, after _Alois P. Heinz_ *)
%Y A122974 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.
%Y A122974 T(n,n) gives A094304(n+1).
%K A122974 easy,tabl,nonn
%O A122974 1,4
%A A122974 _Dennis P. Walsh_, Oct 27 2006