

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
(list;
graph;
refs;
listen;
history;
text;
internal format)



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. 3744. 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. 6667.


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


FORMULA

see Maple code.
E.g.f.: exp(T(x)T(x)^2/2)/(1T(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!) * (n1)^(n2q)/(n2q)!).  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 > (n1)^n + add((1)^i*mul(binomial(n2*(j1), 2), j=1..i)*(n1)^(n2*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!)*(n1)^(n2*q)/(n2*q)!)); \\ Michel Marcus, Mar 09 2016


CROSSREFS

Cf. A065440, A007778.
Sequence in context: A060042 A217855 A285298 * A296980 A219706 A318477
Adjacent sequences: A134359 A134360 A134361 * A134363 A134364 A134365


KEYWORD

nonn


AUTHOR

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


STATUS

approved



