A354458 Number of commuting pairs of equivalence relations on [n].

1, 1, 4, 19, 117, 864, 7459, 73749, 818960, 10078023

Offset

0,3

Comments

More precisely, a(n) is the number of ordered pairs (S,T) of equivalence relations on [n] such that S*T=T*S where the operation * is composition of relations. The composition of equivalence relations is not generally an equivalence relation. S*T=T*S if and only if S*T is the smallest equivalence relation that contains both S and T.

Links

Table of n, a(n) for n=0..9.

Example

Let S = 1/24/3 and T = 13/2/4 be equivalence relations on [4]. Then S*T = T*S = 13/24 so (S,T) is an example of a commuting pair of equivalence relations (as well as (T,S) ).

Mathematica

Needs["Combinatorica`"]; f[partition_] := Normal[SparseArray[ Level[Map[Tuples[#, 2] &, partition], {2}] -> 1]]; Table[er = Map[f, SetPartitions[n]]; Length[Level[
   Table[Select[er, Clip[er[[i]].#] == Clip[#.er[[i]]] &], {i, 1, Length[er]}], {2}]], {n, 0, 8}]

Crossrefs

Cf. A001247, A000110.

Sequence in context: A247056 A163859 A197660 * A361532 A094822 A280939

Adjacent sequences: A354455 A354456 A354457 * A354459 A354460 A354461

Keyword

nonn,more

Author

Geoffrey Critzer, May 30 2022

Extensions

a(9) from Vaclav Kotesovec, May 31 2022

Status

approved