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

1, 1, 2, 2, 56, 544, 5064, 69348, 1210320

Offset

0,3

Comments

A mapping f has a unique square root if there exists a unique g such that gg = f.

Links

Table of n, a(n) for n=0..8.

Example

For n = 3, the two 3-cycles are unique square roots of each other.
Note that the identity map has more than one square root (i.e., 1->2, 2->1, 3->3 and itself).
Another non-example: 1->1, 2->2, 3->1 has two square roots: itself and 1->2, 2->1, 3->2.
In fact, the only endofunctions on {1,2,3} with unique square roots are the two 3-cycles, so a(3) = 2.

Prog

(Lua)
  function increment(size, t)
  t[1] = t[1] + 1
  local index = 1
  while t[index] > size do
    t[index] = 1
    index = index + 1
    if index > size then return true end
    t[index] = t[index] + 1
  end
  return false
end
function get_initial(size)
  local return_value = {}
  for i = 1, size do return_value[i] = 1 end
  return return_value
end
function compute(size)
  candidate = get_initial(size)
  return_value = 0
  repeat
    fun_root = get_initial(size)
    fun_root_count = 0
    repeat
      for i = 1, size do
        if candidate[i] ~= fun_root[fun_root[i]] then
          goto next_fun_root
        end
      end
      fun_root_count = fun_root_count + 1
	  if (fun_root_count == 2) then break end
      ::next_fun_root::
    until (increment(size, fun_root))
	
    if (fun_root_count == 1) then
	  return_value = return_value + 1
	end
  until (increment(size, candidate))
  return return_value
end

Crossrefs

A088994 (permutations only) < This sequence < A102687 (any square maps) < A000312 (all maps).

Sequence in context: A323872 A037292 A239151 * A286377 A187024 A274477

Adjacent sequences: A368864 A368865 A368866 * A368868 A368869 A368870

Keyword

nonn,hard,more

Author

Keith J. Bauer, Jan 08 2024

Extensions

a(7)-a(8) from Andrew Howroyd, Jan 09 2024

Status

approved