0
$\begingroup$

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?

  • 0
    @ThomasAndrews, No problem!2012-09-19

3 Answers 3

2

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.

  • 0
    @Nga: (Sorry to have taken so long to get back to this.) Suppose that $F_2=\{a,b\}$; then $F_1$ can be any of $\{c\},\{a,c\},\{b,c\}$, or $\{a,b,c\}$. (Remember that in this subcase we’re assuming that $d\notin F_1$).2012-09-24
1

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$

  • 0
    @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.2012-09-19
0

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.