A358944 Number of Green's L-classes in B_n, the semigroup of binary relations on [n].

1, 2, 7, 55, 1324, 120633, 36672159

Offset: 0

Author

Geoffrey Critzer, Jan 16 2023

Keywords

• nonn
• hard
• more

Comments

Each L-class in B_n is determined by a union closed family of subsets of [n] that is generated by a basis of size at most n.

References

• K. H. Kim, Boolean Matrix Theory and Applications, Marcel Decker Inc., 1982.

Crossrefs

Cf. A102896, A355315.

Programs

Mathematica

independentQ[collection_] := If[MemberQ[collection, Table[0, {nn}]] \[Or] !
    DuplicateFreeQ[collection], False,Apply[And,Table[! MemberQ[  Map[Clip[Total[#]] &, Subsets[Drop[collection, {i}], {2, Length[collection]}]],
      collection[[i]]], {i, 1, Length[collection]}]]]; Map[Total,
 Map[Select[#, # > 0 &] &, Table[Table[Length[Select[Subsets[Tuples[{0, 1}, nn], {i}], independentQ[#] &]], {i, 0, nn}], {nn, 0, 5}]]]

Formula

a(n) = Sum_{k=0..n} A355315(n,k).