Binary Relations on the Power Set of an n-Element Set

Ross La Haye 955 Coppens Road Green Bay, WI 54303 USA

                      rlahaye@new.rr.com

Abstract

We define six binary relations on the power set of an n-element set and describe their basic structure and interrelationships. An auxiliary relation is noted that will assist in determining the cardinalities of each. We also indicate an eighth relation that may be of interest. We conclude the second section by computing several quantities related to walks in the graph of the sixth relation. In the third section we turn our attention to the basic structure and cardinalities of the auxiliary relation noted in section two and several additional relations. We also compute seven sums associated with these relations and indicate connections four relations have with Wieder’s conjoint and disjoint k-combinations.

1 Introduction

Combinatorial interest has generally focused on the enumeration of various types of relations or associated structures such as topologies and graphs. In this paper we will be interested in the generally more tractable problem of defining and enumerating several binary relations on the power set of an n-element set and computing various quantities associated with them. We will conclude by indicating connections four relations have with Wieder’s conjoint and disjoint k-combinations. The motivation here is to suggest some ways in which sets of ksubsets of some set may be studied under the rubric of asymmetric k-ary relations on the same. To the author’s knowledge, the results of this paper or related results do not appear in the existing literature, except when so noted.

2 The six initial relations

2.1 Definitions and structure

Let P (A) be the power set of an n-element set A^{1}. Then B = P (A) × P (A) is just the Cartesian product of P (A) with itself and the following binary relations on P (A) are, of course, just subsets of B:

R_{0} = {(x, y) : x, y ∈ P (A), x ⊆ y ∨ y ⊆ x},
R_{1} = {(x, y) : x, y ∈ P (A), x ⊂ y ∨ y ⊂ x},
R_{2} = {(x, y) : x, y ∈ P (A), x ≺ y ∨ y ≺ x},
R_{3} = {(x, y) : x, y ∈ P (A), x ⊆ y},
R_{4} = {(x, y) : x, y ∈ P (A), x ⊂ y}, and
R_{5} = {(x, y) : x, y ∈ P (A), x ≺ y}.

Note that x ≺ y denotes that x ⊂ y and |y| − |x| = 1 [2]. As R_{3} has been defined to be a partial order relation on P (A), this just means that R_{5} is the corresponding covering relation [2]. R_{4} is the corresponding strict order [2]. Also, observe that B is a reflexive, symmetric, and transitive relation on P (A) and so is an equivalence relation on the same.

R_{0} R_{1} R_{2} R_{3} R_{4} R_{5}
reflexive  yes no no yes no no
irreflexive  no yes yes no yes yes
symmetric  yes yes yes no no no
asymmetric  no no no no yes yes
antisymmetric no no no yes yes yes
transitive  no no no yes yes no
intransitive  no no yes no no yes

Table 1: Basic properties of R_{0} – R_{5}

Tables 1, 2, and 3 list some basic information with regard to R_{0} – R_{5}. While entries =, ⊆, and ⊇ in Table 3 are easily enough understood, we explain an entry of ∩ as follows. Given a row relation R_{r} and a column relation R_{c} in Table 3, an entry of ∩ indicates that, while R_{r} ⊈ R_{c} and R_{c} ⊈ R_{r}, we still have that R_{r} ∩ R_{c} ≠ ∅.

Examples. With A = {1, 2}, P (A) = {∅, {1} , {2} , {1, 2}}, and

R_{4} = {(∅, {1}), (∅, {2}), (∅, {1, 2}), ({1} , {1, 2}), ({2} , {1, 2})},

R_{5} = {(∅, {1}), (∅, {2}), ({1} , {1, 2}), ({2} , {1, 2})}.

1For convenience we may assume that A = {1, 2, 3, …, n}.

R_{0} R_{1} R_{2} R_{3} R_{4} R_{5}
reflexive closure R_{0} R_{3}
reflexive reduction R_{1}  R_{4}
symmetric closure  R_{0} R_{1} R_{2}
symmetric reduction R_{3} R_{4} R_{5}
transitive closure  R_{1}  R_{4}
transitive reduction  R_{2}  R_{5}

Table 2: Closures and reductions of R_{0} – R_{5}

R_{0} R_{1} R_{2} R_{3} R_{4} R_{5}
R_{0} = ⊇ ⊇ ⊇ ⊇ ⊇
R_{1} ⊆ = ⊇ ∩ ⊇ ⊇
R_{2} ⊆ ⊆ = ∩ ∩ ⊇
R_{3} ⊆ ∩ ∩ = ⊇ ⊇
R_{4} ⊆ ⊆ ∩ ⊆ = ⊇
R_{5} ⊆ ⊆ ⊆ ⊆ ⊆ =

