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

 

Logo


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

%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>, 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 Math Overflow, <a href="http://mathoverflow.net/questions/143058/what-is-the-probability-two-random-maps-on-n-symbols-commute">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/counting-and-understanging-commuting-functions">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, 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

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.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 19 22:36 EST 2020. Contains 332061 sequences. (Running on oeis4.)