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

1, 1, 1, 1, 3, 2, 1, 9, 8, 6, 1, 25, 40, 30, 24, 1, 75, 200, 180, 144, 120, 1, 231, 980, 1260, 1008, 840, 720, 1, 763, 5152, 8820, 8064, 6720, 5760, 5040, 1, 2619, 28448, 61236, 72576, 60480, 51840, 45360, 40320, 1, 9495, 162080, 461160, 653184, 604800, 518400, 453600, 403200, 362880

Offset

1,5

Comments

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.

From Peter Luschny, Mar 07 2009: (Start)

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).

Underlying partition triangle is A102189.

Same partition product with length statistic is A008275.

Diagonal a(A000217(n)) = rising_factorial(1,n-1), A000142(n-1) (n > 0).

Row sum is A000142. (End)

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

Links

Alois P. Heinz, Rows n = 1..141, flattened

Steven Finch, Permute, Graph, Map, Derange, arXiv:2111.05720 [math.CO], 2021.

S. W. Golomb and P. Gaal, On the number of permutations of n objects with greatest cycle length k, Adv. in Appl. Math., 20(1), 1998, 98-107.

IBM Research, Ponder This, December 2006.

Peter Luschny, Counting with Partitions. [From Peter Luschny, Mar 07 2009]

Peter Luschny, Generalized Stirling_1 Triangles. [From Peter Luschny, Mar 07 2009]

D. Panario and B. Richmond, Exact largest and smallest size of components, Algorithmica, 31 (2001), 413-432.

Formula

T(n,1) = 1 T(n,2) = n! * Sum_{k=1..[n/2], (1/(k! * (2!)^k * (n-2k)!)} T(n,k) = n!/k * (1-1/(n-k)-...-1/(k+1)-1/2k), if n/3 < k <= n/2 T(n,k) = n!/k, if n/2 < k <= n T(n,n) = (n-1)! = A000142(n-1)

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

From Peter Luschny, Mar 07 2009: (Start)

T(n,0) = [n = 0] (Iverson notation) and for n > 0 and 1 <= m <= n

T(n,m) = Sum_{a} M(a)|f^a| where a = a_1,..,a_n such that

1*a_1+2*a_2+...+n*a_n = n and max{a_i} = m, M(a) = n!/(a_1!*..*a_n!),

f^a = (f_1/1!)^a_1*..*(f_n/n!)^a_n and f_n = product_{j=0..n-2}(j-n+1). (End)

Sum_{k=1..n} k * T(n,k) = A028418(n). - Alois P. Heinz, May 17 2016

Example

Triangle T(n,k) begins:
  1;
  1,   1;
  1,   3,    2;
  1,   9,    8,    6;
  1,  25,   40,   30,   24;
  1,  75,  200,  180,  144,  120;
  1, 231,  980, 1260, 1008,  840,  720;
  1, 763, 5152, 8820, 8064, 6720, 5760, 5040;
  ...

Maple

A:= proc(n, k) option remember; `if`(n<0, 0, `if`(n=0, 1,
       add(mul(n-i, i=1..j-1)*A(n-j, k), j=1..k)))
    end:
T:= (n, k)-> A(n, k) -A(n, k-1):
seq(seq(T(n, k), k=1..n), n=1..10);  # Alois P. Heinz, Feb 11 2013

Mathematica

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 [From Geoffrey Critzer, May 23 2009]

Prog

(Sage)
def A126074(n, k):
    f = factorial(n)
    P = Partitions(n, max_part=k, inner=[k])
    return sum(f // p.aut() for p in P)
for n in (1..9): print([A126074(n, k) for k in (1..n)]) # Peter Luschny, Apr 17 2016

Crossrefs

Cf. A000142.

Cf. A071007, A080510, A028418.

Cf. A157386, A157385, A157384, A157383, A157400, A157391, A157392, A157393, A157394, A157395. - Peter Luschny, Mar 07 2009

T(2n,n) gives A052145 (for n>0). - Alois P. Heinz, Apr 21 2017

Sequence in context: A155788 A108073 A057731 * A108916 A119421 A121581

Adjacent sequences: A126071 A126072 A126073 * A126075 A126076 A126077

Keyword

base,nonn,tabl

Author

Dan Dima, Mar 01 2007

Status

approved