Determining the number of subsets of a set with a specific property

In summary, in order to find the maximum number of subsets that are not pairwise disjoint in a set with n elements, one would select all sets with n-1 elements and the set with n elements, giving a total of n+1 sets. To prove this, one can use the fact that the sum of all combinations of n elements is equal to 2^n, and to show equality for general n, one can consider how many subsets of {1,2,...,n} contain 1. To prove the inequality, one can consider whether a collection can contain a set and its complement.
  • #1
jdinatale
155
0
I found an example like the problem asks, but I'm still trying to show the first part. You want the maximum number of subsets such that you can guarantee none are pairwise disjoint.

I'm trying to apply my specific case to the whole problem. For a set with 3 elements, I chose all of the sets with 2 elements, [itex]\binom{3}{2}[/itex] and all of the sets with 3 elements, [itex]\binom{3}{3}[/itex], which is 4 sets.

In general, for an set with n elements, would I want to choose all sets of with n - 1 elements, which would be [itex]\binom{n}{n - 1} = n[/itex] of them and the set with n elements which there is [itex]\binom{3}{3} = 1[/itex] of them.

But that's only n + 1 sets, when I want 2^{n - 1} sets.

I know that [itex]\binom{n}{0} + \binom{n}{1} + \binom{n}{2} + ... + \binom{n}{n} = 2^n[/itex], which is really close to what I want to show.

http://i3.photobucket.com/albums/y89/jdinatale/Joseph-5.png [Broken]
 
Last edited by a moderator:
Physics news on Phys.org
  • #2
For an example where equality holds for general n, consider this: how many subsets of {1,2,...,n} contain 1?

To prove the inequality, consider this: if the collection contains a set A, can it also contain the complement of A?
 

1. How do you determine the number of subsets of a set with a specific property?

To determine the number of subsets of a set with a specific property, you first need to identify the property and the set itself. Then, you can use combinatorial techniques such as combinations or permutations to calculate the total number of possible subsets that satisfy the given property.

2. Can you give an example of determining the number of subsets of a set with a specific property?

For example, if we have a set of four letters {A, B, C, D} and want to find the number of subsets that contain at least two vowels, we can use the combination formula C(n,r) = n! / (r!(n-r)!) to find all possible combinations. In this case, n=4 (total number of elements in the set) and r=2 (number of vowels in a subset). So the total number of subsets with at least two vowels is C(4,2) = 4! / (2!(4-2)!) = 6.

3. What if the set has more than one property that needs to be satisfied?

In this case, you can use the same combinatorial techniques to find the number of subsets that satisfy each individual property. Then, you can use the principle of inclusion-exclusion to eliminate the subsets that satisfy both properties more than once and get the final count of subsets that satisfy all given properties.

4. Is there a formula or method that can be used to quickly determine the number of subsets with a specific property?

Yes, there are formulas and methods such as combinations, permutations, and the principle of inclusion-exclusion that can be used to quickly determine the number of subsets with a specific property. However, the complexity of the problem and the size of the set may affect the efficiency of these methods.

5. Can the number of subsets with a specific property ever be infinite?

No, the number of subsets with a specific property cannot be infinite because it is bounded by the total number of elements in the set. Even if the set is infinite, the number of subsets with a specific property will still be finite.

Similar threads

  • Calculus and Beyond Homework Help
Replies
1
Views
455
  • Calculus and Beyond Homework Help
Replies
4
Views
460
  • Calculus and Beyond Homework Help
Replies
4
Views
950
  • Calculus and Beyond Homework Help
Replies
18
Views
1K
  • Calculus and Beyond Homework Help
Replies
4
Views
988
  • Calculus and Beyond Homework Help
Replies
7
Views
1K
  • Calculus and Beyond Homework Help
Replies
20
Views
2K
  • Calculus and Beyond Homework Help
Replies
1
Views
532
  • Calculus and Beyond Homework Help
Replies
1
Views
450
  • Calculus and Beyond Homework Help
Replies
3
Views
1K
Back
Top