login
Number of irreflexive binary relations on the power set P(N) of an n-element set N as restricted below.
0

%I #10 Dec 12 2015 04:31:09

%S 1,1,4,198,209342

%N Number of irreflexive binary relations on the power set P(N) of an n-element set N as restricted below.

%C Each enumerated irreflexive relation R has these restricting properties:

%C Let (A,B) and (C,D) be arbitrary elements of R. Then

%C i) A and B are nonempty subsets of N,

%C ii) A and B are disjoint, and

%C iii) if (A,B) is not equal to (C,D) and A intersect C is nonempty, then B and D are disjoint.

%C Each a(n) includes the empty relation. Each relation R may contain any number of elements from 0 to n^2-n.

%C Inspired by considering less-restricted gift-exchange scenarios than in A053763.

%C Essentially, the scenarios here relax (somewhat but not entirely) noted restrictions iii) and iv) given there to allow joint giving and joint receiving.

%C More generally, these relations could be considered distribution networks (or even possible economies, in some sense) for goods and/or services whenever an entity cannot directly distribute to itself or to another entity of which it is a part and whenever an entity cannot (jointly) distribute directly to a second entity in more than one way (e.g., as part of two larger entities).

%e One of the 209342 irreflexive relations corresponding to a(4) is

%e R = {({1},{2}), ({2},{1}), ({3,4},{1,2}), ({1,4},{3}), ({2},{3,4})}.

%e Notice how the last three ordered pairs correspond to jointly giving and/or receiving gifts.

%Y Cf. A000392, A002378, A028243, A053763.

%K nonn,more

%O 0,3

%A _Rick L. Shepherd_, Feb 06 2009