With how many ways can we choose disjoint subsets?

[evinda]

Hello again! :D

I am given the following exercise:
With how many ways can we choose disjoint subsets $A$ and $B$ of the set $[n]=\{1,2, \dots,n \}$,if we require that the sets $A$ and $B$ are non-empty.

Without the requirement,it would be like that:
For each element $i$,we have: $i \in A, i \in B \text{ or } i \notin A \cup B$.
So,the result would be $3 \cdots 3=3^n$.

At the case when we have the requirement,I thought that each element $i$ ,except from $2$,have $3$ choices ($i \in A, i \in B \text{ or } i \notin A \cup B$) .
Each of the $2$ elements that remain has only one choice,the one should belong in $A$ and the other one in $B$.Then the result would be $3^{n-2} \cdot 1 \cdot 1$.

Could you tell me if it is right?

 

[I like Serena]

Hello again! :D

I am given the following exercise:
With how many ways can we choose disjoint subsets $A$ and $B$ of the set $[n]=\{1,2, \dots,n \}$,if we require that the sets $A$ and $B$ are non-empty.

Without the requirement,it would be like that:
For each element $i$,we have: $i \in A, i \in B \text{ or } i \notin A \cup B$.
So,the result would be $3 \cdots 3=3^n$.

At the case when we have the requirement,I thought that each element $i$ ,except from $2$,have $3$ choices ($i \in A, i \in B \text{ or } i \notin A \cup B$) .
Each of the $2$ elements that remain has only one choice,the one should belong in $A$ and the other one in $B$.Then the result would be $3^{n-2} \cdot 1 \cdot 1$.

Could you tell me if it is right?

Hi!

Let's see...

Let's call $C = (A \cup B)^c$.

Suppose we divide the first n-2 element more or less equally.
Then, at the end the sets are not empty, so we still have 3 choices for each of the last 2 elements.

Now suppose we put the first n-2 elements in C, then we still have 2 choices for the next element, which will have to go in either A or B. And finally we are left with 1 choice for the last element.

In other words, I do not think it is right. (Thinking)

 

[evinda]

Hi!

Let's see...

Let's call $C = (A \cup B)^c$.

Suppose we divide the first n-2 element more or less equally.
Then, at the end the sets are not empty, so we still have 3 choices for each of the last 2 elements.

Now suppose we put the first n-2 elements in C, then we still have 2 choices for the next element, which will have to go in either A or B. And finally we are left with 1 choice for the last element.

In other words, I do not think it is right. (Thinking)

So,is it like that: $3^{n-2} \cdot 2 \cdot 1$,because of the fact that the $n-1$th element has two choices,to belong in $A$ or in $B$ and the last has one choice,to belong in the set in which the previous does not belong? (Thinking)(Blush)

 

[I like Serena]

So,is it like that: $3^{n-2} \cdot 2 \cdot 1$,because of the fact that the $n-1$th element has two choices,to belong in $A$ or in $B$ and the last has one choice,to belong in the set in which the previous does not belong? (Thinking)(Blush)

Not if we begin with dividing elements equally, so that at the end neither set is empty... (Dull)

 

[evinda]

Not if we begin with dividing elements equally, so that at the end neither set is empty... (Dull)

Oh,yes..right! But..how can I find then the number of ways we can choose disjoint subsets $A$ and $B$?? Could you give me a hint?? (Blush) (Thinking)

 

[I like Serena]

Oh,yes..right! But..how can I find then the number of ways we can choose disjoint subsets $A$ and $B$?? Could you give me a hint?? (Blush) (Thinking)

You've already found the number of ways if there were no conditions.

Suppose you counted the number of ways that are not allowed? (Wondering)
Then you can subtract that.

 

[evinda]

You've already found the number of ways if there were no conditions.

Suppose you counted the number of ways that are not allowed? (Wondering)
Then you can subtract that.

It is not allowed that each element $i$ belongs in $C = (A \cup B)^c$. But how can I find the number,that corresponds to it ? (Thinking)

 

[I like Serena]

It is not allowed that each element $i$ belongs in $C = (A \cup B)^c$. But how can I find the number,that corresponds to it ? (Thinking)

There is only 1 way where each element is in C.

But it is also possible that A is empty and B is not empty.
This is also not allowed. (Worried)

 

[evinda]

There is only 1 way where each element is in C.

But it is also possible that A is empty and B is not empty.
This is also not allowed. (Worried)

Is it maybe $3^n-2^n$ ? We subtract $2^n$,since each element $i$ has $2$ choices, $i \in B \text{ or } i \in C$,so we substract the case where $A$ is empty and if all $i$ belong in $C$, we substract also the case where $B$ is empty.. (Blush)
Is it right or am I wrong? (Thinking)

 

[I like Serena]

Is it maybe $3^n-2^n$ ? We subtract $2^n$,since each element $i$ has $2$ choices, $i \in B \text{ or } i \in C$,so we substract the case where $A$ is empty and if all $i$ belong in $C$, we substract also the case where $B$ is empty.. (Blush)
Is it right or am I wrong? (Thinking)

Let's focus on the number of cases that is disallowed.

If A is empty we would indeed have $2^n$ ways that are disallowed.

What if B is empty? (Wondering)

 

[evinda]

Let's focus on the number of cases that is disallowed.

If A is empty we would indeed have $2^n$ ways that are disallowed.

What if B is empty? (Wondering)

Then there are again $2^n$ ways that are disallowed,or am I wrong? (Thinking)

 

[I like Serena]

Then there are again $2^n$ ways that are disallowed,or am I wrong? (Thinking)

Yep.
Mmmh... how many does that make? (Wondering)

 

[evinda]

Yep.
Mmmh... how many does that make? (Wondering)

So,do we have to substract $2^{2n}$ ?

 

[I like Serena]

So,do we have to substract $2^{2n}$ ?

Well... we have $2^n$ ways that A is empty and we have $2^n$ ways that B is empty.
That is $2^n + 2^n$ ways.
I don't think that is equal to $2^{2n}$.

Furthermore, we are counting one case double.
Because 1 of those $2^n$ ways is when both A and B are empty.
So the number to subtract is $2^n + 2^n - 1$.

 

[evinda]

Well... we have $2^n$ ways that A is empty and we have $2^n$ ways that B is empty.
That is $2^n + 2^n$ ways.
I don't think that is equal to $2^{2n}$.

Furthermore, we are counting one case double.
Because 1 of those $2^n$ ways is when both A and B are empty.
So the number to subtract is $2^n + 2^n - 1$.

I understand..Thank you very much! (Party)