cp's OEIS Frontend

A330858 Triangle read by rows: T(n,k) is the number of permutations in S_n for which all cycles have length <= k.

%I A330858 #52 Jul 08 2022 13:05:04
%S A330858 1,1,2,1,4,6,1,10,18,24,1,26,66,96,120,1,76,276,456,600,720,1,232,
%T A330858 1212,2472,3480,4320,5040,1,764,5916,14736,22800,29520,35280,40320,1,
%U A330858 2620,31068,92304,164880,225360,277200,322560,362880,1,9496,171576,632736
%N A330858 Triangle read by rows: T(n,k) is the number of permutations in S_n for which all cycles have length <= k.
%H A330858 Peter Kagey, <a href="/A330858/b330858.txt">Table of n, a(n) for n = 1..10011</a> (first 141 rows, flattened)
%H A330858 Steven Finch, <a href="http://arxiv.org/abs/2202.07621">Second best, Third worst, Fourth in line</a>, arxiv:2202.07621 [math.CO], 2022.
%F A330858 T(n,k) = n! if n <= k, otherwise T(n,k) = n*T(n-1,k) - A068424(n-1,k)*T(n-k-1,k).
%F A330858 T(n,k) = Sum_{j=1..k} A126074(n,j). - _Alois P. Heinz_, Jul 08 2022
%e A330858 For n = 3 and k = 2, the T(3,2) = 4 permutations in S_3 where all cycle lengths are less than or equal to 2 are:
%e A330858 (1)(2)(3), (12)(3), (13)(2), and (1)(23).
%e A330858 Table begins:
%e A330858 n\k| 1    2     3     4      5      6      7      8      9
%e A330858 ---+------------------------------------------------------
%e A330858   1| 1
%e A330858   2| 1    2
%e A330858   3| 1    4     6
%e A330858   4| 1   10    18    24
%e A330858   5| 1   26    66    96    120
%e A330858   6| 1   76   276   456    600    720
%e A330858   7| 1  232  1212  2472   3480   4320   5040
%e A330858   8| 1  764  5916 14736  22800  29520  35280  40320
%e A330858   9| 1 2620 31068 92304 164880 225360 277200 322560 362880
%t A330858 T[n_, k_] := T[n, k] = If[n <= k, n!, n*T[n-1, k] - FactorialPower[n-1, k]* T[n-k-1, k]];
%t A330858 Table[T[n, k], {n, 1, 10}, {k, 1, n}] // Flatten (* _Jean-François Alcover_, Apr 28 2020 *)
%o A330858 (PARI) T4(n, k)=if(k<1 || k>n, 0, n!/(n-k)!); \\ A068424
%o A330858 T(n,k) = if (n<=k, n!, n*T(n-1,k) - T4(n-1,k)*T(n-k-1,k));
%o A330858 tabl(nn) = for (n=1, nn, for (k=1, n, print1(T(n,k), ", ")); print); \\ _Michel Marcus_, May 09 2020
%Y A330858 Cf. A068424, A333726.
%Y A330858 Columns 2-6: A000085, A057693, A070945, A070946, A070947.
%Y A330858 T(n,floor(n/2)) gives A024168.
%Y A330858 Cf. A126074.
%K A330858 nonn,tabl
%O A330858 1,3
%A A330858 _Peter Kagey_, Apr 28 2020