A137775 Number of triples of permutations on n letters such that for each j, exactly one of the permutations fixes j and the other two have the same image on j.

1, 0, 3, 6, 45, 252, 1935, 16146, 153657, 1616760, 18699579, 235498590, 3207570597, 46968796404, 735689606535, 12272343940458, 217191191400945, 4064131571557104, 80166987477918963, 1662468879466624950

Offset

0,3

Comments

This sequence arises in a calculation of the fourth moments of the volumes of random polytopes in certain very symmetric convex bodies.

References

M. Meckes, Volumens of symmetric random polytopes, Arch. Math. 82 (2004) 85--96.

Links

Alois P. Heinz, Table of n, a(n) for n = 0..200

Formula

a(n) = n(a(n-1)+3*a(n-2)) with a(0)=1; E.g.f: exp(-3x)/(1-x)^3.

a(n) is the number of derangements (permutations with no fixed points) of n elements where each cycle is colored with one of three colors. - Michael Somos, Jan 19 2011

G.f.: hypergeom([1,3],[],x/(1+3*x))/(1+3*x). - Mark van Hoeij, Nov 08 2011

a(n) ~ n! * exp(-3) * n^2/2. - Vaclav Kotesovec, Oct 08 2013

Example

a(2) = 3 because one of the permutations must be the identity and the other two are the transposition (1 2); there are three ways to pick which is the identity.
a(4) = 45 because there are 6 derangements with one 4-cycle with 3^1 ways to color each derangement and 3 derangements with two 2-cycles with 3^2 ways to color each derangement. - Michael Somos, Jan 19 2011

Mathematica

Range[0, 20]! CoefficientList[Series[Exp[ -3x]/(1 - x)^3, {x, 0, 20}], x]

Prog

(PARI) {a(n) = if( n<0, 0, n! * polcoeff( exp( -3 * x + x * O(x^n) ) / ( 1 - x )^3, n ) )} /* Michael Somos, Jan 19 2011 */

Crossrefs

Cf. A000007, A000166, A024000, A087981.

Sequence in context: A088674 A203434 A076170 * A038050 A194080 A261841

Adjacent sequences: A137772 A137773 A137774 * A137776 A137777 A137778

Keyword

nonn

Author

Mark W. Meckes (mark.meckes(AT)case.edu), May 06 2008

Extensions

Added a(0)=1 by Michael Somos, Jan 19 2011

Status

approved