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

Offset: 0

Author

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

Keywords

• nonn

Comments

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

Examples

			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
		

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

Crossrefs

Cf. A000007, A000166, A024000, A087981.

Programs

Mathematica

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

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 */

Formula

a(n) = (n-1) * (a(n-1) + 3*a(n-2)) with a(0)=1. [corrected by Seiichi Manyama, Apr 23 2025]

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

a(n) = n! * Sum_{k=0..n} (-3)^(n-k) * binomial(k+2,2)/(n-k)!. - Seiichi Manyama, Apr 23 2025

Extensions

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