

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.


5



1, 0, 3, 6, 45, 252, 1935, 16146, 153657, 1616760, 18699579, 235498590, 3207570597, 46968796404, 735689606535, 12272343940458, 217191191400945, 4064131571557104, 80166987477918963, 1662468879466624950
(list;
graph;
refs;
listen;
history;
text;
internal format)



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) 8596.


LINKS

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


FORMULA

a(n) = n(a(n1)+3*a(n2)) with a(0)=1; E.g.f: exp(3x)/(1x)^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 4cycle with 3^1 ways to color each derangement and 3 derangements with two 2cycles 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



