A354847 Number of binary relations on [n] that are idempotent and reduced.

1, 2, 6, 32, 318, 5552, 159126, 7137272, 484656318, 48628712192, 7076367228486, 1471524821492552, 432066672598422318, 177354805872559516112, 100928502119652298356726, 79062670900333522721886872, 84733519638342583432646258718, 123582326772837258238596562116512, 244150974458417420635453430918487846

Offset: 0

Author

Geoffrey Critzer, Jun 08 2022

Keywords

• nonn

Comments

The Boolean matrix representing a binary relation on [n] is row (column) reduced if no nonzero row (column) is the sum of other rows (columns). It is reduced if it is both row reduced and column reduced.

a(n) is the number of partial order relations on Y, where Y is some subset of [n].

Links

• R. J. Plemmons and M. T. West, On the semigroup of binary relations, Pacific Journal of Mathematics, vol 35, No. 3, 1970. Theorem 2.4

Crossrefs

Cf. A001035, A121337.

Programs

Mathematica

nn = 18; A001035 = Cases[Import["https://oeis.org/A001035/b001035.txt",
    "Table"], {, }][[All, 2]];A[x_] = Sum[A001035[[n + 1]] x^n/n!, {n, 0, nn}];
Range[0, nn]! CoefficientList[Series[A[x] Exp[x], {x, 0, nn}], x]

Formula

E.g.f.: A(x)*exp(x) where A(x) is the e.g.f. for A001035.

a(n) = Sum_{k=0..n} binomial(n,k)*A001035(n-k).