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

1, 1, 2, 4, 2, 16, 8, 80, 40, 520, 160, 40, 3640, 1120, 280, 29120, 8960, 2240, 259840, 87360, 13440, 2240, 2598400, 873600, 134400, 22400, 28582400, 9609600, 1478400, 246400, 343235200, 114329600, 19219200, 1971200, 246400, 4462057600, 1486284800, 249849600, 25625600, 3203200, 62468806400, 20807987200, 3497894400, 358758400, 44844800, 936987251200, 312344032000, 52019968000, 5829824000, 448448000, 44844800

Offset: 0

Author

Dennis P. Walsh, Feb 23 2011

Keywords

• nonn
• tabf

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

Examples

			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;
: ...
		

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

Crossrefs

Cf. A000142, A057693, A008290, A114320.

Programs

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

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.