# Count the amount of pairs such that $A\not\subseteq B$ with constraints

Suppose that $F_1$,$F_2\subseteq \{a,b,c,d\}$. I want to know how many ordered pairs $(F_1,F_2)$,there are such that $F_1 \not\subseteq F_2'$, where $F_2'= F_2 \cup \{c \mid d\in F_2\}$.

My approach:

Suppose that $a \in F_1$ and $a \not\in F_2'$. Notice that $a\in F_2'$ iff $a \in F_2$. Hence we have $2^3 * 2^3 = 64$ possibilities.

Now suppose that $a\not\in F_1$ and $b \in F_1$ and $b \not\in F_2'$. Here we have $2^2 *2^3 = 32$ possibilities.

Now suppose that $a \not\in F_1$ and $b\not\in F_1$ and $d \in F_1$ and $d\not\in F_2'$ here we have $2 * 2^3 = 16$ possibilities.

Now suppose that $a \not\in F_1$ and $b\not\in F_1$ and $d \not\in F_1$ and $c \in F_1$ and $c \not\in F_2'$. Here we have $2^0 * 2^2$ posibilities. Adding this, we get 116.

However, I know that the answer to the question is 90.

Does anyone know where I went wrong?

-
Your description of $F_2'$ isn’t clear. Do you mean that if $d\in F_2$, then $F_2'=F_2\cup\{c\}$? – Brian M. Scott Sep 19 '12 at 20:49
@BrianM.Scott Yes indeed! – Nga Sep 19 '12 at 20:52
@Nga Whoops, sorry, too much caffeine today, I guess. – Thomas Andrews Sep 19 '12 at 20:57
@ThomasAndrews, No problem! – Nga Sep 19 '12 at 20:58

There are $157$ such pairs, not $90$.

It’s probably easier to count the invalid pairs. There are $8$ sets that do not contain $d$. One of them, $\varnothing$, has only one subset; three of them have two subsets; three of them have four subsets; and one of them has eight subsets. That yields a total of $1+6+12+8=27$ invalid pairs $\langle F_1,F_2\rangle$ in which $c\notin F_2$.

There are another $8$ sets that do contain $d$. If $d\in F_2$, then $\{c,d\}\subseteq F_2'$, and $F_1\subseteq F_2'$ iff $F_1\cap\{a,b\}\subseteq F_2\cap\{a,b\}$. If $F_2\cap\{a,b\}=\varnothing$, $F_1\cap\{a,b\}$ must also be $\varnothing$, and there are $4$ possibilities for $F_1\cap\{c,d\}$. If $F_2\cap\{a,b\}$ is a singleton, there are $2$ possibilities for $F_1\cap\{a,b\}$ and $4$ for $F_1\cap\{c,d\}$. And if $\{a,b\}\subseteq F_2$, there are $4$ possibilities for $F_1\cap\{a,b\}$ and $4$ for $F_1\cap\{c,d\}$. This yields another $4+8+8+16=36$ invalid pairs for each of the cases $F_2\cap\{c,d\}=\{d\}$ and $F_2\cap\{c,d\}=\{c,d\}$, for a total of $72$ invalid pairs.

Thus, there are $27+72=99$ invalid pairs, and since there are $16^2=256$ pairs altogether, the number of valid pairs must be $256-99=157$, not $90$.

As a check, here’s a direct count.

For $F\subseteq\{a,b,c,d\}$ let $F^*=F\cap\{a,b\}$. If $d\in F_2$, the only way to make $\langle F_1,F_2\rangle$ a valid pair is to make sure that $F_1^*\nsubseteq F_2^*$; $F_1\setminus F_1^*$ is arbitrary. If $F_2^*=\varnothing$, any of the three non-empty possibilities for $F_1^*$ will do, and if $|F_2^*|=1$, there are two possibilities for $F_1^*$.

