Arguing the correctness of an alternative, way to count how many bit sequences with exactly n zeroes and k+1 ones are there

Question

I was trying to count how many bit sequences with exactly n zeroes and k+1 ones are there.

One obvious reasoning is just by doing $ \binom {k+n+1}{k+1}$, by doing choose.

However, I was told that you could also do it by doing the following summation:

$$\sum^{n}_{i=0}\binom {k+i}{k}$$

If that is true then:

$$\sum^{n}_{i=0}\binom {k+i}{k} = \binom {k+n+1}{k+1}$$

Which after a lot of algebra that I will omit, can be verified by induction! Incredible. However, I am unsure what is the combinatorial reasoning is. Does someone know how to reason it combinatorially to establish the equality? Can you also justify the correctness of your argument?

In fact, I was told that the following is the "correct" reasoning, though I can't make sense of why its correct:

On the other hand, the number of zeroes i to the left of the rightmost one ranges from 0 to n. For a fixed value of i, there are $\binom {k+i}{k}$ possible choices for the sequence of bits before the rightmost one. If we sum over all possible i, we find that the number we want is $\sum^{n}_{i=0} \binom {k+i}{k}$

My main concern is with the summation. I can't understand the interpretation of the summation. Is it summing over disjoint subsets? Or why is it summing things? The only time I have seen sums in counting is when there are disjoint subsets (or with the inclusion-exclusion principle).

Even if you explain me what the interpretation means, I feel it might not be too helpful unless it has an explanation of its correctness.

---

Please provide as much detail on the combinatoric interpretation of the summation, the part of the question that I am having trouble understanding. Thats I guess what is giving me trouble. I fail to see why that description gives the desired equality.

For example, one aspect that I would liked addressed is, how come is that sum NOT double counting? As i increases, combinations from previous steps are "reconsidered"...or not? It seems to me they are. Then if they are, why is that summation NOT double counting?

---

BOUNTY

I am not able to put a bounty yet, but the answer that justifies the correctness well enough and convinces me to accept their answer, I will gladly reward you when the times comes.

Take it that if there is no accepted answer, I have not yet had my confusion/doubt clarified.

Answer 1

Short answer:
Count all arrangements of the k+1 ones spread from position 1 to position k+i+1

Long one:
In the k+n+1 positions,
place one '1' at position k+i+1. This is the sentinel element. Distribute the rest k '1'-s from position 1 to position k+i. This can be done in $${k+i\choose k}$$ ways.

This way you have an arrangement where '1'-s are spread between positions 1 and k+i+1 (both inclusive). Rest of the positions are of course '0'-s

Sum these over all i (0 <= i <= n ) and you will have all arrangement of k+1 1's and n '0'-s over k+n+1 positions.

Answer 2

The idea behind doing that sum is that you are classifying according to how many zeroes come before the the last one. Since the number of zeroes before the last one can be any number from $0$ to $n$ we get the desired bijection.

Another way to see why the identity $\binom{n+k+1}{k+1}=\sum\limits_{i=0}^n\binom{k+i}{k}$

is to notice the left hand side is telling us the number of subsets of size $k+1$ of the set $\{1,2,3\dots n+k+1\}$ While the right hand side is giving us the number of subsets of size $k$ of $\{1,2,3,4\dots k\}$ plus the number of subsets of size $k$ of $\{1,2,3\dots k+1\} \dots$ plus the number of subsets of size $k$ of $\{1,2,3\dots k+n\}$

Now consider a subsets $A$ of $k+1$ elements of the set $\{1,2,3\dots,n+k+1\}$ , let $w$ be its largest element. We shall assign to this subset the subset of the set $\{1,2,3\dots w-1\}$ consisting of all the elements in $A$ except $w$. You should check that this function is indeed a bijection between the subsets counted in the left hand side and the subsets counted in the right hand side.

Answer 3

Taking $A_i$ to be the set of sequences in which the number of zeros to the left of the rightmost digit one is $i,$ and doing this once for each $i=0,\ldots,n,$ does in fact give you $n+1$ disjoint sets $$A_0,\ldots,A_n.$$ No element of $A_p$ can be in $A_q$ for any $p\neq q,$ because you can always simply count the number of zeros to the left of the rightmost one in any finite bit sequence. That number can be $p,$ or it can be $q,$ but it cannot be both $p$ and $q.$

Moreover, any sequence of $n$ zeros and $k+1$ ones must be in one of the sets $A_0,\ldots,A_n,$ again because you can simply count the number of zeros to the left of the rightmost one. That number cannot be greater than $n$ (because then there would be more than $n$ zeros altogether in that sequence) and it certainly cannot be less than $0.$

So the sets $A_0,\ldots,A_n$ are a partition of the set of all sequences of $n$ zeros and $k+1$ ones, and the size of that set is $|\bigcup A_i| = \sum |A_i|.$

EDIT: Here's a specific example that I hope may help to visualize the general case described above:

For $n=2$ and $k=2,$ we have $$\begin{eqnarray} A_0 &=& \{ 11100 \},\\ A_1 &=& \{ 11010, 10110, 01110 \},\\ A_2 &=& \{ 11001, 10101, 01101, 10011, 01011, 00111 \}.\\ \end{eqnarray}$$

Each set in this example is exactly as I described it for the general case (for example, the number of zeros to the left of the rightmost one is exactly $2$ in each element of $A_2$) and as you can see, there are no duplicates.