Table 3: Inclusion and intersection relationships, R_{0} – R_{5}

Define the partial order relation

E = {(p, q) : p, q ∈ {R_{0}, R_{1}, …, R_{5}} , p ⊆ q}

so that G may be defined to be the (directed) graph of the covering relation corresponding to E. Then most of the information in Tables 1, 2, and 3 is illustrated in Figure 1. Observe that we have labelled the edges of G in the diagram to indicate the closure and reduction relationships that obtain between the vertices of this graph, i.e., R_{0}, R_{1} etc. For example, an edge labelled s and directed from vertex u to vertex v indicates that u is the symmetric reduction of v (and v the symmetric closure of u); we can also deduce from this that v is a symmetric relation. Similar observations hold for the other two edge labels. Finally, note that if a walk exists from u to v, then u ⊆ v. However, if there is neither a walk from u to v nor a walk from v to u, then, while u ⊈ v and v ⊈ u, it is still the case that u ∩ v ≠ ∅.

\xymatrix{ & R_{0} \\ R_{3} \ar[ur]^{s} &  & R_{1} \ar[ul]^{r} \\  & R_{4} \ar[ul]^{r} \ar[ur]^{s} &  & R_{2} \ar[ul]^{t} \\  &  & R_{5} \ar[ul]^{t} \ar[ur]^{s}}

Figure 1: Hasse diagram of G

2.2 The cardinalities of R_{0} – R_{5}

In determining the cardinalities of R_{0} – R_{5} it will be useful to recall [1] that

|P (A)| = 2^{n}.  (1)

To see this, consider that in enumerating a subset of A, i.e., an element of P (A), we decide on a case by case basis which elements of A to include in the subset. As there are 2 outcomes possible for each of the elements of A – include in the subset or exclude from the subset – and n elements of A, there are 2^{n} subsets of A altogether.

Now recall that the (x, y) ∈ R_{3} are such that x ⊆ y. It is not hard to see that enumerating each subset of each subset of A will enumerate the elements of R_{3}. We may do so by deciding on a case by case basis which elements of A to

1. include in both x and y,

2. exclude from both x and y, or

3. exclude from x and include in y.

As there are 3 outcomes possible for each of the n elements of A, we see that

|R_{3}| = 3^{n}.  (2)

The cardinalities of R_{0}, R_{1}, and R_{4} are determined as follows. Let R_{i}^{−1} denote the inverse relation of R_{i} [3]. Then, define

R_{11} = {(x, y) : x, y ∈ P (A), x = y} = {(x, x) : x ∈ P (A)}.

It should be clear that R_{11} ⊂ R_{3}. Moreover, it is obvious that

|R_{11}| = 2^{n}.  (3)

It then follows that

|R_{0}| = 2 · 3^{n} − 2^{n},  (4)

as, by definition, R_{0} = R_{3} ∪ R_{3}^{−1}, and R_{11} should only be counted once in this union.

Similarly, we see that

|R_{4}| = 3^{n} − 2^{n},  (5)

as, by definition, R_{4} = R_{3} \ R_{11}.

Furthermore,

|R_{1}| = 2 · (3^{n} − 2^{n}),  (6)

as, by definition, R_{1} = R_{4} ∪ R_{4}^{−1}.

Recall that for each (x, y) ∈ R_{5}, x ⊂ y and |y| − |x| = 1. This suggests the following enumeration of this relation. First, select 1 of the n elements of A to add to x (to get y). x is then constructed from the remaining elements of A, and this can be done in 2^{n−1} ways. As y is now completely determined, we have that

|R_{5}| = n · 2^{n−1}.  (7)

It is then easy to see that

|R_{2}| = n · 2^{n},  (8)

as, by definition, R_{2} = R_{5} ∪ R_{5}^{−1}.

Before concluding here we note one additional relation that may be of interest:

R_{6} = R_{4} \ R_{5}.

R_{6} is an irreflexive, asymmetric, antisymmetric, and transitive relation and so a strict order. We also note that this relation is a proper subset of R_{0}, R_{1}, R_{3}, and R_{4}. Finally, that

|R_{6}| = 3^{n} − 2^{n} − n · 2^{n−1}  (9)

is easily deduced from Eqns. (5) and (7).

