cp's OEIS Frontend

A181162 Number of commuting functions: the number of ordered pairs (f,g) of functions from {1..n} to itself such that fg=gf (i.e., f(g(i))=g(f(i)) for all i).

%I A181162 #56 Sep 24 2022 09:31:04
%S A181162 1,1,10,141,2824,71565,2244096,83982199,3681265792,186047433225,
%T A181162 10716241342240,697053065658411,50827694884298784,4129325095108122637,
%U A181162 371782656333674104624,36918345387693628911375,4025196918605160943576576,479796375191949916361466897
%N A181162 Number of commuting functions: the number of ordered pairs (f,g) of functions from {1..n} to itself such that fg=gf (i.e., f(g(i))=g(f(i)) for all i).
%C A181162 Also, the total number of endomorphisms of all directed graphs on n labeled vertices with outdegree of each vertex equal 1. - _Max Alekseyev_, Jan 09 2015
%C A181162 Seems to be relatively hard to compute for large n. (a(n)-n^n)/2 is always an integer, since it gives the number of unordered pairs of distinct commuting functions.
%C A181162 a(n) is divisible by n as proved by Holloway and Shattuck (2015).
%C A181162 From _Joerg Arndt_, Jul 21 2014: (Start)
%C A181162 Multiply fg=gf from the right by f to obtain fgf=gff, and use f(gf)=f(fg)=ffg to see ffg=gff; iterate to see f^k g = g f^k for all k>=1; by symmetry g^k f = f g^k holds as well.
%C A181162 More generally, if X and Y are words of length w over the alphabet {f,g}, then X = Y (as functional composition) whenever both words contain j symbols f and k symbols g (and j+k=w).  (End)
%C A181162 Functions with the same mapping pattern have the same number of commuting functions, so there is no need to check every pair. - _Martin Fuller_, Feb 01 2015
%H A181162 Martin Fuller, <a href="/A181162/b181162.txt">Table of n, a(n) for n = 0..20</a>
%H A181162 Joerg Arndt, <a href="/A181162/a181162.txt">the a(3) = 141 pairs of maps [3] -> [3]</a>
%H A181162 Stephen M. Buckley, <a href="http://archive.maths.nuim.ie/staff/sbuckley/Papers/semigp_cp.pdf">Minimal order semigroups with specified commuting probability</a>, 04-03-2013. - _W. Edwin Clark_, Jul 21 2014
%H A181162 Martin Fuller, <a href="/A181162/a181162_1.txt">a(6) from the A001372(6)=130 mapping patterns</a>
%H A181162 M. Holloway and M. Shattuck, <a href="http://www.researchgate.net/profile/Mark_Shattuck/publication/272492907_Commuting_pairs_of_functions_on_a_finite_set/links/54e65a030cf2bff5a4f54375.pdf">Commuting pairs of functions on a finite set</a>, 2015.
%H A181162 Math Overflow, <a href="https://mathoverflow.net/q/143058">What is the probability two random maps on n symbols commute?</a>, 2013. - _W. Edwin Clark_, Jul 21 2014
%H A181162 Math Overflow, <a href="https://mathoverflow.net/q/42084">Counting and understanding commuting functions</a>, 2010.
%e A181162 The a(2) = 10 pairs of maps [2] -> [2] are:
%e A181162 01:  [ 1 1 ]  [ 1 1 ]
%e A181162 02:  [ 1 1 ]  [ 1 2 ]
%e A181162 03:  [ 1 2 ]  [ 1 1 ]
%e A181162 04:  [ 1 2 ]  [ 1 2 ]
%e A181162 05:  [ 1 2 ]  [ 2 1 ]
%e A181162 06:  [ 1 2 ]  [ 2 2 ]
%e A181162 07:  [ 2 1 ]  [ 1 2 ]
%e A181162 08:  [ 2 1 ]  [ 2 1 ]
%e A181162 09:  [ 2 2 ]  [ 1 2 ]
%e A181162 10:  [ 2 2 ]  [ 2 2 ]
%e A181162 - _Joerg Arndt_, Jul 22 2014
%t A181162 (* This brute force code allows to get a few terms *)
%t A181162 a[n_] := a[n] = If[n == 0, 1, Module[{f, g, T}, T = Tuples[Range[n], n]; Table[f = T[[j, #]]&; g = T[[k, #]] &; Table[True, {n}] == Table[f[g[i]] == g[f[i]], {i, n}], {j, n^n}, {k, n^n}] // Flatten // Count[#, True]&]];
%t A181162 Table[Print[n, " ", a[n]]; a[n], {n, 0, 5}] (* _Jean-François Alcover_, Sep 24 2022 *)
%Y A181162 A053529 is a similar count for permutations. A254529 is for permutations commuting with functions.
%Y A181162 Cf. A000312, A001372, A239749-A239785, A239836-A239841.
%K A181162 hard,nonn,nice
%O A181162 0,3
%A A181162 _Jeffrey Norden_, Oct 07 2010
%E A181162 a(11)-a(20) from _Martin Fuller_, Feb 01 2015