The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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, 04-03-2013. [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, A239749-A239785, A239836-A239841. 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified January 22 10:52 EST 2020. Contains 331144 sequences. (Running on oeis4.)