Relation  Cardinality  Sequence  Sequence  Sequence
R_{0}  2 · 3^{n} − 2^{n}  \underline{A027649}(n) \underline{A090888}(n, 3)
R_{1}  2 · (3^{n} − 2^{n})  \underline{A056182}(n)
R_{2}  n · 2^{n}  \underline{A036289}(n)
R_{3}  3^{n}  \underline{A000244}(n) \underline{A090888}(n, 2) \underline{A112626}(n, 0)
R_{4}  3^{n} − 2^{n}  \underline{A001047}(n) \underline{A090888}(n, 1) \underline{A112626}(n, 1)
R_{5}  n · 2^{n−1}  \underline{A001787}(n) \underline{A090802}(n, 1)
R_{6}  3^{n} − 2^{n} − n · 2^{n−1} \underline{A066810}(n)  \underline{A112626}(n, 2)

Table 4: The cardinalities of R_{0} – R_{6}

Table 4 lists the cardinalities of R_{0} – R_{6} with references to the corresponding integer sequences in Sloane’s Encyclopedia [5].

2.3 Walks and lengths of walks in the graph of R_{5}

Let H be the (directed) graph of R_{5} and recall that P (A) is the power set of an n-element set A. Also, let C(n, k) denote the binomial coefficient, i.e., the number of ways to select k elements from an n-element set.

We begin by counting the number of k-length walks w(n, k) in H [3]. As the vertices of H are just elements of P (A), a little thought shows that a k-length walk in H begins at some x ∈ P (A) and adds k elements of A not in x to x, where the order of addition is important. We may enumerate such a walk by first selecting the k elements to add to x. There are C(n, k) ways to do this. This then leaves 2^{n−k} ways to construct x. Once constructed, we then just need to decide which of the k! ways we will add the k selected elements in. Hence

w(n, k) = k! · C(n, k) · 2^{n−k}.  (10)

The total number of walks W (n) in H is then just given by

W (n) = ∑_{0≤k≤n} w(n, k) = ∑_{0≤k≤n} k! · C(n, k) · 2^{n−k}.  (11)

\xymatrix{ & \{1, 2, 3\} \\ \{1, 2\} \ar@{-->}[ur] & \{1, 3\} \ar[u] & \{2, 3\} \ar@{-->}[ul] \\ \{1\} \ar[u] \ar[ur] & \{2\} \ar[ul] \ar[ur] & \{3\} \ar[ul] \ar[u] \\  & ∅ \ar[ul] \ar[u] \ar[ur]}

Figure 2: Hasse diagram of H with A = {1, 2, 3}

Now let l(n, k) denote the total length of all k-length walks in H. It is not hard to see that

l(n, k) = \frac{k}{k!} · w(n, k) = k · C(n, k) · 2^{n−k}  (12)

as in computing l(n, k) we are interested in determining only that in fact a k-length walk exists in H and accounting for the length of this walk, and this is easily accomplished by dividing w(n, k) by k! and then, of course, just multiplying the result by k. The total length of all walks L(n) in H is then just given by

L(n) = ∑_{0≤k≤n} l(n, k) = ∑_{0≤k≤n} k · C(n, k) · 2^{n−k}.  (13)

w(n, k) is given by \underline{A090802}(n, k) in Sloane’s Encyclopedia [5], while W (n) is given by \underline{A010842}(n). There is no sequence listed that gives l(n, k). However, L(n) is given by \underline{A027471}(n + 1).

We conclude this section by observing that the number of 1-length walks in H is just 1! · C(n, 1) · 2^{n−1} = n · 2^{n−1}. It should be clear that the enumeration of these walks is fundamentally equivalent to the enumeration of R_{5} given above (7).

3 The additional relations

3.1 Definitions and structure

As before, let P (A) be the power set of an n-element set A. Here we will be chiefly interested in five pairwise disjoint relations on P (A) whose union we define to be R_{35}. It should be clear that the cardinality of R_{35} is easily computed as the sum of the cardinalities of these five relations. Moreover, we will be able to easily define and determine the cardinalities of the 2^{5} − 7 = 25 remaining possible unions of the relations (the empty union is excluded, of course). So we define

R_{7} = {(x, y) : x, y ∈ P (A), x ⊂ y ∧ x ∩ y = ∅}, and

R_{10} = {(x, y) : x, y ∈ P (A), x ⊂ y ∧ x ∩ y ≠ ∅},

and recall that

R_{11} = {(x, y) : x, y ∈ P (A), x = y}.

