Lesson Upper level combinatorics problem on subsets of a finite set
Algebra
->
Permutations
-> Lesson Upper level combinatorics problem on subsets of a finite set
Log On
Algebra: Combinatorics and Permutations
Section
Solvers
Solvers
Lessons
Lessons
Answers archive
Answers
Source code of 'Upper level combinatorics problem on subsets of a finite set'
This Lesson (Upper level combinatorics problem on subsets of a finite set)
was created by by
ikleyn(53107)
:
View Source
,
Show
About ikleyn
:
<H2>Upper level combinatorics problem on subsets of a finite set</H2> <H3>Problem 1</H3>Let S = {1, 2, 3, 4, . . . , n}, and let A and B be two subsets of S such that A ≠ ∅, B ≠ S, and A ⊆ B. Calculate the number of ordered pairs (A,B) for all subsets of the set S. <B>Solution</B> <pre> Set S contains n distinguishable elements. Let m be an integers number 0 <= m <= n. The number of different subsets B in S, consisting of m elements, is {{{C[n]^m}}}. Notice that in this formula, I admit B = S. This case will be excluded later. So, for given integer m between 1 and n, we can choose subset B in {{{C[n]^m}}} different ways. Let B is one such selected set of m elements. The number of all different subsets A in B is {{{2^m}}}. Notice that in this formula, I admit A = ∅. This case will be excluded later. Having this, we conclude that the number of all pairs (A,B), where A is a subset in B, is {{{sum(C[n]^m*2^m, m=0,n)}}}. This sum is REMARCABLE. It is nothing else as {{{3^n}}}. Indeed, this sum is a binomial expansion/decomposition, which can be folded back {{{sum(C[n]^m*2^m, m=0,n)}}} = {{{(1+2)^n}}} = {{{3^n}}}. OK. The problem is almost fully solved. To fully complete it, we only need to exclude all pairs (A,B), where B = S or A = ∅. The number of pairs (A,S) is the same as the number of all subsets A in S: it is {{{2^n}}}, including the subset (∅,S). The number of pairs (∅,B) is the same as the number of subsets B in S: it is {{{2^n}}} again, including the subset (∅,S). So, when we exclude the prohibited pairs, we will get the number of all pairs under the problem's question is {{{3^n}}} - {{{2^n}}} - {{{2^n}}} + 1 = {{{3^n}}} - {{{2*2^n}}} + 1. I added 1 to compensate the fact that above I excluded the pair (∅,S) twice. <U>ANSWER</U>. The number of all pairs under the problem's question is {{{3^n}}} - {{{2*2^n}}} + 1. </pre> Now the problem is solved completely. My other additional lessons on Combinatorics problems in this site are - <A HREF=https://www.algebra.com/algebra/homework/Permutations/Upper-league-combinatorics-problem.lesson>Upper league combinatorics problem</A> - <A HREF=https://www.algebra.com/algebra/homework/Permutations/An-upper-level-problem-on-a-party-of-people-sitting-at-a-round-table.lesson>Upper level problems on a party of people sitting at a round table</A> - <A HREF=https://www.algebra.com/algebra/homework/Permutations/A-confusing-combinatorics-problem-on-repeating-digits.lesson>A confusing combinatorics problem on repeating digits in numbers</A> - <A HREF=https://www.algebra.com/algebra/homework/Permutations/Upper-level-combinatorics-problems-on-Inclusion-Exclusion-principle.lesson>Upper level combinatorics problems on Inclusion-Exclusion principle</A> - <A HREF=https://www.algebra.com/algebra/homework/Permutations/This-nice-problem-teaches-to-distinguish-permutations-from-combinations.lesson>This nice problem teaches to distinguish permutations from combinations</A> - <A HREF=https://www.algebra.com/algebra/homework/Permutations/OVERVIEW-of-additional-combinatorics-problems.lesson>OVERVIEW of additional combinatorics problems</A> Use this file/link <A HREF=https://www.algebra.com/algebra/homework/complex/ALGEBRA-II-YOUR-ONLINE-TEXTBOOK.lesson>ALGEBRA-II - YOUR ONLINE TEXTBOOK</A> to navigate over all topics and lessons of the online textbook ALGEBRA-II.
