1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Combinatorics -- Counting Sets of Binary Strings

  1. Apr 19, 2016 #1
    1. The problem statement, all variables and given/known data
    Give combinatorial proofs of the identities below. Use the following structure for each proof. First, define an appropriate set S. Next, show that the left side of the equation counts the number of elements in S. Then show that, from another perspective, the right side of the equation also counts the number of elements in set S. Conclude that the left side must be equal to the right, since both are equal to |S|.

    ##\binom{2n}{n} \sum_{k=0}^n \binom{n}{k} * \binom{n}{n-k}##
    ##\sum_{i=0}^r \binom{n+i}{i} = \binom{n+r+1}{r}##

    Hint: consider a set of binary strings that could be counted using the right side of the equation, then try partitioning them into subsets countable by the elements of the sum on the left.

    2. Relevant equations

    3. The attempt at a solution
    a)The left hand side is just choosing n out of 2n.
    The right hand side is choosing a total of n out of 2n as well, but with the constraint that some k must be from one half, some n-k must be from the other. Thus you would need to sum across all of k up to n in order to all possible selections.

    b) I'm having trouble understanding their hint. I've never seen counting attempted on a set of binary strings before, only on a singular binary string. I don't know what to do with the right hand side.

    The left hand side I think I understand a little more: Each individual term ##\binom{n+i}{i}## is the way I've seen used to express the number of possibilities if you have an n+i binary string, choosing i of the bits to be 1's. If there's a summation from i=0 to r, then it seems to me that might be a set of binary strings from length n to n+r, and the number of possible combinations for each string is added up. However, I don't see how the right hand side relates to this. Am I on the right track?
  2. jcsd
  3. Apr 20, 2016 #2


    User Avatar
    Science Advisor
    Homework Helper

    For b)
    RHS: the number of ways of building a binary string consisting of n+1 0's and r 1's.
    Now, the first 0 can be at position 1, position 2, ..., position r, position r+1. That gives an interesting partitioning.
  4. Apr 20, 2016 #3
    Ok I think I have it:

    Based on your partitioning, if the first 0 is at position 1, of the remaining n+r bits, there are n zeroes and r ones. Thus

    If the first 0 is at position 2, of remaining n+r-1 bits, there are n zeroes, r-1 ones. Thus
    Continuing, for first 0 at i+1 spot, of remaining n+r-i bits, there are n zeroes, r-i bits. Thus
    and i can vary from 0 to r. This is essentially the summation on the LHS but with i counting backwards. It describes every possible appearance of the bit string, just like the RHS.

    Does that seem right?

    It didn't seem like anything in this problem was really a "set"... I guess maybe the set of all partitions.
  5. Apr 20, 2016 #4


    User Avatar
    Science Advisor
    Homework Helper

    Yes, that's exactly what I had in mind.
    With "set", they probably meant the set of all binary strings consisting of n+1 0's and r 1's.
    Or maybe there is a totally different solution: that can happen in these combinatorial exercises.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted