login
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).
4
1, 0, 0, 2, 30, 444, 7360, 138690, 2954364, 70469000, 1864204416, 54224221050, 1721080885480, 59217131089908, 2195990208122880, 87329597612123594, 3707783109757616400, 167411012044894728720, 8010372386879991018496, 404912918159552083622130
OFFSET
0,4
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.
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
P. Flajolet and R. Sedgewick, Analytic Combinatorics, Cambridge University Press, 2009, page 130.
FORMULA
See Maple code.
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
EXAMPLE
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.
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 *)
PROG
(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
CROSSREFS
Sequence in context: A060042 A217855 A285298 * A296980 A219706 A318477
KEYWORD
nonn
AUTHOR
Adam Day (adam.r.day(AT)gmail.com), Jan 17 2008
STATUS
approved