%I
%S 1,1,10,141,2824,71565,2244096,83982199,3681265792,186047433225,
%T 10716241342240,697053065658411,50827694884298784,4129325095108122637,
%U 371782656333674104624,36918345387693628911375,4025196918605160943576576,479796375191949916361466897
%N 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 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 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 a(n) is always divisible by n. A proof of this is currently (Oct 2010) being written up  we will add a link as soon as the preprint is available.
%C From _Joerg Arndt_, Jul 21 2014: (Start)
%C 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 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 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 Martin Fuller, <a href="/A181162/b181162.txt">Table of n, a(n) for n = 0..20</a>
%H M. Holloway, 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 Joerg Arndt, <a href="/A181162/a181162.txt">the a(3) = 141 pairs of maps [3] > [3]</a>
%H Stephen M. Buckley, <a href="http://archive.maths.nuim.ie/staff/sbuckley/Papers/semigp_cp.pdf">Minimal order semigroups with specified commuting probability</a>, 04032013. [_W. Edwin Clark_, Jul 21 2014]
%H Martin Fuller, <a href="/A181162/a181162_1.txt">a(6) from the A001372(6)=130 mapping patterns</a>
%H Math Overflow, <a href="http://mathoverflow.net/questions/143058/whatistheprobabilitytworandommapsonnsymbolscommute">What is the probability two random maps on n symbols commute?</a>, 2013. [_W. Edwin Clark_, Jul 21 2014]
%H Math Overflow, <a href="http://mathoverflow.net/questions/42084/countingandunderstangingcommutingfunctions">Counting and understanding commuting functions</a>, 2010.
%e The a(2) = 10 pairs of maps [2] > [2] are:
%e 01: [ 1 1 ] [ 1 1 ]
%e 02: [ 1 1 ] [ 1 2 ]
%e 03: [ 1 2 ] [ 1 1 ]
%e 04: [ 1 2 ] [ 1 2 ]
%e 05: [ 1 2 ] [ 2 1 ]
%e 06: [ 1 2 ] [ 2 2 ]
%e 07: [ 2 1 ] [ 1 2 ]
%e 08: [ 2 1 ] [ 2 1 ]
%e 09: [ 2 2 ] [ 1 2 ]
%e 10: [ 2 2 ] [ 2 2 ]
%e  _Joerg Arndt_, Jul 22 2014
%Y A053529 is a similar count for permutations. A254529 is for permutations commuting with functions.
%Y Cf. A000312, A001372, A239749A239785, A239836A239841.
%K hard,nonn,nice
%O 0,3
%A _Jeffrey Norden_, Oct 07 2010
%E a(11)a(20) from _Martin Fuller_, Feb 01 2015
