Combinatorics -- Counting Sets of Binary Strings

[QuietMind]

Homework Statement

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|.

a)
$\binom{2n}{n} \sum_{k=0}^n \binom{n}{k} * \binom{n}{n-k}$
b)
$\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.

Homework Equations

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?

 

[Samy_A]

Homework Statement

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|.

a)
$\binom{2n}{n} \sum_{k=0}^n \binom{n}{k} * \binom{n}{n-k}$
b)
$\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.

Homework Equations

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?

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.

 

[QuietMind]

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
$\binom{n+r}{r}$

If the first 0 is at position 2, of remaining n+r-1 bits, there are n zeroes, r-1 ones. Thus
$\binom{n+r-1}{r-1}$
Continuing, for first 0 at i+1 spot, of remaining n+r-i bits, there are n zeroes, r-i bits. Thus
$\binom{n+r-i}{r-i}$
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.

 

[Samy_A]

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
$\binom{n+r}{r}$

If the first 0 is at position 2, of remaining n+r-1 bits, there are n zeroes, r-1 ones. Thus
$\binom{n+r-1}{r-1}$
Continuing, for first 0 at i+1 spot, of remaining n+r-i bits, there are n zeroes, r-i bits. Thus
$\binom{n+r-i}{r-i}$
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.

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.