cp's OEIS Frontend

A126074 Triangle read by rows: T(n,k) is the number of permutations of n elements that have the longest cycle length k.

%I A126074 #65 Aug 12 2025 03:40:58
%S A126074 1,1,1,1,3,2,1,9,8,6,1,25,40,30,24,1,75,200,180,144,120,1,231,980,
%T A126074 1260,1008,840,720,1,763,5152,8820,8064,6720,5760,5040,1,2619,28448,
%U A126074 61236,72576,60480,51840,45360,40320,1,9495,162080,461160,653184,604800,518400,453600,403200,362880
%N A126074 Triangle read by rows: T(n,k) is the number of permutations of n elements that have the longest cycle length k.
%C A126074 Sum of the n-th row is the number of all permutations of n elements: Sum_{k=1..n, T(n,k)} = n! = A000142(n) We can extend T(n,k)=0, if k<=0 or k>n.
%C A126074 From _Peter Luschny_, Mar 07 2009: (Start)
%C A126074 Partition product of prod_{j=0..n-2}(k-n+j+2) and n! at k = -1, summed over parts with equal biggest part (see the Luschny link).
%C A126074 Underlying partition triangle is A102189.
%C A126074 Same partition product with length statistic is A008275.
%C A126074 Diagonal a(A000217(n)) = rising_factorial(1,n-1), A000142(n-1) (n > 0).
%C A126074 Row sum is A000142. (End)
%C A126074 Let k in {1,2,3,...} index the family of sequences A000012, A000085, A057693, A070945, A070946, A070947, ... respectively. Column k is the k-th sequence minus its immediate predecessor. For example, T(5,3)=A057693(5)-A000085(5). - _Geoffrey Critzer_, May 23 2009
%H A126074 Alois P. Heinz, <a href="/A126074/b126074.txt">Rows n = 1..141, flattened</a>
%H A126074 Steven Finch, <a href="https://arxiv.org/abs/2111.05720">Permute, Graph, Map, Derange</a>, arXiv:2111.05720 [math.CO], 2021.
%H A126074 S. W. Golomb and P. Gaal, <a href="https://doi.org/10.1006/aama.1997.0567">On the number of permutations of n objects with greatest cycle length k</a>, Adv. in Appl. Math., 20(1), 1998, 98-107.
%H A126074 IBM Research, <a href="https://research.ibm.com/haifa/ponderthis/challenges/December2006.html">Ponder This</a>, December 2006.
%H A126074 Peter Luschny, <a href="http://www.luschny.de/math/seq/CountingWithPartitions.html">Counting with Partitions</a>. [From _Peter Luschny_, Mar 07 2009]
%H A126074 Peter Luschny, <a href="http://www.luschny.de/math/seq/stirling1partitions.html">Generalized Stirling_1 Triangles</a>. [From _Peter Luschny_, Mar 07 2009]
%H A126074 D. Panario and B. Richmond, <a href="https://doi.org/10.1007/s00453-001-0047-1">Exact largest and smallest size of components</a>, Algorithmica, 31 (2001), 413-432.
%F A126074 T(n,1) = 1.
%F A126074 T(n,2) = n! * Sum_{k=1..[n/2]} 1/(k! * (2!)^k * (n-2*k)!).
%F A126074 T(n,k) = n!/k * (1-1/(n-k)-...-1/(k+1)-1/2k), if n/3 < k <= n/2.
%F A126074 T(n,k) = n!/k, if n/2 < k <= n.
%F A126074 T(n,n) = (n-1)! = A000142(n-1).
%F A126074 E.g.f. for k-th column: exp(-x^k*LerchPhi(x,1,k))*(exp(x^k/k)-1)/(1-x). - _Vladeta Jovovic_, Mar 03 2007
%F A126074 From _Peter Luschny_, Mar 07 2009: (Start)
%F A126074 T(n,0) = [n = 0] (Iverson notation) and for n > 0 and 1 <= m <= n
%F A126074 T(n,m) = Sum_{a} M(a)|f^a| where a = a_1,..,a_n such that
%F A126074 1*a_1+2*a_2+...+n*a_n = n and max{a_i} = m, M(a) = n!/(a_1!*..*a_n!),
%F A126074 f^a = (f_1/1!)^a_1*..*(f_n/n!)^a_n and f_n = product_{j=0..n-2}(j-n+1). (End)
%F A126074 Sum_{k=1..n} k * T(n,k) = A028418(n). - _Alois P. Heinz_, May 17 2016
%e A126074 Triangle T(n,k) begins:
%e A126074   1;
%e A126074   1,   1;
%e A126074   1,   3,    2;
%e A126074   1,   9,    8,    6;
%e A126074   1,  25,   40,   30,   24;
%e A126074   1,  75,  200,  180,  144,  120;
%e A126074   1, 231,  980, 1260, 1008,  840,  720;
%e A126074   1, 763, 5152, 8820, 8064, 6720, 5760, 5040;
%e A126074   ...
%p A126074 A:= proc(n,k) option remember; `if`(n<0, 0, `if`(n=0, 1,
%p A126074        add(mul(n-i, i=1..j-1)*A(n-j,k), j=1..k)))
%p A126074     end:
%p A126074 T:= (n, k)-> A(n, k) -A(n, k-1):
%p A126074 seq(seq(T(n,k), k=1..n), n=1..10);  # _Alois P. Heinz_, Feb 11 2013
%t A126074 Table[CoefficientList[ Series[(Exp[x^m/m] - 1) Exp[Sum[x^k/k, {k, 1, m - 1}]], {x, 0, 8}], x]*Table[n!, {n, 0, 8}], {m, 1, 8}] // Transpose // Grid (* _Geoffrey Critzer_, May 23 2009 *)
%o A126074 (Sage)
%o A126074 def A126074(n, k):
%o A126074     f = factorial(n)
%o A126074     P = Partitions(n, max_part=k, inner=[k])
%o A126074     return sum(f // p.aut() for p in P)
%o A126074 for n in (1..9): print([A126074(n,k) for k in (1..n)]) # _Peter Luschny_, Apr 17 2016
%Y A126074 Cf. A000142.
%Y A126074 Cf. A071007, A080510, A028418.
%Y A126074 Cf. A157386, A157385, A157384, A157383, A157400, A157391, A157392, A157393, A157394, A157395. - _Peter Luschny_, Mar 07 2009
%Y A126074 T(2n,n) gives A052145 (for n>0). - _Alois P. Heinz_, Apr 21 2017
%K A126074 base,nonn,tabl
%O A126074 1,5
%A A126074 _Dan Dima_, Mar 01 2007