Then we let R_{8} be an asymmetric binary relation on P (A) whose (x, y) are such that x ⊈ y and y ⊈ x and x ∩ y = ∅. Similarly, we define R_{9} be an asymmetric binary relation on P (A) whose (x, y) are such that x ⊈ y and y ⊈ x and x∩y ≠ ∅. It should be clear that R_{7} and R_{10} are also asymmetric relations. We also observe that R_{7} - R_{10} are irreflexive and vacuously antisymmetric, while R_{11} is reflexive, vacuously symmetric, and antisymmetric.

R_{35} is a reflexive, antisymmetric, and transitive relation, and so a partial order. Let Q be the quotient set [4] B/ ≡, i.e., an equivalence relation on B, where

(a, b) ≡ (c, d) ⇔ (a = d) ∧ (b = c)

for all (a, b), (c, d) ∈ B. Then R_{35} may also be thought of as a set of equivalence class representatives of Q. Furthermore, we note that

R_{3} = R_{7} ∪ R_{10} ∪ R_{11}, and
R_{4} = R_{7} ∪ R_{10}.

Examples. With A = {1, 2}, P (A) = {∅, {1} , {2} , {1, 2}}, and

R_{7} = {(∅, {1}), (∅, {2}), (∅, {1, 2})},
R_{8} = either {({1} , {2})} or {({2} , {1})},
R_{9} = ∅,
R_{10} = {({1} , {1, 2}), ({2} , {1, 2})},
R_{11} = {(∅, ∅), ({1} , {1}), ({2} , {2}), ({1, 2} , {1, 2})}.

3.2 The cardinalities of R_{7} – R_{11} and their possible unions

The Stirling numbers of the second kind S(n, k) count the number of ways to partition an n-element set into k non-empty subsets, or, parts. They satisfy the recurrence

S(n + 1, k + 1) = S(n, k) + (k + 1) · S(n, k + 1).  (14)

It is also the case that

S(n, 1) = S(n, n) = 1,  (15)

as there is clearly just 1 way to partition an n-element set into either 1 part or n parts. We assume S(i, j) = 0 when i < j . The main approach we will take in determining the cardinalities of R_{7} – R_{11} will be to

form two partitions of the n-element set A and then assign one part of each to x and one or two of each to y for all the (x, y) of R_{7} - R_{11}. For one of these partitions, it will be the case that |x ∪ y| = |A|; for the other, |x ∪ y| < |A|. In other words, we will enumerate the elements of R_{7} - R_{11} based upon which of these results will obtain.

We begin with R_{7}. Observe that for the (x, y) ∈ R_{7} it is the case that x = ∅ and x ≠ y. So we may enumerate R_{7} by fixing x = ∅, and then partitioning A into either 1 or 2 parts and assigning one part to y. There are clearly 1 = S(n, 1) ways to accomplish the 1-part enumeration and C(2, 1) · S(n, 2) = 2 · S(n, 2) ways to accomplish the 2-part enumeration. With k = 1 in Eqn. (14), it then follows that

|R_{7}| = S(n + 1, 2).  (16)

With regard to the (x, y) ∈ R_{8}, we partition A into either 2 or 3 parts and assign one part to x and another to y. It is easy to see that there are S(n, 2) ways to accomplish the 2-part enumeration, as we can only assign the parts in 1 way. The 3-part enumeration may be accomplished in C(3, 2)·S(n, 3) = 3·S(n, 3) ways, as we select 2 of the 3 parts and assign one to x and the other to y. With k = 2 in Eqn. (14), we then see that

|R_{8}| = S(n + 1, 3).  (17)

With regard to the (x, y) ∈ R_{9}, we partition A into either 3 or 4 parts and assign one part to x, another to y, and another to their intersection. There are C(3, 2) · S(n, 3) = 3 · S(n, 3) ways to accomplish the 3-part enumeration, as selecting 2 of the 3 parts and assigning one to x and the other to y leaves only 1 way to assign the remaining part to x ∩ y. The 4-part enumeration may be accomplished in C(4, 2) · C(2, 1) · S(n, 4) = 12 · S(n, 4) ways, as we first select 2 of the 4 parts and assign one to x and the other to y, and then select 1 of the 2 remaining parts to assign to x ∩ y. With k = 3 in Eqn. (14), we then have that

|R_{9}| = 3 · S(n + 1, 4).  (18)

