[math-fun] Pairs (f,g) of maps [n] --> [n] such that f g = g f
Hope it is OK to occasionally(!) raise an OEIS related question. This is about A181162 ( https://oeis.org/draft/A181162 ). I have no better idea than the author: exhaustive search. It seems almost certain that this (nice) problem has been investigated somewhere. Any pointers? Best, jj
Of course it is a special case of the question: Given a binary operation on a set X determine the probability that two elements of X chosen uniformly at random commute. This question has been studied for groups and semigroups. In particular this paper http://archive.maths.nuim.ie/staff/sbuckley/Papers/semigp_cp.pdf finds the order Ord(i,j) of the smallest semigroup whose commuting probability is i/j. There is a Mathoverflow discussion of your particular problem at http://mathoverflow.net/questions/143058/what-is-the-probability-two-random-... On Mon, Jul 21, 2014 at 1:37 PM, Joerg Arndt <arndt@jjj.de> wrote:
Hope it is OK to occasionally(!) raise an OEIS related question. This is about A181162 ( https://oeis.org/draft/A181162 ).
I have no better idea than the author: exhaustive search. It seems almost certain that this (nice) problem has been investigated somewhere. Any pointers?
Best, jj
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
We might ask the same question for triples: How often does (all n<N) f(g(h(n))) = g(h(f(n)))? and ditto for the other permutations of f,g,h. We know the number of NxN->N (binary operation) tables that are commutative is N^((N^2+N)/2). The number of associative tables (semigroups) seems to be dominated by Dull Semigroups (my term; satisfying the extra rule ABC = DEF). The probability that a table is commutative exceeds prob(associative) forr 2<N<406, but assoc > comm for larger N. Rich ------ Quoting "W. Edwin Clark" <wclark@mail.usf.edu>:
Of course it is a special case of the question:
Given a binary operation on a set X determine the probability that two elements of X chosen uniformly at random commute. This question has been studied for groups and semigroups. In particular this paper http://archive.maths.nuim.ie/staff/sbuckley/Papers/semigp_cp.pdf finds the order Ord(i,j) of the smallest semigroup whose commuting probability is i/j.
There is a Mathoverflow discussion of your particular problem at
http://mathoverflow.net/questions/143058/what-is-the-probability-two-random-...
On Mon, Jul 21, 2014 at 1:37 PM, Joerg Arndt <arndt@jjj.de> wrote:
Hope it is OK to occasionally(!) raise an OEIS related question. This is about A181162 ( https://oeis.org/draft/A181162 ).
I have no better idea than the author: exhaustive search. It seems almost certain that this (nice) problem has been investigated somewhere. Any pointers?
Best, jj
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (3)
-
Joerg Arndt -
rcs＠xmission.com -
W. Edwin Clark