Results 1 to 3 of 3

Math Help - ordered pair!!

  1. #1
    Newbie
    Joined
    Jan 2008
    Posts
    3

    ordered pair!!

    Determine the number of ordered pairs (A,B), where A is a subset of B and B is a subset of {1,2,....,n}.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1573
    Awards
    1
    Quote Originally Posted by vivian View Post
    Determine the number of ordered pairs (A,B), where A is a subset of B and B is a subset of {1,2,....,n}.
    For a particular subset B \subseteq \left\{ {1,2,3, \cdots ,n} \right\} and B has k elements then there are 2^k subsets of B. Hence there are 2^k ordered pairs (A,B) where A \subseteq B. BUT that is only for one particular subset.

    Let’s do the general case: for any number j, 1 \le j \le n, there are {n \choose j} subsets of \left\{ {1,2,3, \cdots ,n} \right\} having j elements. Thus there are {n \choose j}2^j pairs of the form (A,B) where A \subseteq B and |B|=j.

    The total count: \sum\limits_{j = 0}^n {{n \choose j} 2^j } .
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by Plato View Post
    The total count: \sum\limits_{j = 0}^n {{n \choose j} 2^j } .
    Comparing that with the binomial formula (x+y)^n = \sum\limits_{j = 0}^n {{n \choose j} x^jy^{n-j} } , you see that the total count is 3^n (put x=2, y=1).

    You can see this answer directly from the original question if you argue as follows. For each integer from 1 to n, there are three possibilities: (a) it belongs to both A and B, (b) it belongs to B but not A, (c) it belongs to neither. Total number of possible choices: 3^n (but I wouldn't have thought of that if I hadn't seen Plato's answer first).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Ordered pair
    Posted in the Algebra Forum
    Replies: 7
    Last Post: November 29th 2009, 06:52 PM
  2. Ordered Pair
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: September 9th 2009, 02:17 PM
  3. Ordered pair. need help in understanding.
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: May 6th 2009, 05:07 PM
  4. What is an ordered pair?
    Posted in the Discrete Math Forum
    Replies: 10
    Last Post: February 9th 2008, 11:15 PM
  5. ordered pair solution
    Posted in the Algebra Forum
    Replies: 2
    Last Post: September 14th 2006, 03:57 AM

Search Tags


/mathhelpforum @mathhelpforum