With regard to the (x, y) ∈ R_{10}, we partition A into either 2 or 3 parts and assign one part to x and this part and another part to y. There are C(2, 1) · S(n, 2) = 2 · S(n, 2) ways to accomplish the 2-part enumeration, as selecting 1 of the 2 parts to assign to x leaves just 1 part to assign to y (in 1 way). The 3-part enumeration may be accomplished in C(3, 1) · C(2, 1) · S(n, 3) = 6 · S(n, 3) ways, as we first select 1 of the 3 parts to assign to x and then combine this with 1 of the 2 remaining parts and assign the result to y. With k = 2 in Eqn. (14), it then follows that

|R_{10}| = 2 · S(n + 1, 3).  (19)

With regard to the (x, y) ∈ R_{11}, we partition A into either 1 or 2 parts and assign one part to both x and y. This then leaves (∅, ∅) to be included in R_{11}. There are clearly 1 = S(n, 1) ways to accomplish the 1-part enumeration, C(2, 1) · S(n, 2) = 2 · S(n, 2) ways to accomplish the 2-part enumeration, and, of course, 1 way to construct (∅, ∅). With k = 1 in Eqn. (14), we then see that

|R_{11}| = S(n + 1, 2) + 1.  (20)

\begin{matrix}R_{12} = R_{7} ∪ R_{8} & R_{24} = R_{7} ∪ R_{9} ∪ R_{10} \\ R_{13} = R_{7} ∪ R_{9} & R_{25} = R_{7} ∪ R_{9} ∪ R_{11} \\ R_{4} = R_{7} ∪ R_{10} & R_{3} = R_{7} ∪ R_{10} ∪ R_{11} \\ R_{14} = R_{7} ∪ R_{11} & R_{26} = R_{8} ∪ R_{9} ∪ R_{10} \\ R_{15} = R_{8} ∪ R_{9} & R_{27} = R_{8} ∪ R_{9} ∪ R_{11} \\ R_{16} = R_{8} ∪ R_{10} & R_{28} = R_{8} ∪ R_{10} ∪ R_{11} \\ R_{17} = R_{8} ∪ R_{11} & R_{29} = R_{9} ∪ R_{10} ∪ R_{11} \\ R_{18} = R_{9} ∪ R_{10} & R_{30} = R_{7} ∪ R_{8} ∪ R_{9} ∪ R_{10} \\ R_{19} = R_{9} ∪ R_{11} & R_{31} = R_{7} ∪ R_{8} ∪ R_{9} ∪ R_{11} \\ R_{20} = R_{10} ∪ R_{11} & R_{32} = R_{7} ∪ R_{8} ∪ R_{10} ∪ R_{11} \\ R_{21} = R_{7} ∪ R_{8} ∪ R_{9} & R_{33} = R_{7} ∪ R_{9} ∪ R_{10} ∪ R_{11} \\ R_{22} = R_{7} ∪ R_{8} ∪ R_{10} & R_{34} = R_{8} ∪ R_{9} ∪ R_{10} ∪ R_{11} \\ R_{23} = R_{7} ∪ R_{8} ∪ R_{11} & R_{35} = R_{7} ∪ R_{8} ∪ R_{9} ∪ R_{10} ∪ R_{11} \end{matrix}

Table 5: Definitions of R_{3}, R_{4}, and R_{12} - R_{35}

Table 5 lists the definitions of relations R_{3} and R_{4}, as we understand them here, and R_{12} - R_{35}. Table 6 lists the cardinalities of R_{3}, R_{4} and R_{7} – R_{35} with references to corresponding integer sequences in Sloane’s Encyclopedia [5]. Again, as R_{7} - R_{11} are defined to be pairwise disjoint, the cardinalities of R_{3}, R_{4}, and R_{12} - R_{35} are easily deduced. For example, |R_{3}| just equals |R_{7}| + |R_{10}| + |R_{11}|.

Before concluding here we note that the cardinalities of R_{30}, R_{26}, R_{35}, and R_{34} may be easily computed using binomial and multichoose coefficients. The multichoose coefficient MC(n, k) [1] counts the number of ways to select k elements from an n-element set where any given element may be selected multiple times. For example, it is easily seen that

|R_{30}| = C(2^{n}, 2),  (21)

as we are effectively selecting 2 distinct elements of the 2^{n} of P (A) and assigning one to x and the other to y (in some specified manner) for all the (x, y) ∈ R_{30}.

By similar reasoning, we have that

|R_{26}| = C(2^{n} − 1, 2),  (22)

