A254570 -id:A254570 - cp's OEIS frontend

A254569 The number of unordered 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, 7, 84, 1540, 37345, 1145376, 42402871, 1849021504, 93217426857, 5363120671120, 348669188664511, 25418305492373520, 2064813985107357445, 185896884170249831320, 18459391640792004885375, 2012607682674617326564096, 239898601216105901349115537, 31132586664410794285693925664, 4380971763246528510240944123071, 665896706682993760478978112600400

Offset: 1

Joerg Arndt, Feb 01 2015

nonn

			The a(2) = 7 pairs of maps [2] -> [2] are:
01:  [ 1 1 ]  [ 1 1 ]
02:  [ 1 1 ]  [ 1 2 ]
03:  [ 1 2 ]  [ 1 2 ]
04:  [ 1 2 ]  [ 2 1 ]
05:  [ 1 2 ]  [ 2 2 ]
06:  [ 2 1 ]  [ 2 1 ]
07:  [ 2 2 ]  [ 2 2 ]

Cf. A181162 (ordered pairs), A254570 (unordered pairs, f and g distinct).

a(n) = (A181162(n) - n^n)/2 + n^n.

A322654 Number of binary operations on an n-set that satisfy (ab)c = (ac)b for all a,b,c.

Original entry on oeis.org

1, 1, 10, 573, 136528, 115511945, 365045461056

Offset: 0

David Radcliffe, Dec 21 2018

Equivalently, these are operations for which the functions induced by right multiplication commute with one another. The operations of subtraction, division, and exponentiation satisfy this identity on appropriate domains.

J. Benaloh and M. de Mare, One-Way Accumulators: A Decentralized Alternative to Digital Signatures, in: Tor Helleseth, Advances in Cryptology — EUROCRYPT '93, Springer-Verlag Berlin Heidelberg, 1994, 274-285 (Link to PDF).

Cf. A019538, A254570.

a(n) = Sum_{k=1..n} k!*Stirling2(n,k)*c(n,k), where c(n,k) is the number of sets of k distinct functions from {1..n} to itself that are mutually commutative.

cp's OEIS Frontend

A254569 The number of unordered 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).

Views

Author

Keywords

Examples

Crossrefs

Formula