• $F_2^*=\varnothing$: There are $3$ possible choices for $F_1^*$ and $4$ for the rest of $F_1$, and there are $2$ possibilities for the rest of $F_2$, so there are $24$ pairs.
• $F_2^*=\{a\}$: There are $2$ possible choices for $F_1^*$ and $4$ for the rest of $F_1$, and there are $2$ possibilities for the rest of $F_2$, so there are $16$ pairs.
• $F_2^*=\{b\}$: This is essentially the same as the previous case and yields another $16$ pairs.

Altogether we have $56$ valid pairs in which $c\in F_2$.

Now we consider sets $F_2$ that do not contain $d$, so that $F_2'=F_2$; there are $8$ such sets. Clearly any $F_1$ that contains $d$ yields a valid pair with any of these $8$ sets, so there are $8^2=64$ valid pairs of this type. Now consider the cases in which $d\notin F_1$. There are no valid pairs when $F_2=\{a,b,c\}$. When $|F_2|=2$ there are $4$ valid pairs, and there are $3$ such sets $F_2$, so this case accounts for $12$ valid pairs. When $|F_2|=1$ there are $6$ valid pairs, and there are $3$ such sets $F_2$, so this case adds $18$ valid pairs. Finally, the case $F_2=\varnothing$ we get $7$ valid pairs, for a total of $12+18+7=37$ valid pairs. This brings the grand total to $56+64+37=157$ valid pairs.

-
Thanks for your answer. How about the following case: suppose $F_1 =\{a,b,d\}$ and $F_2 = \{a,b,c\}$. This is a valid pair, but $F_1^* \subseteq F_2^*$. – Nga Sep 19 '12 at 22:21
@Nga: No, it’s not a valid pair, because $F_2'=\{a,b,c,d\}$. – Brian M. Scott Sep 19 '12 at 22:23
No? $F_2' = \{a,b,c\}$? – Nga Sep 19 '12 at 22:31
@Nga: Oops: I reversed the rôles of $c$ and $d$. My count is correct, but everywhere that I talked about $c$ or $d$ you should interchange them. It’s fixed now. – Brian M. Scott Sep 19 '12 at 22:35
Thanks man. I continued my method and it seems that I am missing some pairs, could you point me out where? Your solution is very elegant by the way, mine is just a big mess. – Nga Sep 19 '12 at 22:43

First, let us focus first on $c$ and $d$. This part of $F_2'$ can be any of $\{\}, \{d\}, \{c,d\}$, while this part of $F_1$ can be any of the four choices. There are then $12$ possibilities for this part of $F_1,F_2'$, but the ones with $F_2'=\{c,d\}$ count double because it can from from two versions of $F_2$.We have $$\begin {array} {c c c c}F_1 & F_2' & F_1 \subset F_2' & weight \\ \emptyset & \emptyset & Y & 1 \\ \emptyset & \{d\} & Y & 1\\ \emptyset & \{c,d\} & Y & 2\\\{c\} & \emptyset & N & 1\\\{c\} & \{d\} & N & 1\\\{c\} & \{c,d\} & Y & 2\\\{d\} & \emptyset & N & 1\\\{d\} & \{d\} & Y & 1\\\{d\} & \{c,d\} & Y & 2\\\{c,d\} & \emptyset & N & 1 \\\{c,d\} & \{d\} & N & 1\\\{c,d\} & \{c,d\} & Y & 2 \end {array}$$ When $F_1 \subset F_2'$ we have to make sure the subset doesn't extend to the $ab$ portion, I get $7$ possibilities for that. When $F_1 \not \subset F_2'$ there are $16$ possibilities for the $ab$ portion. This gives a total of $3\cdot 7 + 4 \cdot 7 \cdot 2+5\cdot 16=157$

-
Could you also tell me where I went wrong myself? – Nga Sep 19 '12 at 21:25
@Nga: I don't think you did. Do you truly believe the answer is $90$? Each of the remaining $9$ lines of the table will contribute at least $7$ (and some of them more) giving a total of at least $100$. I thought this was an easier way to be sure we get all the cases and don't double count, but your approach works, too. – Ross Millikan Sep 19 '12 at 21:36
Well, It is a part of a combinatorial proof in a computer science paper, which I believe to be correct. – Nga Sep 19 '12 at 21:39
Now I am getting confused! You have another total than Brian M Scott, and he also has another total than the paper. – Nga Sep 19 '12 at 22:01
@Nga: I finished the table, corrected it, and agree with Brian Scott. I had lines with $\{c\}$ in the $F_2'$ column, which were not allowed as in my first sentence. – Ross Millikan Sep 19 '12 at 22:01

