A136394 Triangle read by rows: T(n,k) is the number of permutations of an n-set having k cycles of size > 1 (0<=k<=floor(n/2)).

1, 1, 1, 1, 1, 5, 1, 20, 3, 1, 84, 35, 1, 409, 295, 15, 1, 2365, 2359, 315, 1, 16064, 19670, 4480, 105, 1, 125664, 177078, 56672, 3465, 1, 1112073, 1738326, 703430, 74025, 945, 1, 10976173, 18607446, 8941790, 1346345, 45045, 1, 119481284, 216400569, 118685336

Offset: 0

Author

Vladeta Jovovic, May 03 2008

Keywords

• easy
• nonn
• tabf
• look

Examples

			Triangle (n,k) begins:
  1;
  1;
  1,    1;
  1,    5;
  1,   20,    3;
  1,   84,   35;
  1,  409,  295,  15;
  1, 2365, 2359, 315;
  ...
		

Links

• Alois P. Heinz, Rows n = 0..200, flattened
• Jean-Luc Baril and Sergey Kirgizov, Transformation à la Foata for special kinds of descents and excedances, arXiv:2101.01928 [math.CO], 2021. See Theorem 2. p. 5.
• FindStat - Combinatorial Statistic Finder, The number of nontrivial cycles of a permutation pi in its cycle decomposition
• Bin Han, Jianxi Mao, and Jiang Zeng, Equidistributions around special kinds of descents and excedances, arXiv:2103.13092 [math.CO], 2021, see page 2.

Crossrefs

Columns k=0-10 give: A000012, A006231, A289950, A289951, A289952, A289953, A289954, A289955, A289956, A289957, A289958.

Row sums give A000142.

Cf. A000276, A000483, A001147, A001705, A051577, A124324, A159964.

Programs

Maple

egf:= proc(k::nonnegint) option remember; x-> exp(x)* ((-x-ln(1-x))^k)/k! end; T:= (n,k)-> coeff(series(egf(k)(x), x=0, n+1), x, n) *n!; seq(seq(T(n,k), k=0..n/2), n=0..30); # Alois P. Heinz, Aug 14 2008
# second Maple program:
b:= proc(n) option remember; expand(`if`(n=0, 1, add(b(n-i)*
      `if`(i>1, x, 1)*binomial(n-1, i-1)*(i-1)!, i=1..n)))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n)):
seq(T(n), n=0..15);  # Alois P. Heinz, Sep 25 2016
# third Maple program:
T:= proc(n, k) option remember; `if`(k<0 or k>2*n, 0,
      `if`(n=0, 1, add(T(n-i, k-`if`(i>1, 1, 0))*
       mul(n-j, j=1..i-1), i=1..n)))
    end:
seq(seq(T(n,k), k=0..n/2), n=0..15);  # Alois P. Heinz, Jul 16 2017

Mathematica

max = 12; egf = Exp[x*(1-y)]/(1-x)^y; s = Series[egf, {x, 0, max}, {y, 0, max}] // Normal; t[n_, k_] := SeriesCoefficient[s, {x, 0, n}, {y, 0, k}]*n!; t[0, 0] = t[1, 0] = 1; Table[t[n, k], {n, 0, max}, {k, 0, n/2}] // Flatten (* Jean-François Alcover, Jan 28 2014 *)

Formula

E.g.f.: exp(x*(1-y))/(1-x)^y. Binomial transform of triangle A008306. exp(x)*((-x-log(1-x))^k)/k! is e.g.f. of k-th column.

From Alois P. Heinz, Jul 13 2017: (Start)

T(2n,n) = A001147(n).

T(2n+1,n) = A051577(n) = (2*n+3)!!/3 = A001147(n+2)/3. (End)

From Alois P. Heinz, Aug 17 2023: (Start)

Sum_{k=0..floor(n/2)} k * T(n,k) = A001705(n-1) for n>=1.

Sum_{k=0..floor(n/2)} (-1)^k * T(n,k) = A159964(n-1) for n>=1. (End)