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

1, 1, 10, 141, 2824, 71565, 2244096, 83982199, 3681265792, 186047433225, 10716241342240, 697053065658411, 50827694884298784, 4129325095108122637, 371782656333674104624, 36918345387693628911375, 4025196918605160943576576, 479796375191949916361466897

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, 04-03-2013. - 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}] (* Jean-François Alcover, Sep 24 2022 *)

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