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,2

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

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

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

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).

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]

Crossrefs

Cf. A001035, A121337.

Sequence in context: A277475 A277484 A005736 * A123903 A172401 A272661

Adjacent sequences: A354844 A354845 A354846 * A354848 A354849 A354850

Keyword

nonn

Author

Geoffrey Critzer, Jun 08 2022

Status

approved