

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).


35



1, 1, 10, 141, 2824, 71565, 2244096, 83982199, 3681265792, 186047433225, 10716241342240, 697053065658411, 50827694884298784, 4129325095108122637, 371782656333674104624, 36918345387693628911375, 4025196918605160943576576, 479796375191949916361466897
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

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
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.
a(n) is divisible by n as proved by Holloway and Shattuck (2015).
From Joerg Arndt, Jul 21 2014: (Start)
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.
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)
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


LINKS

Martin Fuller, Table of n, a(n) for n = 0..20
Joerg Arndt, the a(3) = 141 pairs of maps [3] > [3]
Stephen M. Buckley, Minimal order semigroups with specified commuting probability, 04032013.  W. Edwin Clark, Jul 21 2014
Martin Fuller, a(6) from the A001372(6)=130 mapping patterns
M. Holloway and M. Shattuck, Commuting pairs of functions on a finite set, 2015.
Math Overflow, What is the probability two random maps on n symbols commute?, 2013.  W. Edwin Clark, Jul 21 2014
Math Overflow, Counting and understanding commuting functions, 2010.


EXAMPLE

The a(2) = 10 pairs of maps [2] > [2] are:
01: [ 1 1 ] [ 1 1 ]
02: [ 1 1 ] [ 1 2 ]
03: [ 1 2 ] [ 1 1 ]
04: [ 1 2 ] [ 1 2 ]
05: [ 1 2 ] [ 2 1 ]
06: [ 1 2 ] [ 2 2 ]
07: [ 2 1 ] [ 1 2 ]
08: [ 2 1 ] [ 2 1 ]
09: [ 2 2 ] [ 1 2 ]
10: [ 2 2 ] [ 2 2 ]
 Joerg Arndt, Jul 22 2014


MATHEMATICA

(* This brute force code allows to get a few terms *)
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]&]];
Table[Print[n, " ", a[n]]; a[n], {n, 0, 5}] (* JeanFrançois Alcover, Sep 24 2022 *)


CROSSREFS

A053529 is a similar count for permutations. A254529 is for permutations commuting with functions.
Cf. A000312, A001372, A239749A239785, A239836A239841.
Sequence in context: A277310 A343689 A277372 * A245988 A184710 A263055
Adjacent sequences: A181159 A181160 A181161 * A181163 A181164 A181165


KEYWORD

hard,nonn,nice


AUTHOR

Jeffrey Norden, Oct 07 2010


EXTENSIONS

a(11)a(20) from Martin Fuller, Feb 01 2015


STATUS

approved



