Results 1 to 5 of 5

Math Help - Set theory Puzzle

  1. #1
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21

    Set theory Puzzle

    Let S=\left\{1,2,\cdots,n\right\}. It is quite commonly known that the number of subsets one can form from S are 2^n, but how many pairs A,B of these subsets is A\subseteq B true?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member Dinkydoe's Avatar
    Joined
    Dec 2009
    Posts
    411
    Interesting,

    So we're interested in finding all pairs (A,B)\in n\times n such that A\subseteq B

    Let A\in \mathcal{P}(n) a set with k elements. Then we have \sum_{i=0}^{n-k}{n-k\choose i}= 2^{n-k} sets B\in \mathcal{P}(n) such that A\subseteq B. Namely these are all sets, disjunct with A, we can unite A with such that A\cup B \in \mathcal{P}(n).

    Thus the total amount of such pairs are: \sum_{k=0}^{n}{n\choose k}2^{n-k} = (1+2)^n = 3^n. With the Binomium of Newton.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Banned
    Joined
    Sep 2009
    Posts
    502
    Quote Originally Posted by Dinkydoe View Post
    Interesting,

    So we're interested in finding all pairs (A,B)\in n\times n such that A\subseteq B

    Let A\in \mathcal{P}(n) a set with k elements. Then we have \sum_{i=0}^{n-k}{n-k\choose i}= 2^{n-k} sets B\in \mathcal{P}(n) such that A\subseteq B. Namely these are all sets, disjunct with A, we can unite A with such that A\cup B \in \mathcal{P}(n).

    Thus the total amount of such pairs are: \sum_{k=0}^{n}{n\choose k}2^{n-k} = (1+2)^n = 3^n. With the Binomium of Newton.
    How much math must I learn to understand this? Am I hopeless?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member Dinkydoe's Avatar
    Joined
    Dec 2009
    Posts
    411
    How much math must I learn to understand this? Am I hopeless?
    Not much really, it's pretty elementary. You've seen the induction proof of |\mathcal{P}(n)| = 2^n.

    However this can fairly easily shown by applying the binomium of Newton too!
    Observe that |\mathcal{P}(n)| = {n\choose 0}+{n\choose 1}+\cdots + {n\choose n}.

    Namely: it's how many different ways we can choose 0 elements, + how many different ways we can choose 1 element...etc.

    However note that 2^n = (1+1)^n. Applying the binomium of newton: (x+y)^n = \sum_{k=1}^{n}{n \choose k}x^ky^{n-k} with x= y = 1.

    And this gives: |\mathcal{P}(n)| = {n\choose 0}+{n\choose 1}+\cdots + {n\choose n} = (1+1)^n = 2^n.

    That idea is used here again here.
    Taking an element A\in \mathcal{P}(n) with k elements. How many sets B\in \mathcal{P}(n) exist such that A\subseteq B? Well, we have k elements in A. So we have n-k elements left to choose from. Observe that the amount of such B's equals the amount of subsets we can create from n-k elements!

    Hence there exists 2^{n-k} of such B's in \mathcal{P}(n).

    Since we have {n \choose k} elements in \mathcal{P}(n) of length k, it follows we have {n\choose k}2^{n-k} pairs (A,B)\in \mathcal{P}(n)\times \mathcal{P}(n), where A is a set of length k and A\subseteq B.

    Now we only need to sum over all different lengths k a set A can have. Thus we obtain:

    Total amount of pairs (A,B) = \sum_{k=0}^{n}{n\choose k}2^{n-k}.


    And if we analyse this number close we can recognise the binomium of Newton again with x= 1, y = 2.

    Hence we obtain: Total amount of pairs (A,B) = 3^n
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Banned
    Joined
    Sep 2009
    Posts
    502
    Quote Originally Posted by Dinkydoe View Post
    Not much really, it's pretty elementary. You've seen the induction proof of |\mathcal{P}(n)| = 2^n.

    However this can fairly easily shown by applying the binomium of Newton too!
    Observe that |\mathcal{P}(n)| = {n\choose 0}+{n\choose 1}+\cdots + {n\choose n}.

    Namely: it's how many different ways we can choose 0 elements, + how many different ways we can choose 1 element...etc.

    However note that 2^n = (1+1)^n. Applying the binomium of newton: (x+y)^n = \sum_{k=1}^{n}{n \choose k}x^ky^{n-k} with x= y = 1.

    And this gives: |\mathcal{P}(n)| = {n\choose 0}+{n\choose 1}+\cdots + {n\choose n} = (1+1)^n = 2^n.

    That idea is used here again here.
    Taking an element A\in \mathcal{P}(n) with k elements. How many sets B\in \mathcal{P}(n) exist such that A\subseteq B? Well, we have k elements in A. So we have n-k elements left to choose from. Observe that the amount of such B's equals the amount of subsets we can create from n-k elements!

    Hence there exists 2^{n-k} of such B's in \mathcal{P}(n).

    Since we have {n \choose k} elements in \mathcal{P}(n) of length k, it follows we have {n\choose k}2^{n-k} pairs (A,B)\in \mathcal{P}(n)\times \mathcal{P}(n), where A is a set of length k and A\subseteq B.

    Now we only need to sum over all different lengths k a set A can have. Thus we obtain:

    Total amount of pairs (A,B) = \sum_{k=0}^{n}{n\choose k}2^{n-k}.


    And if we analyse this number close we can recognise the binomium of Newton again with x= 1, y = 2.

    Hence we obtain: Total amount of pairs (A,B) = 3^n
    Oh, thank you. You are a very good teacher.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Graph Theory Puzzle
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 19th 2010, 02:31 PM
  2. A number theory puzzle
    Posted in the Math Puzzles Forum
    Replies: 9
    Last Post: September 16th 2010, 09:46 AM
  3. Replies: 0
    Last Post: May 20th 2010, 08:58 AM
  4. puzzle, set theory or statistics or probability
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: December 21st 2009, 05:24 AM
  5. Game Theory - Heuristic for single-player puzzle
    Posted in the Math Challenge Problems Forum
    Replies: 0
    Last Post: March 16th 2008, 02:25 PM

Search Tags


/mathhelpforum @mathhelpforum