as ∅ is excluded from consideration in enumerating the given relation.

It is then also easily seen that

|R_{35}| = MC(2^{n}, 2)  (23)

and

|R_{34}| = MC(2^{n} − 1, 2) + 1,  (24)

as ∅ only occurs in (∅, ∅) in R_{34}.

Similar results may be deduced for the remaining relations. However, most are not as pretty as these, so we pass them over here.

Relation  Cardinality  Sequence
R_{7}  S(n + 1, 2)  \underline{A000225}(n)
R_{8}  S(n + 1, 3)  \underline{A000392}(n + 1)
R_{9}  3 · S(n + 1, 4)  \underline{A032263}(n + 1)
R_{10}  2 · S(n + 1, 3)  \underline{A028243}(n + 1)
R_{11}  S(n + 1, 2) + 1  \underline{A000079}(n)
R_{12}  S(n + 1, 3) + S(n + 1, 2)  \underline{A003462}(n)
R_{13}  3 · S(n + 1, 4) + S(n + 1, 2)  \underline{A134018}(n)
R_{4}  2 · S(n + 1, 3) + S(n + 1, 2)  \underline{A001047}(n)
R_{14}  S(n + 2, 2)  \underline{A000225}(n + 1)
R_{15}  3 · S(n + 1, 4) + S(n + 1, 3)  \underline{A016269}(n − 2)
R_{16}  3 · S(n + 1, 3)  \underline{A094033}(n + 1)
R_{17}  S(n + 1, 3) + S(n + 1, 2) + 1  \underline{A007051}(n)
R_{18}  3 · S(n + 1, 4) + 2 · S(n + 1, 3)  \underline{A036239}(n)
R_{19}  3 · S(n + 1, 4) + S(n + 1, 2) + 1  \underline{A134019}(n)
R_{20}  2 · S(n + 1, 3) + S(n + 1, 2) + 1  \underline{A083323}(n)
R_{21}  3 · S(n + 1, 4) + S(n + 1, 3) + S(n + 1, 2)  \underline{A133789}(n)
R_{22}  S(n + 2, 3)  \underline{A000392}(n + 2)
R_{23}  S(n + 1, 3) + S(n + 2, 2)  \underline{A094374}(n)
R_{24}  3 · S(n + 1, 4) + 2 · S(n + 1, 3) + S(n + 1, 2) \underline{A053154}(n)
R_{25}  3 · S(n + 1, 4) + S(n + 2, 2)  \underline{A134045}(n)
R_{3}  2 · S(n + 1, 3) + S(n + 2, 2)  \underline{A000244}(n)
R_{26}  3 · (S(n + 1, 4) + S(n + 1, 3))  \underline{A134057}(n)
R_{27}  3 · S(n + 1, 4) + S(n + 1, 3) + S(n + 1, 2) + 1 \underline{A084869}(n)
R_{28} S(n + 2, 3) + 1 \underline{A134063}(n)
R_{29}  3 · S(n + 1, 4) + 2 · S(n + 1, 3) + S(n + 1, 2) + 1 \underline{A134064}(n)
R_{30}  3 · S(n + 1, 4) + S(n + 2, 3)  \underline{A006516}(n)
R_{31}  3 · S(n + 1, 4) + S(n + 1, 3) + S(n + 2, 2)  \underline{A134165}(n)
R_{32}  S(n + 2, 3) + S(n + 1, 2) + 1  \underline{A053156}(n + 1)
R_{33}  3 · S(n + 1, 4) + 2 · S(n + 1, 3) + S(n + 2, 2) \underline{A134168}(n)
R_{34} 3 · S(n + 1, 4) + S(n + 2, 3) + 1 \underline{A134169}(n)
R_{35}  3 · S(n + 1, 4) + S(n + 2, 3) + S(n + 1, 2) + 1 \underline{A007582}(n)

Table 6: The cardinalities of R_{3}, R_{4}, and R_{7} – R_{35}

3.3 Seven sums associated with R_{35}

Recall that B is just P (A)×P (A). As |P (A)| = 2^{n} it is then obvious that |B| = 4^{n}. Another way to see this is that in enumerating the (x, y) ∈ B there are 4 possible outcomes for each of the elements of A:

1. include in both x and y,

2. exclude from both x and y,

3. exclude from x and include in y, or

4. include in x and exclude from y.

Let x △ y denote the symmetric difference of sets x and y. It is not hard to see, then, that the sums

