OFFSET
0,3
COMMENTS
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!.
REFERENCES
Arratia, R. and Tavaré, S. (1992). The cycle structure of random permutations. Ann. Probab. 20 1567-1591.
LINKS
Alois P. Heinz, Rows n = 0..250, flattened
FORMULA
T(n,k) = (n!(1/3)^k)/k!*sum((-1/3)^j/j!, j=0..(m-k)) where m=floor(n/3).
E.g.f.: exp(x^3/3*(y-1))/(1-x). - Geoffrey Critzer, Aug 26 2012.
EXAMPLE
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).
Triangle T(n,k) begins:
: 1;
: 1;
: 2;
: 4, 2;
: 16, 8;
: 80, 40;
: 520, 160, 40;
: 3640, 1120, 280;
: 29120, 8960, 2240;
: ...
MAPLE
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);
# second Maple program:
b:= proc(n) option remember; expand(`if`(n=0, 1, add(b(n-i)*
`if`(i=3, 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
MATHEMATICA
nn = 8; Range[0, nn]! CoefficientList[
Series[Exp[x^3/3 (y - 1)]/(1 - x), {x, 0, nn}], {x, y}] // Grid
CROSSREFS
KEYWORD
nonn,tabf
AUTHOR
Dennis P. Walsh, Feb 23 2011
STATUS
approved