With how many ways can we choose disjoint subsets?

  • Context: MHB 
  • Thread starter Thread starter evinda
  • Start date Start date
  • Tags Tags
    Subsets
Click For Summary

Discussion Overview

The discussion revolves around the combinatorial problem of determining the number of ways to choose disjoint non-empty subsets \( A \) and \( B \) from the set \( [n] = \{1, 2, \ldots, n\} \). Participants explore various approaches to count the valid configurations while considering the constraints of non-emptiness for both subsets.

Discussion Character

  • Exploratory
  • Mathematical reasoning
  • Debate/contested

Main Points Raised

  • One participant suggests that without the non-empty requirement, each element has three choices, leading to a total of \( 3^n \) configurations.
  • Another participant challenges the initial reasoning, proposing that if two elements must be in \( A \) and \( B \), the count should be \( 3^{n-2} \cdot 1 \cdot 1 \), but questions whether this is correct.
  • Further discussion leads to the idea that if the first \( n-2 \) elements are placed in a separate set \( C \), the last two elements have limited choices, suggesting a count of \( 3^{n-2} \cdot 2 \cdot 1 \).
  • Participants express uncertainty about how to accurately count the disallowed configurations, such as when either \( A \) or \( B \) is empty.
  • One participant proposes subtracting \( 2^n \) for the cases where \( A \) is empty and another \( 2^n \) for when \( B \) is empty, leading to the conjecture that the total might be \( 3^n - 2^n \).
  • Another participant points out that the total number of disallowed configurations should account for double counting the case where both \( A \) and \( B \) are empty, suggesting the need to subtract \( 2^n + 2^n - 1 \) instead.

Areas of Agreement / Disagreement

Participants do not reach a consensus on the correct approach to counting the valid configurations. Multiple competing views and methods are presented, and the discussion remains unresolved.

Contextual Notes

Participants express uncertainty regarding the assumptions made in their calculations and the implications of the non-empty conditions on the total counts. The discussion reflects a range of interpretations and methods without a definitive resolution.

evinda
Gold Member
MHB
Messages
3,741
Reaction score
0
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?
 
Physics news on Phys.org
evinda said:
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! :o

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)
 
I like Serena said:
Hi! :o

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)
 
evinda said:
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)
 
I like Serena said:
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)
 
evinda said:
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.
 
I like Serena said:
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 ? :confused: (Thinking)
 
evinda said:
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 ? :confused: (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)
 
I like Serena said:
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$ ? :confused: 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)
 
  • #10
evinda said:
Is it maybe $3^n-2^n$ ? :confused: 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)
 
  • #11
I like Serena said:
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)
 
  • #12
evinda said:
Then there are again $2^n$ ways that are disallowed,or am I wrong? (Thinking)

Yep.
Mmmh... how many does that make? (Wondering)
 
  • #13
I like Serena said:
Yep.
Mmmh... how many does that make? (Wondering)

So,do we have to substract $2^{2n}$ ? :confused:
 
  • #14
evinda said:
So,do we have to substract $2^{2n}$ ? :confused:

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}$. :eek:

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$.
 
  • #15
I like Serena said:
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}$. :eek:

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)
 

Similar threads

Undergrad Understanding permutations and combinations in a coin toss experiment
  • · Replies 6 ·
Replies
6
Views
1K
Undergrad When does ## { n \choose k } ## represent set of lists?
  • · Replies 20 ·
Replies
20
Views
2K
MHB How many subsets of set A satisfy given conditions?
  • · Replies 2 ·
Replies
2
Views
2K
Undergrad Is an algorithm for a proof required to halt?
  • · Replies 3 ·
Replies
3
Views
2K
Undergrad Subset definition: universal quantifier over which set?
  • · Replies 33 ·
2
Replies
33
Views
4K
Undergrad How to interpret this definition of a subset?
  • · Replies 5 ·
Replies
5
Views
2K
Undergrad Sets, Subsets, Possible Relations
  • · Replies 1 ·
Replies
1
Views
2K
MHB Model the situation with a Laplace room
  • · Replies 18 ·
Replies
18
Views
2K
Undergrad Ways to put n balls in m boxes such that exactly k boxes are empty?
  • · Replies 29 ·
Replies
29
Views
5K
MHB Let A and B be two subsets of some universal set. Prove that....
  • · Replies 2 ·
Replies
2
Views
2K