S(n) = ∑_{(x,y)∈B} |x △ y|,
T (n) = ∑_{(x,y)∈B} |x ∩ y|,
U(n) = ∑_{(x,y)∈B} |x ∪ y|

may be computed by counting relevant possible outcomes for each of the n decisions made in the given enumeration. By correcting these sums for double-counting, the values of the sums

S_{Q}(n) = ∑_{(x,y)∈R_{35}} |x △ y|,
T_{Q}(n) = ∑_{(x,y)∈R_{35}} |x ∩ y|,
U_{Q}(n) = ∑_{(x,y)∈R_{35}} |x ∪ y|

may then be easily deduced. This correction is necessary because R_{35} effectively results from removing every (y, x) ∈ B when (x, y) ∈ B and x ≠ y. In other words, let

R_{36} = {(x, y) : x, y ∈ P (A), x ≠ y}

and recall that R_{11} = {(x, y) : x, y ∈ P (A), x = y}. This just means that

R_{36} = B \ R_{11}.

As it is easily deduced that

R_{30} = {(x, y) ∈ R_{35}, x ≠ y} = R_{35} \ R_{11},

we then have that

\frac{1}{2}|R_{36}| = |R_{30}|.  (25)

Let m be the number of relevant possible outcomes for each decision made in the enumeration of B. It is not hard to see that m = 2 for S(n) and S_{Q}(n), as only outcomes 3 and 4 can make a difference with regard to |x △ y| for each of the (x, y) ∈ B. By similar reasoning, we have m = 1 for T (n) and T_{Q}(n) and m = 3 for U(n) and U_{Q}(n). It is not hard to see from this, then, that

S(n) = n · \frac{2}{4} · 4^{n} = 2 · n · 4^{n−1},  (26)
T (n) = n · \frac{1}{4} · 4^{n} = n · 4^{n−1},  (27)
U(n) = n · \frac{3}{4} · 4^{n} = 3 · n · 4^{n−1}.  (28)

Now with

P (n) = ∑_{x∈P (A)} |x|  (29)

we may deduce that

P (n) = n · \frac{1}{2} · 2^{n} = n · 2^{n−1}  (30)

by applying the same reasoning used to establish Eqns. (26) – (28). Furthermore, it is obvious that |x △ x| = 0 and |x ∩ x| = |x ∪ x| = |x| for any given finite set x. It is then easily seen that

∑_{(x,y)∈R_{11}} |x △ y| = 0,  (31)

and that with

X(n) = ∑_{(x,y)∈R_{11}} |x ∩ y|  (32)
= ∑_{(x,y)∈R_{11}} |x ∪ y|  (33)

we have

X(n) = P (n) = n · 2^{n−1},  (34)

as, again, x = y for all (x, y) ∈ R_{11}. A little thought then shows that

S_{Q}(n) = \frac{1}{2} · (S(n) − 0) + 0,  (35)
T_{Q}(n) = \frac{1}{2} · (T (n) − X(n)) + X(n),  (36)
U_{Q}(n) = \frac{1}{2} · (U(n) − X(n)) + X(n),  (37)

which upon substitution and simplification yields

S_{Q}(n) = n · 4^{n−1},  (38)
T_{Q}(n) = \frac{1}{2} · n · (4^{n−1} + 2^{n−1}),  (39)
U_{Q}(n) = \frac{1}{2} · n · (3 · 4^{n−1} + 2^{n−1}).  (40)

Table 7 lists the values of the sums computed here with references to corresponding sequences in Sloane’s Encyclopedia [5].

Sum  Value  Sequence
S(n)  2 · n · 4^{n−1}  \underline{A002699}(n)
T (n)  n · 4^{n−1}  \underline{A002697}(n)
U(n)  3 · n · 4^{n−1}  none
P (n)  n · 2^{n−1}  \underline{A001787}(n)
S_{Q}(n)  n · 4^{n−1}  \underline{A002697}(n)
T_{Q}(n) \frac{1}{2} · n · (4^{n−1} + 2^{n−1}) \underline{A082134}(n)
U_{Q}(n) \frac{1}{2} · n · (3 · 4^{n−1} + 2^{n−1}) \underline{A133224}(n)

Table 7: Seven sums associated with R_{35}

3.4 Wieder connections

As before, let P (A) be the power set of an n-element set A. In Wieder’s analysis [6] of coalition structures, four basic sets of k-subsets of P (A) are defined:

conjoint usual k-combinations,

conjoint strict k-combinations,

disjoint usual k-combinations, and

disjoint strict k-combinations.

