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

%I #56 Aug 17 2023 12:44:31

%S 1,1,1,1,1,5,1,20,3,1,84,35,1,409,295,15,1,2365,2359,315,1,16064,

%T 19670,4480,105,1,125664,177078,56672,3465,1,1112073,1738326,703430,

%U 74025,945,1,10976173,18607446,8941790,1346345,45045,1,119481284,216400569,118685336

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

%H Alois P. Heinz, <a href="/A136394/b136394.txt">Rows n = 0..200, flattened</a>

%H Jean-Luc Baril and Sergey Kirgizov, <a href="https://arxiv.org/abs/2101.01928">Transformation à la Foata for special kinds of descents and excedances</a>, arXiv:2101.01928 [math.CO], 2021. See Theorem 2. p. 5.

%H FindStat - Combinatorial Statistic Finder, <a href="http://www.findstat.org/StatisticsDatabase/St000162/">The number of nontrivial cycles of a permutation pi in its cycle decomposition</a>

%H Bin Han, Jianxi Mao, and Jiang Zeng, <a href="https://arxiv.org/abs/2103.13092">Equidistributions around special kinds of descents and excedances</a>, arXiv:2103.13092 [math.CO], 2021, see page 2.

%F 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.

%F From _Alois P. Heinz_, Jul 13 2017: (Start)

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

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

%F From _Alois P. Heinz_, Aug 17 2023: (Start)

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

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

%e Triangle (n,k) begins:

%e 1;

%e 1;

%e 1, 1;

%e 1, 5;

%e 1, 20, 3;

%e 1, 84, 35;

%e 1, 409, 295, 15;

%e 1, 2365, 2359, 315;

%e ...

%p 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

%p # second Maple program:

%p b:= proc(n) option remember; expand(`if`(n=0, 1, add(b(n-i)*

%p `if`(i>1, x, 1)*binomial(n-1, i-1)*(i-1)!, i=1..n)))

%p end:

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

%p seq(T(n), n=0..15); # _Alois P. Heinz_, Sep 25 2016

%p # third Maple program:

%p T:= proc(n, k) option remember; `if`(k<0 or k>2*n, 0,

%p `if`(n=0, 1, add(T(n-i, k-`if`(i>1, 1, 0))*

%p mul(n-j, j=1..i-1), i=1..n)))

%p end:

%p seq(seq(T(n,k), k=0..n/2), n=0..15); # _Alois P. Heinz_, Jul 16 2017

%t 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 *)

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

%Y Row sums give A000142.

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

%K easy,nonn,tabf,look

%O 0,6

%A _Vladeta Jovovic_, May 03 2008