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
    Your description of $F_2'$ isn’t clear. Do you mean that if $d\in F_2$, then $F_2'=F_2\cup\{c\}$?2012-09-19
  • 0
    @BrianM.Scott Yes indeed!2012-09-19
  • 0
    @Nga Whoops, sorry, too much caffeine today, I guess.2012-09-19
  • 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
    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^*$.2012-09-19
  • 0
    @Nga: No, it’s not a valid pair, because $F_2'=\{a,b,c,d\}$.2012-09-19
  • 0
    No? $F_2' = \{a,b,c\}$?2012-09-19
  • 0
    @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.2012-09-19
  • 0
    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.2012-09-19
  • 0
    @Nga: I didn’t look for all of the missing pairs, but for instance you’re missing all of the pairs in which $a\in F_1$ and $a\in F_2$ but $F_1\nsubseteq F_2'$, e.g., $F_1=\{a,b\}$ and $F_2=\{a\}$. After you considered the case $a\in F_1$ and $a\notin F_2'$, you considered only cases in which $a\notin F_1$.2012-09-19
  • 0
    Oh I see, thanks!2012-09-19
  • 0
    Reading it again, I am slightly confused by your last paragraph. When $|F_2| = 2$ you say there are 4 valid pairs. What do you mean by this?2012-09-21
  • 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
    Could you also tell me where I went wrong myself?2012-09-19
  • 0
    @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.2012-09-19
  • 0
    Well, It is a part of a combinatorial proof in a computer science paper, which I believe to be correct.2012-09-19
  • 0
    Now I am getting confused! You have another total than Brian M Scott, and he also has another total than the paper.2012-09-19
  • 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.