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

Author

Dan Dima, Mar 01 2007

Keywords

• base
• nonn
• tabl

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

Examples

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

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.

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

Programs

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 (* Geoffrey Critzer, May 23 2009 *)

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

Formula

T(n,1) = 1.

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

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