Results 1 to 4 of 4

Math Help - Subsets

  1. #1
    Member
    Joined
    Apr 2009
    Posts
    190

    Subsets

    Let \binom{n}{r} stand for the number of subsets of size r taken from a set of size n. (This is the number of ways of choosing r objects from n if the order does not matter.) Every subset of the set 1, 2, . . . , n either contains the element 1 or it doesn’t. By considering these two
    possibilities, show that:

    \binom{n-1}{r-1} + \binom{n-1}{r} = \binom{n}{r}

    By using a similar method or otherwise, prove that:

    \binom{n-2}{r-2} + 2\binom{n-2}{r-1} + \binom{n-2}{r} = \binom{n}{r}


    I'm not sure what to do. I do not understand the queston, with what they said in the 1st paragraph and how to apply it here. Can i basically use the idea of binomial coefficients and factorials, and simplify the fraction or what?

    Thanks for the help
    Last edited by Aquafina; October 30th 2009 at 11:29 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member Failure's Avatar
    Joined
    Jul 2009
    From
    Zürich
    Posts
    555
    Quote Originally Posted by Aquafina View Post
    Let \binom{n}{r} stand for the number of subsets of size r taken from a set of size n. (This is the number of ways of choosing r objects from n if the order does not matter.) Every subset of the set 1, 2, . . . , n either contains the element 1 or it doesn’t. By considering these two
    possibilities, show that:

    \binom{n-1}{r-1} + \binom{n-1}{r} = \binom{n}{r}

    By using a similar method or otherwise, prove that:

    \binom{n-2}{r-2} + 2\binom{n-2}{r-1} + \binom{n-2}{r} = \binom{n}{r}


    I'm not sure what to do. I do not understand the queston, with what they said in the 1st paragraph and how to apply it here. Can i basically use the idea of binomial coefficients and factorials, and simplify the fraction or what?

    Thanks for the help
    Take the first equation. You are asked to count the subsets of size r of a set of size n in two different ways: on the right side you count the subsets of size r. On the left side of the equation, you count the subsets of size r that contain 1 and then add to that the number of subsets of size r that do not contain 1, which also gives you the number of subsets of size r. Hence equality holds.

    This method of counting the same thing two ways to show that an equation holds is quite frequently used in combinatorics. It's called the "counting two ways" method of proof (you guessed it, I suppose).

    Now try to guess what the left side of the second equation may be counting. From the right side you get the hint that it is probably also a somewhat complicated way of counting all the subsets of size r of a set of size n.

    * I dont know why my latex symbols are not showing...*
    They are not showing because you need to wrap them in [math ] ... [/math ] tags.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Apr 2009
    Posts
    190
    Quote Originally Posted by Failure View Post
    Take the first equation. You are asked to count the subsets of size r of a set of size n in two different ways: on the right side you count the subsets of size r. On the left side of the equation, you count the subsets of size r that contain 1 and then add to that the number of subsets of size r that do not contain 1, which also gives you the number of subsets of size r. Hence equality holds.

    This method of counting the same thing two ways to show that an equation holds is quite frequently used in combinatorics. It's called the "counting two ways" method of proof (you guessed it, I suppose).

    Now try to guess what the left side of the second equation may be counting. From the right side you get the hint that it is probably also a somewhat complicated way of counting all the subsets of size r of a set of size n.
    Hi thanks.

    So when I evaluate the LHS and the RHS, do I have to treat them like binomial coefficients?

    like n!/(r!(n-r)!) ?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member Failure's Avatar
    Joined
    Jul 2009
    From
    Zürich
    Posts
    555
    Quote Originally Posted by Aquafina View Post
    Hi thanks.

    So when I evaluate the LHS and the RHS, do I have to treat them like binomial coefficients?
    Yes, but with their combinatorial interpretation. Thus \binom{n}{r} is the number of subsets of size r of a set of size n.
    Of course, it would be possible to do everything as an exercise in algebra, but that would not be an elegant way of proving that the equation holds. Furthermore, the method of "counting two ways" is best tried out first on such relatively simple cases, even though a purely algebraic argument could be made instead.

    like n!/(r!(n-r)!) ?
    No, not at all! (Except if you want to do the proof purely algebraically, i.e. not by the method of "counting two ways".) - You use the combinatorial interpretation of the binomial coefficient as the total number of r-element subsets of an n-element set. Thus, if you want to count how many subsets of size r containing the element 1 of a set of n elements (that contains 1) there are, you find that, using the combinatorial interpretation of the binomial coefficient, there are \binom{n-1}{r-1} such subsets. - Why? - Because, since 1 is to be an element of such a subset, you are only allowed to add r-1 other elements from the n-1 remaining elements (i.e. excluding 1) of the superset to that subset you are trying to "construct" (in your mind, that is). ... and so on.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Subsets of R^3
    Posted in the Advanced Algebra Forum
    Replies: 11
    Last Post: May 14th 2011, 01:26 AM
  2. Subsets
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: December 29th 2010, 10:33 AM
  3. How many subsets
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: May 17th 2010, 05:41 AM
  4. Subsets
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 1st 2009, 07:54 PM
  5. Subsets
    Posted in the Math Topics Forum
    Replies: 0
    Last Post: October 22nd 2008, 12:58 AM

Search Tags


/mathhelpforum @mathhelpforum