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

 

Logo

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 56th year, we are closing in on 350,000 sequences, and we’ve crossed 9,700 citations (which often say “discovered thanks to the OEIS”).

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: 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

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 December 7 20:40 EST 2021. Contains 349589 sequences. (Running on oeis4.)