Let C_{u,k}, C_{s,k}, D_{u,k}, and D_{s,k} respectively denote these sets and fix k = 2. C_{u,2} is just the set of all 2-subsets {x, y} of P (A); C_{s,2} is the subset of C_{u,2} for which neither x nor y may be equal to ∅ or A. Similarly, D_{u,2} is the set of all 2-subsets {x, y} of P (A) where x ∩ y = ∅; D_{s,2} is the subset of D_{u,2} for which neither x nor y may be equal to ∅. So we have that

C_{s,2} ⊂ C_{u,2};  D_{s,2} ⊂ D_{u,2} ⊂ C_{u,2};
D_{s,2} ⊂ C_{s,2};  D_{u,2} ⊈ C_{s,2}, D_{u,2} ∩ C_{s,2} ≠ ∅.

Now recall that R_{30} = R_{35} \ R_{11} is an asymmetric binary relation on P (A). This just means that either (x, y) or (y, x) is an element of R_{30} such that x ≠ y. So we may map {x, y} = {y, x} in C_{u,2} to whichever of either (x, y) or (y, x) occurs in this relation. Moreover, it is clear that this mapping is invertible. In other words, there is a one-to-one correspondence between C_{u,2} and R_{30}. Let

R_{37} = (P (A) × A) \ {(∅, A), (A, A)}

so that

R_{38} = R_{26} \ R_{37}.

Then we have that

R_{38} ⊂ R_{30};  R_{8} ⊂ R_{12} ⊂ R_{30};
R_{8} ⊂ R_{38};  R_{12} ⊈ R_{38}, R_{12} ∩ R_{38} ≠ ∅.

It is then easily shown that the following one-to-one correspondences also obtain:

C_{s,2} ↔ R_{38},
D_{u,2} ↔ R_{12},
D_{s,2} ↔ R_{8}.

It is clear that we could extend this analysis to any remaining sets of 2-subsets of P (A) and corresponding asymmetric binary relations on the same. More generally, we might consider sets of k-subsets (or even k-multisubsets) on any given well-defined finite set and corresponding asymmetric k-ary relations. Whatever the merits might be of such investigations, we leave as an open question here.

4 Acknowledgements

The author would like to thank the anonymous referee whose thoughtful suggestions improved the quality of this paper.

References

[1] Arthur T. Benjamin and Jennifer J. Quinn, Proofs That Really Count: The Art of Combinatorial Proof, the Mathematical Association of America, 2003.

[2] B. A. Davey and H. A. Priestley, Introduction to Lattices and Order: Second Edition, Cambridge University Press, 2002.

[3] Kenneth H. Rosen, Handbook of Discrete and Combinatorial Mathematics, CRC Press, 2000.

[4] Eric Schechter, Handbook of Analysis and Its Foundations, Academic Press, 1997.

[5] N. J. A. Sloane, The On-line Encyclopedia of Integer Sequences, 2008.

[6] Thomas Wieder, The number of certain k-combinations of an n-set, Applied Mathematics E-Notes, 8 (2008), 45–52.

2000 Mathematics Subject Classification: Primary 04A05; Secondary 05A05, 05A18, 11B73. Keywords: binary relation, combinatorics, graph, directed graph, set partition.

(Concerned with sequences \underline{A000079}, \underline{A000225}, \underline{A000244}, \underline{A000392}, \underline{A001047}, \underline{A001787}, \underline{A002697}, \underline{A002699}, \underline{A003462}, \underline{A006516}, \underline{A007051}, \underline{A007582}, \underline{A010842}, \underline{A016269}, \underline{A027471}, \underline{A027649}, \underline{A028243}, \underline{A032263}, \underline{A036239}, \underline{A036289}, \underline{A038207}, \underline{A053154}, \underline{A053156}, \underline{A056182}, \underline{A066810}, \underline{A082134}, \underline{A083323}, \underline{A084869}, \underline{A090802}, \underline{A090888}, \underline{A094033}, \underline{A094374}, \underline{A112626}, \underline{A133224}, \underline{A133789}, \underline{A134018}, \underline{A134019}, \underline{A134045}, \underline{A134057}, \underline{A134063}, \underline{A134064}, \underline{A134165}, \underline{A134168}, and \underline{A134169}.)

Received January 20 2009; revised version received February 1 2009. Published in Journal of Integer Sequences, February 14 2009. Revised May 18 2010. Additional revision, April 11 2012.

Return to Journal of Integer Sequences home page.