Question:
How many arrangements are there with n 0's and m 1's, with k runs of 0's? (A run is a consecutive set [1 or more] of the same digit;
eg. 000 111 0 11 00 has three runs.)
Hi,
Think of the n 0's and how we can break them into k runs. This is the same as placing them in k boxes none of which are empty. Put a 0 in each box then distribute the rest of the n-k 0's with no restriction -- this is equal to the number of ways of arranging n-k 0's and (k-1) x's in a line, n-1Ck-1 (this is a combination, n-1choose k-1). Now we have to look at the m 1's. The 1's have to be placed in up to k+1 places -- before the 1st box of 0's, between the 1st & 2nd box of 0's, ..., after the last box of 0's with the k-1 spaces between the 1st & 2nd, ..., between the k-1st and kth being none empty. Place a 1 in these k-1 places and distribute the remaining m-k+1 into the total k+1 places with no restriction; this is equal to the number of ways of arranging m-k+1 1's and k x's in a line, m+1Ck . In total there are (n-1Ck-1)(m+1Ck) ways . In total there are (n-1Ck-1)(mCk-1) ways.
This is not the only way to look at the problem. When you see the answer, can you think of other explanations?
Penny