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

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

T(2n,n) gives A322450.

Sequence in context: A300973 A300930 A109528 * A092580 A004468 A254630

Adjacent sequences: A136122 A136123 A136124 * A136126 A136127 A136128

Keyword

nonn,tabl

Author

Emeric Deutsch, Jan 10 2008

Status

approved