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