Results 1 to 6 of 6

Math Help - Cardinality

  1. #1
    Member
    Joined
    Dec 2010
    Posts
    107

    Cardinality

    I'm stuck on this question:
    Let A={1,2,3....,n}. What is the cardinality of the set:
    {(a,S) : a \inS, S \inP(A)}.

    I feel like its going to be related to 2^n, but i'm not sure. Could someone point me in the right direction?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,648
    Thanks
    1596
    Awards
    1
    Let D = \left\{ {(a,S):a \in S \in \mathcal{P}(A)} \right\}, then we are counting the number of ordered pairs in D.
    There are 2^{n-1} subsets of A that contain the number 1.
    So there are 2^{n-1} pairs in D having 1 as the first term.
    Therefore, how many pairs are there in D~?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Dec 2010
    Posts
    107
    Why 2^{n-1}? Surely it would be 2^n?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Dec 2010
    Posts
    107
    No wait I see it now. So the answer should be n{2^{n-1}}?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,648
    Thanks
    1596
    Awards
    1
    You have it.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Dec 2010
    Posts
    107
    Awesome, thanks for the help!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Cardinality
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: May 11th 2010, 07:08 AM
  2. Cardinality of R, [0,1], R^2, [0,1] x [0,1]
    Posted in the Differential Geometry Forum
    Replies: 11
    Last Post: March 18th 2010, 02:20 PM
  3. Cardinality
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 31st 2009, 03:56 PM
  4. Cardinality
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: February 11th 2009, 05:36 PM
  5. Cardinality
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: February 8th 2009, 02:23 PM

Search Tags


/mathhelpforum @mathhelpforum