Here's some code that counts them in GAP:

T:=Tuples(Combinations([1,2,3,4]),2);
count:=0;

for A in T do
F1:=A[1];
F2:=A[2];
F2dash:=F2;
if(4 in F2) then
F2dash:=Union(F2dash,[3]);
fi;
if(Intersection(F1,F2dash)<>F1) then
Print([F1,F2]," ",[F2dash],"\n");
count:=count+1;
fi;
od;
Print(count," ordered pairs found.\n");


The output is:

[ [ 1 ], [  ] ] [ [  ] ]
[ [ 1 ], [ 2 ] ] [ [ 2 ] ]
[ [ 1 ], [ 2, 3 ] ] [ [ 2, 3 ] ]
[ [ 1 ], [ 2, 3, 4 ] ] [ [ 2, 3, 4 ] ]
[ [ 1 ], [ 2, 4 ] ] [ [ 2, 3, 4 ] ]
[ [ 1 ], [ 3 ] ] [ [ 3 ] ]
[ [ 1 ], [ 3, 4 ] ] [ [ 3, 4 ] ]
[ [ 1 ], [ 4 ] ] [ [ 3, 4 ] ]
[ [ 1, 2 ], [  ] ] [ [  ] ]
[ [ 1, 2 ], [ 1 ] ] [ [ 1 ] ]
[ [ 1, 2 ], [ 1, 3 ] ] [ [ 1, 3 ] ]
[ [ 1, 2 ], [ 1, 3, 4 ] ] [ [ 1, 3, 4 ] ]
[ [ 1, 2 ], [ 1, 4 ] ] [ [ 1, 3, 4 ] ]
[ [ 1, 2 ], [ 2 ] ] [ [ 2 ] ]
[ [ 1, 2 ], [ 2, 3 ] ] [ [ 2, 3 ] ]
[ [ 1, 2 ], [ 2, 3, 4 ] ] [ [ 2, 3, 4 ] ]
[ [ 1, 2 ], [ 2, 4 ] ] [ [ 2, 3, 4 ] ]
[ [ 1, 2 ], [ 3 ] ] [ [ 3 ] ]
[ [ 1, 2 ], [ 3, 4 ] ] [ [ 3, 4 ] ]
[ [ 1, 2 ], [ 4 ] ] [ [ 3, 4 ] ]
[ [ 1, 2, 3 ], [  ] ] [ [  ] ]
[ [ 1, 2, 3 ], [ 1 ] ] [ [ 1 ] ]
[ [ 1, 2, 3 ], [ 1, 2 ] ] [ [ 1, 2 ] ]
[ [ 1, 2, 3 ], [ 1, 3 ] ] [ [ 1, 3 ] ]
[ [ 1, 2, 3 ], [ 1, 3, 4 ] ] [ [ 1, 3, 4 ] ]
[ [ 1, 2, 3 ], [ 1, 4 ] ] [ [ 1, 3, 4 ] ]
[ [ 1, 2, 3 ], [ 2 ] ] [ [ 2 ] ]
[ [ 1, 2, 3 ], [ 2, 3 ] ] [ [ 2, 3 ] ]
[ [ 1, 2, 3 ], [ 2, 3, 4 ] ] [ [ 2, 3, 4 ] ]
[ [ 1, 2, 3 ], [ 2, 4 ] ] [ [ 2, 3, 4 ] ]
[ [ 1, 2, 3 ], [ 3 ] ] [ [ 3 ] ]
[ [ 1, 2, 3 ], [ 3, 4 ] ] [ [ 3, 4 ] ]
[ [ 1, 2, 3 ], [ 4 ] ] [ [ 3, 4 ] ]
[ [ 1, 2, 3, 4 ], [  ] ] [ [  ] ]
[ [ 1, 2, 3, 4 ], [ 1 ] ] [ [ 1 ] ]
[ [ 1, 2, 3, 4 ], [ 1, 2 ] ] [ [ 1, 2 ] ]
[ [ 1, 2, 3, 4 ], [ 1, 2, 3 ] ] [ [ 1, 2, 3 ] ]
[ [ 1, 2, 3, 4 ], [ 1, 3 ] ] [ [ 1, 3 ] ]
[ [ 1, 2, 3, 4 ], [ 1, 3, 4 ] ] [ [ 1, 3, 4 ] ]
[ [ 1, 2, 3, 4 ], [ 1, 4 ] ] [ [ 1, 3, 4 ] ]
[ [ 1, 2, 3, 4 ], [ 2 ] ] [ [ 2 ] ]
[ [ 1, 2, 3, 4 ], [ 2, 3 ] ] [ [ 2, 3 ] ]
[ [ 1, 2, 3, 4 ], [ 2, 3, 4 ] ] [ [ 2, 3, 4 ] ]
[ [ 1, 2, 3, 4 ], [ 2, 4 ] ] [ [ 2, 3, 4 ] ]
[ [ 1, 2, 3, 4 ], [ 3 ] ] [ [ 3 ] ]
[ [ 1, 2, 3, 4 ], [ 3, 4 ] ] [ [ 3, 4 ] ]
[ [ 1, 2, 3, 4 ], [ 4 ] ] [ [ 3, 4 ] ]
[ [ 1, 2, 4 ], [  ] ] [ [  ] ]
[ [ 1, 2, 4 ], [ 1 ] ] [ [ 1 ] ]
[ [ 1, 2, 4 ], [ 1, 2 ] ] [ [ 1, 2 ] ]
[ [ 1, 2, 4 ], [ 1, 2, 3 ] ] [ [ 1, 2, 3 ] ]
[ [ 1, 2, 4 ], [ 1, 3 ] ] [ [ 1, 3 ] ]
[ [ 1, 2, 4 ], [ 1, 3, 4 ] ] [ [ 1, 3, 4 ] ]
[ [ 1, 2, 4 ], [ 1, 4 ] ] [ [ 1, 3, 4 ] ]
[ [ 1, 2, 4 ], [ 2 ] ] [ [ 2 ] ]
[ [ 1, 2, 4 ], [ 2, 3 ] ] [ [ 2, 3 ] ]
[ [ 1, 2, 4 ], [ 2, 3, 4 ] ] [ [ 2, 3, 4 ] ]
[ [ 1, 2, 4 ], [ 2, 4 ] ] [ [ 2, 3, 4 ] ]
[ [ 1, 2, 4 ], [ 3 ] ] [ [ 3 ] ]
[ [ 1, 2, 4 ], [ 3, 4 ] ] [ [ 3, 4 ] ]
[ [ 1, 2, 4 ], [ 4 ] ] [ [ 3, 4 ] ]
[ [ 1, 3 ], [  ] ] [ [  ] ]
[ [ 1, 3 ], [ 1 ] ] [ [ 1 ] ]
[ [ 1, 3 ], [ 1, 2 ] ] [ [ 1, 2 ] ]
[ [ 1, 3 ], [ 2 ] ] [ [ 2 ] ]
[ [ 1, 3 ], [ 2, 3 ] ] [ [ 2, 3 ] ]
[ [ 1, 3 ], [ 2, 3, 4 ] ] [ [ 2, 3, 4 ] ]
[ [ 1, 3 ], [ 2, 4 ] ] [ [ 2, 3, 4 ] ]
[ [ 1, 3 ], [ 3 ] ] [ [ 3 ] ]
[ [ 1, 3 ], [ 3, 4 ] ] [ [ 3, 4 ] ]
[ [ 1, 3 ], [ 4 ] ] [ [ 3, 4 ] ]
[ [ 1, 3, 4 ], [  ] ] [ [  ] ]
[ [ 1, 3, 4 ], [ 1 ] ] [ [ 1 ] ]
[ [ 1, 3, 4 ], [ 1, 2 ] ] [ [ 1, 2 ] ]
[ [ 1, 3, 4 ], [ 1, 2, 3 ] ] [ [ 1, 2, 3 ] ]
[ [ 1, 3, 4 ], [ 1, 3 ] ] [ [ 1, 3 ] ]
[ [ 1, 3, 4 ], [ 2 ] ] [ [ 2 ] ]
[ [ 1, 3, 4 ], [ 2, 3 ] ] [ [ 2, 3 ] ]
[ [ 1, 3, 4 ], [ 2, 3, 4 ] ] [ [ 2, 3, 4 ] ]
[ [ 1, 3, 4 ], [ 2, 4 ] ] [ [ 2, 3, 4 ] ]
[ [ 1, 3, 4 ], [ 3 ] ] [ [ 3 ] ]
[ [ 1, 3, 4 ], [ 3, 4 ] ] [ [ 3, 4 ] ]
[ [ 1, 3, 4 ], [ 4 ] ] [ [ 3, 4 ] ]
[ [ 1, 4 ], [  ] ] [ [  ] ]
[ [ 1, 4 ], [ 1 ] ] [ [ 1 ] ]
[ [ 1, 4 ], [ 1, 2 ] ] [ [ 1, 2 ] ]
[ [ 1, 4 ], [ 1, 2, 3 ] ] [ [ 1, 2, 3 ] ]
[ [ 1, 4 ], [ 1, 3 ] ] [ [ 1, 3 ] ]
[ [ 1, 4 ], [ 2 ] ] [ [ 2 ] ]
[ [ 1, 4 ], [ 2, 3 ] ] [ [ 2, 3 ] ]
[ [ 1, 4 ], [ 2, 3, 4 ] ] [ [ 2, 3, 4 ] ]
[ [ 1, 4 ], [ 2, 4 ] ] [ [ 2, 3, 4 ] ]
[ [ 1, 4 ], [ 3 ] ] [ [ 3 ] ]
[ [ 1, 4 ], [ 3, 4 ] ] [ [ 3, 4 ] ]
[ [ 1, 4 ], [ 4 ] ] [ [ 3, 4 ] ]
[ [ 2 ], [  ] ] [ [  ] ]
[ [ 2 ], [ 1 ] ] [ [ 1 ] ]
[ [ 2 ], [ 1, 3 ] ] [ [ 1, 3 ] ]
[ [ 2 ], [ 1, 3, 4 ] ] [ [ 1, 3, 4 ] ]
[ [ 2 ], [ 1, 4 ] ] [ [ 1, 3, 4 ] ]
[ [ 2 ], [ 3 ] ] [ [ 3 ] ]
[ [ 2 ], [ 3, 4 ] ] [ [ 3, 4 ] ]
[ [ 2 ], [ 4 ] ] [ [ 3, 4 ] ]
[ [ 2, 3 ], [  ] ] [ [  ] ]
[ [ 2, 3 ], [ 1 ] ] [ [ 1 ] ]
[ [ 2, 3 ], [ 1, 2 ] ] [ [ 1, 2 ] ]
[ [ 2, 3 ], [ 1, 3 ] ] [ [ 1, 3 ] ]
[ [ 2, 3 ], [ 1, 3, 4 ] ] [ [ 1, 3, 4 ] ]
[ [ 2, 3 ], [ 1, 4 ] ] [ [ 1, 3, 4 ] ]
[ [ 2, 3 ], [ 2 ] ] [ [ 2 ] ]
[ [ 2, 3 ], [ 3 ] ] [ [ 3 ] ]
[ [ 2, 3 ], [ 3, 4 ] ] [ [ 3, 4 ] ]
[ [ 2, 3 ], [ 4 ] ] [ [ 3, 4 ] ]
[ [ 2, 3, 4 ], [  ] ] [ [  ] ]
[ [ 2, 3, 4 ], [ 1 ] ] [ [ 1 ] ]
[ [ 2, 3, 4 ], [ 1, 2 ] ] [ [ 1, 2 ] ]
[ [ 2, 3, 4 ], [ 1, 2, 3 ] ] [ [ 1, 2, 3 ] ]
[ [ 2, 3, 4 ], [ 1, 3 ] ] [ [ 1, 3 ] ]
[ [ 2, 3, 4 ], [ 1, 3, 4 ] ] [ [ 1, 3, 4 ] ]
[ [ 2, 3, 4 ], [ 1, 4 ] ] [ [ 1, 3, 4 ] ]
[ [ 2, 3, 4 ], [ 2 ] ] [ [ 2 ] ]
[ [ 2, 3, 4 ], [ 2, 3 ] ] [ [ 2, 3 ] ]
[ [ 2, 3, 4 ], [ 3 ] ] [ [ 3 ] ]
[ [ 2, 3, 4 ], [ 3, 4 ] ] [ [ 3, 4 ] ]
[ [ 2, 3, 4 ], [ 4 ] ] [ [ 3, 4 ] ]
[ [ 2, 4 ], [  ] ] [ [  ] ]
[ [ 2, 4 ], [ 1 ] ] [ [ 1 ] ]
[ [ 2, 4 ], [ 1, 2 ] ] [ [ 1, 2 ] ]
[ [ 2, 4 ], [ 1, 2, 3 ] ] [ [ 1, 2, 3 ] ]
[ [ 2, 4 ], [ 1, 3 ] ] [ [ 1, 3 ] ]
[ [ 2, 4 ], [ 1, 3, 4 ] ] [ [ 1, 3, 4 ] ]
[ [ 2, 4 ], [ 1, 4 ] ] [ [ 1, 3, 4 ] ]
[ [ 2, 4 ], [ 2 ] ] [ [ 2 ] ]
[ [ 2, 4 ], [ 2, 3 ] ] [ [ 2, 3 ] ]
[ [ 2, 4 ], [ 3 ] ] [ [ 3 ] ]
[ [ 2, 4 ], [ 3, 4 ] ] [ [ 3, 4 ] ]
[ [ 2, 4 ], [ 4 ] ] [ [ 3, 4 ] ]
[ [ 3 ], [  ] ] [ [  ] ]
[ [ 3 ], [ 1 ] ] [ [ 1 ] ]
[ [ 3 ], [ 1, 2 ] ] [ [ 1, 2 ] ]
[ [ 3 ], [ 2 ] ] [ [ 2 ] ]
[ [ 3, 4 ], [  ] ] [ [  ] ]
[ [ 3, 4 ], [ 1 ] ] [ [ 1 ] ]
[ [ 3, 4 ], [ 1, 2 ] ] [ [ 1, 2 ] ]
[ [ 3, 4 ], [ 1, 2, 3 ] ] [ [ 1, 2, 3 ] ]
[ [ 3, 4 ], [ 1, 3 ] ] [ [ 1, 3 ] ]
[ [ 3, 4 ], [ 2 ] ] [ [ 2 ] ]
[ [ 3, 4 ], [ 2, 3 ] ] [ [ 2, 3 ] ]
[ [ 3, 4 ], [ 3 ] ] [ [ 3 ] ]
[ [ 4 ], [  ] ] [ [  ] ]
[ [ 4 ], [ 1 ] ] [ [ 1 ] ]
[ [ 4 ], [ 1, 2 ] ] [ [ 1, 2 ] ]
[ [ 4 ], [ 1, 2, 3 ] ] [ [ 1, 2, 3 ] ]
[ [ 4 ], [ 1, 3 ] ] [ [ 1, 3 ] ]
[ [ 4 ], [ 2 ] ] [ [ 2 ] ]
[ [ 4 ], [ 2, 3 ] ] [ [ 2, 3 ] ]
[ [ 4 ], [ 3 ] ] [ [ 3 ] ]
157 ordered pairs found.


So, there are 157 such pairs, agreeing with previous accounts.

-