Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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

3 Answers 3

up vote 2 down vote accepted

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.

share|improve this answer
    
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$

share|improve this answer
    
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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.