A136125 - OEIS

A136125

Triangle read by rows: T(n,k) is the number of permutations of {1,2,...,n} in which the size of the last cycle is k (the cycles are ordered by increasing smallest elements; 1 <= k <=n).

1, 1, 1, 3, 1, 2, 12, 4, 2, 6, 60, 20, 10, 6, 24, 360, 120, 60, 36, 24, 120, 2520, 840, 420, 252, 168, 120, 720, 20160, 6720, 3360, 2016, 1344, 960, 720, 5040, 181440, 60480, 30240, 18144, 12096, 8640, 6480, 5040, 40320

(list; table; graph; refs; listen; history; text; internal format)

OFFSET

1,4

COMMENTS

Row sums are the factorials (A000142). T(n,1)=n!/2 for n>=2; Sum(k*T(n,k),k=1..n)=s(n,2)=A000254(n) (Stirling numbers of the first kind).

LINKS

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

FORMULA

T(n,k) = n!/[k(k+1)] if k<n; T(n,n)=(n-1)!.

Rec. rel.: T(n,k) = (n-1-k)*T(n-1,k) + (k-1)T(n-1,k-1) for 1 < k < n.

EXAMPLE

T(4,2) = 4 because we have (1)(2)(34), (13)(24), (12)(34) and (14)(23).

Triangle starts:

1, 1;

3, 1, 2;

12, 4, 2, 6;

60, 20, 10, 6, 24;

MAPLE

T:=proc(n, k) if k < n then factorial(n)/(k*(k+1)) elif k = n then factorial(n-1) else 0 end if end proc: for n to 9 do seq(T(n, k), k=1..n) end do; # yields sequence in triangular form

# second Maple program:

b:= proc(n, l) option remember; `if`(n=0, x^l, add(

binomial(n-1, j-1)*b(n-j, j)*(j-1)!, j=1..n))

end:

T:= n-> (p-> (seq(coeff(p, x, i), i=1..n)))(b(n, 0)):

seq(T(n), n=1..12); # Alois P. Heinz, Dec 08 2018

MATHEMATICA

T[n_, n_] := (n-1)!;

T[n_, k_] := n!/(k(k+1));

Table[T[n, k], {n, 1, 12}, {k, 1, n}] // Flatten (* Jean-François Alcover, Dec 09 2019 *)

CROSSREFS

Cf. A000142, A000254.