3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Perhaps the best way to understand the argument in the quoted passage is to look for a counterexample. By this I mean you try to find a specific written sequence of ones and zeros, such as 1100101 or 001001001000, and show how this exact sequence is counted in two separate terms of the sum (for two specific values of $i$; you should be able to say something like, "This sequence was counted in the term $\binom{k+5}{k}$ and then again in the term $\binom{k+6}{k}$"). The problem is simple enough that if a counterexample exists, it should not be hard to construct. $\endgroup$
    – David K
    Nov 6, 2014 at 4:27

3 Answers 3

1
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ Let me ask you one question that I still don't grasp. Its kind of hard to write but, let me try. As i increases, the k 1's have more options to be on different positions. However, even though they have more options, they also have positions/options from the previous step, i.e. step k+i-1. All of the combinations of the positions of the 1's from 0 to k+i-1 have already been counted, right? Then if that is the case, how on earth is the summation we wrote not double counting? For me it seems weird that its not (Im sure Im wrong I just wish to understand why my intuition is wrong). $\endgroup$ Nov 5, 2014 at 5:31
  • $\begingroup$ The sentinel element makes sure you do not repeat cases from the previous step. The right-most 1 in the i-th iteration is precisely at position k+1+i. Previous step it was at k+i. Previous to that the right-most 1 was at k+i-1 $\endgroup$
    – Shooter
    Nov 5, 2014 at 8:11
  • $\begingroup$ What do you mean that it makes sure cases are not repeated from the previous case? I thought it was inevitable that you are double counting the reason is the following: $\endgroup$ Nov 5, 2014 at 14:29
  • $\begingroup$ Correct me where I am wrong. Consider the first positions for the ones $\binom {k}{k}$ when i = 0. Let the $X_{(\binom {k}{k},1st)} = \{1, ..., k\}$ be the set from the first term in the summation specifying the bit position of the 1's selected when i = 0 i.e. there are zero zeroes to the left. Now consider the case when there is one zero. Now we have $\binom {k+1}{k}$. In that counting it has to be counting k subsets chosen from k+1. In those, sets it must contain $\{1, ..., k\}$, specifying the position of the 1's. But we already counted that. However, somehow its ok. Isn't that inevitable? $\endgroup$ Nov 5, 2014 at 14:30
  • $\begingroup$ Firstly, we are dealing with k+1 ones. The set is {1,2,...,k,k+1} when i = 0. In this case we place the k+1 -th 1 at its position and play with the rest. When k = 1, we can possibly place 1-s at {1,2,...,k+1,k+2}; we place one 1 at k+2 position and choose one of {1,2,...,k+1}. For ith: we can choose to place 1's at {1,2,...,k+i+1}. We place a 1 at k+i+1 and place the rest k 1's by choosing k from the k+i positions on the left. Please let me know if this is not clear. $\endgroup$
    – Shooter
    Nov 5, 2014 at 16:16
0
$\begingroup$

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.

$\endgroup$
10
  • $\begingroup$ are you sure you don't have typos on your left hand side? it should be n+k+1 on top. $\endgroup$ Nov 5, 2014 at 4:47
  • $\begingroup$ yes, I had a typo, it should be fine now $\endgroup$
    – Asinomás
    Nov 5, 2014 at 5:01
  • $\begingroup$ did you mean subsets of size k+1? when you wrote "is to notice the left hand side is telling us the number of subsets of size k of the set" $\endgroup$ Nov 5, 2014 at 5:08
  • $\begingroup$ Dang, yes. Sorry . On the bright side it seems like you are understanding the idea. $\endgroup$
    – Asinomás
    Nov 5, 2014 at 5:09
  • 1
    $\begingroup$ Sorry if this is extremely easy for you, but do you mind providing a explanation/justification of the correctness of the summation? Like when we consider k subsets from $\{1,...,k\}$ to $\{1,...,k+1\}$ to $\{1,...,k+2\}$ to $\{1,...,k+n+1\}$, how as we progress in this sum, how come we are NOT double counting? I think I understand what the statement means and what its summing now. However, I fail to appreciate the correctness of the combinatorial argument. If you could justify that I would be immensely grateful :) Thnx for your patience so far Jorge. $\endgroup$ Nov 5, 2014 at 6:04
0
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ I thought that there was invalid double counting. Correct me where I am wrong. Consider the first ones $\binom {k}{k}$. Let the $X_{(\binom {k}{k},1st)} = \{1, ..., k\}$ be the set from the first term in the summation specifying the bit position of the 1's selected when i = 0 i.e. there are zero zeroes to the left. Now consider the case when there is one zero. Now we have $\binom {k+1}{k}$. In that counting it has to be counting k subsets chosen from k+1. In those, sets it must contain $\{1, ..., k\}$, specifying the position of the 1's. But we already counted that. However, somehow its ok. $\endgroup$ Nov 5, 2014 at 14:28
  • $\begingroup$ From my argument (if we are thinking that the $A_j$ are the same, which is to clear because you didn't explicate what $A_i$ was) there seems to be an inherent double counting in this method, so things can't be disjoint. Obviously, I am the confused one so I might be wrong. For me, $A_i$ is the number of sets from $\{1,...,k+i \}$ that specifies the bit position of the ones to the left of the rightmost one. $\endgroup$ Nov 5, 2014 at 14:58
  • $\begingroup$ Ultimately, we are supposed to be counting bit sequences, not sets of integers. If you can show one sequence that is counted for $i=0$ and show that the same sequence is counted for $i=1,$ then you have shown double counting. But the sequences generally are distinguished not just by the position of the leftmost $k$ ones, but also by the position of the rightmost one. It just happens that all the sequences we count for a single value of $i$ all have the $k+1$st one in the same place. The sequences we count for any other $i$ will have the rightmost one somewhere else. $\endgroup$
    – David K
    Nov 5, 2014 at 18:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .