Quandaries
and Queries 

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 nk 0's with no restriction  this is equal to the number of ways of arranging nk 0's and (k1) x's in a line, n1Ck1 (this is a combination, n1choose k1). 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 k1 spaces between the 1st & 2nd, ..., between the k1st and kth being none empty. Place a 1 in these k1 places and distribute the remaining mk+1 into the total k+1 places with no restriction; this is equal to the number of ways of arranging mk+1 1's and k x's in a line, m+1Ck . In total there are (n1Ck1)(m+1Ck) ways . In total there are (n1Ck1)(mCk1) ways. This is not the only way to look at the problem. When you see the answer, can you think of other explanations? Penny 

