cp's OEIS Frontend

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

%I A134362 #45 May 21 2025 19:07:00
%S A134362 1,0,0,2,30,444,7360,138690,2954364,70469000,1864204416,54224221050,
%T A134362 1721080885480,59217131089908,2195990208122880,87329597612123594,
%U A134362 3707783109757616400,167411012044894728720,8010372386879991018496,404912918159552083622130
%N 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).
%C A134362 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.
%D A134362 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.
%D A134362 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.
%H A134362 Alois P. Heinz, <a href="/A134362/b134362.txt">Table of n, a(n) for n = 0..150</a>
%H A134362 P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/AnaCombi/anacombi.html">Analytic Combinatorics</a>, Cambridge University Press, 2009, page 130.
%H A134362 Marko Riedel, <a href="http://math.stackexchange.com/questions/1688801/">Proof of EGF and closed form</a>
%F A134362 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
%F A134362 a(n) ~ exp(-3/2) * n^n. - _Vaclav Kotesovec_, Aug 16 2013
%F A134362 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
%e A134362 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.
%p A134362 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);
%t A134362 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 *)
%o A134362 (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
%Y A134362 Cf. A065440, A007778.
%K A134362 nonn
%O A134362 0,4
%A A134362 Adam Day (adam.r.day(AT)gmail.com), Jan 17 2008