String of 0's and 1's in combinatorics Here is a question in one of my combinatorics homework.
We want to know the number of string of $n$ ones and zeros in which no zeros are next to one another and out of those $n$ digits we have $m$ zeros. We need to find the formula that gives us this number of strings but I have no idea how to do it.
I have defined a reccurence formula for $T^n_m$ which is the number of strings that respect the condition (no two zeros are next to one another) and here it is:
$$T^n_m=T^{n-2}_{m-1}+T^{n-1}_{m}$$ I have also been able to find some identités and properties of $T^n_m$ and here they are:
$$T^n_n=0 \iff n >1$$ $$T^n_1=n \iff n>0$$ $$T^n_m=0 \iff 1<n<m$$ $$T^1_1=1$$ 
$$T^1_0=1$$ $$T^n_0=1$$
 A: Lets first partition the problem into two cases:
$(1)\   m \leq n-m+1$
$(2)\   m > n-m+1$
A $00$ occurrence is not allowed, so we may only have $01$, $10$ occurrences.
Lets address $(2)$ first. There are $n-m$ $1$'s and $m$ $0$'s . All $0$'s need to be paired with $1$'s. So if we consider $1$'s as our pigeon-holes, our $0$'s are pigeons. Now if we try placing all our pigeons into our pigeon holes, since
$m > n-m+1$ we are going to have at least one occurrence of the dreaded $00$ 
So $(2)$ is impossible. 
$(1)$ is possible, we can even have $m = n-m+1$ but if this is the case, the answer to how many strings you can produce is kind of trivial, you can try that out for yourself.
So we'll consider the other cases, which are when the number of $0$'s are equal to the number of $1$'s or less than the number of $1$'s . Again, the case of equality is pretty simple as well, so I won't talk about it.
Now what remains is when there are fewer $0$'s than $1$'s .
There is a general way of solving this problem, and it involves a 'phantom' or 'ghost' position.
First of all, lets pair all our $0$'s with $1$'s so that we have $01$ groups. This is always possible, as we have fewer $0$'s than $1$'s .
There will thus be $m$ of these groups, and $n-2m$ lingering $1$'s .
So we see that we've reduced the problem to a simpler one, how many ways can we arrange these new objects in a row? We are considering $01$ as ONE object now, not two distinct objects.
Well, that's pretty straight forward, this is just equivalent to the number of ways we can choose $m$ positions from $n-m$ possible positions. Which is, as you know, ${n-m}\choose {m}$. But wait, this does leave out some cases!
The cases it leaves out are when we could have a $0$ on the extreme right of the row! Or $0$'s on both extremes of the row!
To account for this, we introduce a 'phantom' position on the extreme right, if we decide to place a $01$ in this 'phantom' position, it simply flips the $01$ into a $0$, so that now we CAN have a $0$ on the extreme right in conjunction with every other combination.
So now the number of ways is simply ${n-m+1}\choose{m}$ as we've introduced the phantom position.
Let me know if this makes sense.
A: Consider $N$ blank spaces. You need to find the number of ways of filling $m$ zeroes in these $N$ spaces such that no two zeroes come together. You can do this in the following way:
Instead of filling $m$ zeroes in $N$ spaces and then filling the remaining spaces with ones, consider the ways of filling $n-m+1$ spaces with $m$ objects, where the first $m-1$ objects in the row are each $01$ and the last object in the row is $0$. Then fill the remaining spaces with ones. 
See here that if you expand any such arrangement, you'll get a unique number consisting of zeroes and ones in which no zero is followed by another zero. 
Similarly, every such number can be "compressed" into a unique arrangement of this kind. Thus the number of such numbers in which no zero is followed by a zero is $^{n-m+1} \ C \ _m$.
A: You can define $A$ recursively as
\begin{align}
& A(n, m) = A(n-1, m) + A(n-2, m-1) \\
\text{ where } \\
& A(n, 0) = 1, \forall n \geq 0 \\
& A(n, 1) = n, \forall n \geq 1 \\
& A(n, m) = 0, n \leq m, \text{ except cases above} 
\end{align}
A: It's hard for me to see where you could have got stuck after you found the recurrence. You used your recurrence to make a table of $T^n_m$ for small values of $m$ and $n$ (I'm sure you did that, I can't imagine any reason why you wouldn't), and then—didn't you notice that your table looks Pascal's triangle? (Well, you have to look at it slantwise, but still . . .) Once you recognize Pascal's triangle, you've got the formula:
$$T^n_m=\binom{n+1-m}m\text{ for }0\le m\le n+1.$$
Of course you still need to prove it. For that, you can either use mathematical induction (boring) or try to think of a combinatorial proof. It might be easier to find a combinatorial proof now that you know the answer; the formula $\binom{n+1-m}m$ is a good hint. At least, you could have posted the question this way: "Looks like the answer is $\binom{n+1-m}m$; is there a way to prove it without resorting to brute force induction?"
