cp's OEIS Frontend

A368867 Number of labeled mappings from n points to themselves with unique square root (endofunctions).

%I A368867 #13 Dec 27 2024 01:35:16
%S A368867 1,1,2,2,56,544,5064,69348,1210320
%N A368867 Number of labeled mappings from n points to themselves with unique square root (endofunctions).
%C A368867 A mapping f has a unique square root if there exists a unique g such that gg = f.
%e A368867 For n = 3, the two 3-cycles are unique square roots of each other.
%e A368867 Note that the identity map has more than one square root (i.e., 1->2, 2->1, 3->3 and itself).
%e A368867 Another non-example: 1->1, 2->2, 3->1 has two square roots: itself and 1->2, 2->1, 3->2.
%e A368867 In fact, the only endofunctions on {1,2,3} with unique square roots are the two 3-cycles, so a(3) = 2.
%o A368867 (Lua)
%o A368867 function increment(size, t)
%o A368867   t[1] = t[1] + 1
%o A368867   local index = 1
%o A368867   while t[index] > size do
%o A368867     t[index] = 1
%o A368867     index = index + 1
%o A368867     if index > size then return true end
%o A368867     t[index] = t[index] + 1
%o A368867   end
%o A368867   return false
%o A368867 end
%o A368867 function get_initial(size)
%o A368867   local return_value = {}
%o A368867   for i = 1, size do return_value[i] = 1 end
%o A368867   return return_value
%o A368867 end
%o A368867 function compute(size)
%o A368867   candidate = get_initial(size)
%o A368867   return_value = 0
%o A368867   repeat
%o A368867     fun_root = get_initial(size)
%o A368867     fun_root_count = 0
%o A368867     repeat
%o A368867       for i = 1, size do
%o A368867         if candidate[i] ~= fun_root[fun_root[i]] then
%o A368867           goto next_fun_root
%o A368867         end
%o A368867       end
%o A368867       fun_root_count = fun_root_count + 1
%o A368867       if (fun_root_count == 2) then break end
%o A368867       ::next_fun_root::
%o A368867     until (increment(size, fun_root))
%o A368867     if (fun_root_count == 1) then
%o A368867       return_value = return_value + 1
%o A368867     end
%o A368867   until (increment(size, candidate))
%o A368867   return return_value
%o A368867 end
%Y A368867 A088994 (permutations only) < This sequence < A102687 (any square maps) < A000312 (all maps).
%K A368867 nonn,hard,more
%O A368867 0,3
%A A368867 _Keith J. Bauer_, Jan 08 2024
%E A368867 a(7)-a(8) from _Andrew Howroyd_, Jan 09 2024