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,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

Cf. A000142, A057693, A008290, A114320.

Sequence in context: A370135 A290645 A152878 * A350816 A326723 A227924

Adjacent sequences: A186523 A186524 A186525 * A186527 A186528 A186529

Keyword

nonn,tabf

Author

Dennis P. Walsh, Feb 23 2011

Status

approved