

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 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.
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
M. Holloway, M. Shattuck, Commuting pairs of functions on a finite set, 2015.
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
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


CROSSREFS

A053529 is a similar count for permutations. A254529 is for permutations commuting with functions.
Cf. A000312, A001372, A239749A239785, A239836A239841.
Sequence in context: A324448 A277310 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



