|
%I #56 Sep 24 2022 09:31:04
%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 divisible by n as proved by Holloway and Shattuck (2015).
%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 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>, 04-03-2013. - _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 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 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 Math Overflow, <a href="https://mathoverflow.net/q/42084">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
%t (* This brute force code allows to get a few terms *)
%t 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 Table[Print[n, " ", a[n]]; a[n], {n, 0, 5}] (* _Jean-François Alcover_, Sep 24 2022 *)
%Y A053529 is a similar count for permutations. A254529 is for permutations commuting with functions.
%Y Cf. A000312, A001372, A239749-A239785, A239836-A239841.
%K hard,nonn,nice
%O 0,3
%A _Jeffrey Norden_, Oct 07 2010
%E a(11)-a(20) from _Martin Fuller_, Feb 01 2015
| 