A186526 - OEIS

%I #37 May 20 2020 16:07:09

%S 1,1,2,4,2,16,8,80,40,520,160,40,3640,1120,280,29120,8960,2240,259840,

%T 87360,13440,2240,2598400,873600,134400,22400,28582400,9609600,

%U 1478400,246400,343235200,114329600,19219200,1971200,246400,4462057600,1486284800,249849600,25625600,3203200,62468806400,20807987200,3497894400,358758400,44844800,936987251200,312344032000,52019968000,5829824000,448448000,44844800

%N Number T(n,k) of permutations on n elements with exactly k 3-cycles; triangle read by rows.

%C Triangle T(n,k) with 0<=k<=floor(n/3) gives the number of permutations in the symmetric group Sn that have exactly k cycles of length 3. The sum of T(n,k) over all k equals n!.

%D Arratia, R. and Tavaré, S. (1992). The cycle structure of random permutations. Ann. Probab. 20 1567-1591.

%H Alois P. Heinz, <a href="/A186526/b186526.txt">Rows n = 0..250, flattened</a>

%F T(n,k) = (n!(1/3)^k)/k!*sum((-1/3)^j/j!, j=0..(m-k)) where m=floor(n/3).

%F E.g.f.: exp(x^3/3*(y-1))/(1-x). - _Geoffrey Critzer_, Aug 26 2012.

%e For n=4 and k=1, T(4,1)=8 since there are 8 permutations on 4 elements with 1 cycle of length 3, namely, (abc)(d), (acb)(d), (abd)(c), (adb)(c), (acd)(b), (adc)(b), (bcd)(a), and (bdc)(a).

%e Triangle T(n,k) begins:

%e :     1;

%e :     1;

%e :     2;

%e :     4,    2;

%e :    16,    8;

%e :    80,   40;

%e :   520,  160,   40;

%e :  3640, 1120,  280;

%e : 29120, 8960, 2240;

%e : ...

%p seq(seq(n!*(1/3)^x/x!*sum((-1/3)^j/j!,j=0..(floor(n/3)-x)),x=0..floor(n/3)),n=0..15);

%p # second Maple program:

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

%p       `if`(i=3, 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

%t nn = 8; Range[0, nn]! CoefficientList[

%t    Series[Exp[x^3/3 (y - 1)]/(1 - x), {x, 0, nn}], {x, y}] // Grid

%Y Cf. A000142, A057693, A008290, A114320.

%K nonn,tabf

%O 0,3

%A _Dennis P. Walsh_, Feb 23 2011