A134362 a(n) is the number of functions f:X->X, where |X| = n, such that for every x in X, f(f(x)) != x (i.e., the square of the function has no fixed points; note this implies that the function has no fixed points).

1, 0, 0, 2, 30, 444, 7360, 138690, 2954364, 70469000, 1864204416, 54224221050, 1721080885480, 59217131089908, 2195990208122880, 87329597612123594, 3707783109757616400, 167411012044894728720, 8010372386879991018496, 404912918159552083622130

Offset: 0

Author

Adam Day (adam.r.day(AT)gmail.com), Jan 17 2008

Keywords

• nonn

Comments

This sequence arose when analyzing the Zen Stare game. This game is played with a group of people standing in a circle. They start heads bowed and then everyone raises their heads simultaneously and looks at someone else in the circle. If no two people are looking at each other a Zen Stare is achieved.

Examples

			a(3) = 2 because given a three-element set X:= {A, B, C} the only functions whose square has no fixed points are f:X->X where f(A)=B, f(B)=C, f(C)=A and g:X->X where g(A)=C, g(B)=A, g(C)=B.
		

References

• Mohammad K. Azarian, On the Fixed Points of a Function and the Fixed Points of its Composite Functions, International Journal of Pure and Applied Mathematics, Vol. 46, No. 1, 2008, pp. 37-44. Mathematical Reviews, MR2433713 (2009c:65129), March 2009. Zentralblatt MATH, Zbl 1160.65015.
• Mohammad K. Azarian, Fixed Points of a Quadratic Polynomial, Problem 841, College Mathematics Journal, Vol. 38, No. 1, January 2007, p. 60. Solution published in Vol. 39, No. 1, January 2008, pp. 66-67.

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..150
• P. Flajolet and R. Sedgewick, Analytic Combinatorics, Cambridge University Press, 2009, page 130.
• Marko Riedel, Proof of EGF and closed form

Crossrefs

Cf. A065440, A007778.

Programs

Maple

a:= n -> (n-1)^n + add((-1)^i*mul(binomial(n-2*(j-1),2),j=1..i)*(n-1)^(n-2*i)/i!,i=1..floor(n/2)): seq(a(n), n=0..20);

Mathematica

nn = 20; t = Sum[n^(n - 1) x^n/n!, {n, 1, nn}]; Drop[Range[0, nn]! CoefficientList[Series[Exp[-t - t^2/2]/(1 - t), {x, 0, nn}], x], 1] (* Geoffrey Critzer, Feb 06 2012 *)

PARI

a(n) = n!*sum(q=0, n\2, ((-1)^q/(2^q*q!)*(n-1)^(n-2*q)/(n-2*q)!)); \\ Michel Marcus, Mar 09 2016

Formula

E.g.f.: exp(-T(x)-T(x)^2/2)/(1-T(x)) where T(x) is the e.g.f. for A000169. - Geoffrey Critzer, Feb 06 2012

a(n) ~ exp(-3/2) * n^n. - Vaclav Kotesovec, Aug 16 2013

a(n) = n!*Sum_{q=0..floor(n/2)} ((-1)^q/(2^q q!) * (n-1)^(n-2q)/(n-2q)!). - Marko Riedel, Mar 08 2016