Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Among all $n$-bits binary numbers, we count the continuous 1s as a single 1. For example, 10011101 gets three 1s, 111 gets one 1.

$C(n,k)$ is the number of all $n$-bit binary numbers that get $k$ 1s (according to the above specification).

For example, $C(3,1)=6$, and they are: 001,010,100,011,110,111; while 000,101 are not.

Find a simplified form for $C(n,k)$.

share|improve this question

3 Answers 3

Hint: I would look for a recurrence for $C(n,k)$, and start by defining $D(n,k)$ as the number of binary numbers $n$ bits long with a score of $k$ and ending in $1$, and $E(n,k)$ as the number of binary numbers $n$ bits long with a score of $k$ and ending in $0$. Then $C(n,k)=D(n,k)+E(n,k)$. Try to find a recurrence for $D(n,k)$ in terms of $D(n-1,k)$ and $E(n-1,k-1)$ (Why?) and one for $E(n,k)$. Then calculate some values, guess a solution, and prove by induction.

share|improve this answer
    
Thank you very much, I get:$D(n,k)=D(n-1,k)+E(n-1,k-1)$,$E(n,k)=D(n-1,k)+E(n-1,k)$, and I get $D(n,k)=$$n\choose 2*k-1$,$E(n,k)=$$n\choose 2*k$,$C(n,k)=$$n+1\choose 2*k$. –  jchzhu Oct 17 '12 at 2:43
    
but this is by induction,it there a more reasonable way? –  jchzhu Oct 17 '12 at 2:47
    
@jchzhu: That was my first thought. Looks like you have it. Later I realized (partly based on your results) that you could look at it as stars and bars. There are $n$ stars (the bits) and you can place $2k$ bars (the transitions between $0$ and $1$ or back) in the places between the stars or at either end. We think of the lines outside as being $0$. This yields your expression $C(n,k)={n+1 \choose 2k}$ because there are $n+1$ places for the bars. Good work. –  Ross Millikan Oct 17 '12 at 2:57

Here’s a purely combinatorial solution.

Let $W(n,k)$ be the set of $n$-bit words having $k$ blocks of $1$’s, and let $\widehat W(n,k)$ be the set of $(n+2)$-bit words that begin and end with $0$ and have $k$ blocks of $1$’s. The map $W(n,k)\to\widehat W(n,k):w\mapsto 0w0$ is clearly a bijection. Each word in $\widehat W(n,k)$ consists of alternating blocks of $0$’s and $1$’s, starting and ending with blocks of $0$’s, so there must be $k+1$ blocks of $0$’s. $C(n,k)$ is therefore the number of $(n+2)$-bit words consisting of $k+1$ blocks of $0$’s alternating with $k$ blocks of $1$’s. Put a $2$ between adjacent blocks; the result is a word with $2k$ $2$’s separating $2k+1$ alternating blocks of $0$’s and $1$’s, the first and last blocks being of $0$’s.

If $0w0$ is such a word, let $x_0$ be the number of $0$’s in the first block, $x_1$ the number of $1$’s in the next block, and so on; $x_{2k}$ will be the number of $0$’s in the last block. Clearly $$x_0+x_1+\ldots+x_{2k}=n+2\;,\tag{1}$$ and every solution of $(1)$ in positive integers corresponds to one word in $\widehat W(n,k)$ and hence to one in $W(n,k)$. Counting these solutions is a standard stars-and-bars problem, and the result is that $$C(n,k)=\binom{n+1}{2k}\;.$$

share|improve this answer
    
This is the same idea as in my last comment. Two explanations are better than one. Thanks. –  Ross Millikan Oct 17 '12 at 3:50
    
@Ross: It is indeed, though I’d seen only your suggestion to get a recurrence and the OP’s implementation when I posted. Oh, well; as you say, the more extended explanation may help someone. –  Brian M. Scott Oct 17 '12 at 3:54

Okay, this is much longer than I intended. I tried to write this post about another method of solving this problem---specifically, the use of generating functions. I sort of skim over a lot of material, but hopefully it conveys the general idea!


There is another method which you could use to try to solve this problem---the method of generating functions. Generating functions allow us to solve a large number of combinatorial problems rather mechanically by giving us tools to count things. If you've not seen generating functions before, the main idea behind them is that in expanding polynomials, the coefficient in the $n$-th degree term is related to the number of times it can be combined, in a sense.

Problems with binary strings can be easily dealt with in terms of generating functions by employing an idea known as decomposition. The main idea is that we're going to break a binary string down by the ways we could make strings. This document provides some more information if you're curious.


The Problem

We are going to see if we can define a bivariate generating function $\Phi(x, y)$ where the degree of the $x$ monomial is counts the length of the binary string and the degree of the $y$ monomial counts the number of blocks, or continuous segments of $1$'s.

In order to define our generating function, we are going to decompose binary strings in the following manner:

First, we can form binary strings, in general, by the following decomposition:

$$\{0\}^*\left( 1\{1\}^*0\{0\}^*\right)^*\{1\}^*$$

In the notation above, when we have multiplication, that is simply string concatenation; the $^*$ operation means that we are going to consider all the possible lengths of whatever is in the braces, so $\{0\}^* = \{\epsilon, 0, 00, 000, \dots \}$, where epsilon is the empty string.

Basically, the decomposition above says that any binary string is going to be a block of an arbitrary number of $0$'s , followed by blocks of alternating $0$'s and $1$'s, of which there are an arbitrary number of each, and at last, we may have a block of $1$'s. If you take a moment to think about this, you will see that this indeed describes the way all binary strings may be represented, and in fact, that there is only one way to form any string with this sort of decomposition. This is means that each string has a unambiguous decomposition, and this property gives us nice lemmas as to how we may form generating functions.

Alright, the problem with the above decomposition is that we're going to have a tough time counting the number of $1$ blocks above because the $1$ block at the very end is not necessarily there---it may very well be empty! But this turns out to be a minor problem, because then we have two cases: either there is a block at the end or there is not. Furthermore, it's not hard to see that this defines two disjoint subsets of all binary strings, so we may continue to count simply by adding the two results that we shall get shortly.

The Approach

Now that we have a rough idea as to what we're going to do, how are we going to do it? I suggest that you take a look at the document above for some background since I am not going to explain every minor detail. Nonetheless, if you have questions, feel free to ask and I would be delighted to try to explain more!

Basically, the idea is that we're going to exploit the formal rules of algebra in order to help solve the problem. We shall use the fact that

$$\frac{1}{1-x} = 1 + x + x^2 + x^3 + \dots$$

in that the number of length $n = 0, 1, 2,\dots$ strings of $0$'s or $1$'s alone is going to be equal to the coefficient of the $n$-th degree term in the formal power series above, namely, there is going to be only $1$ string that is like $000$, or $111111$, or of any length $n$.

Finally, one more thing I am going to try to quickly explain: when considering the generating function of binary strings with respect to decompositions, we have three wonderful lemmas that tell us that if $\Phi_A$ is the generating function for the string $A$, and $\Phi_B$ is the generating function for the string $B$, then \begin{align} \Phi_{A + B} & = \Phi_A + \Phi_B , \\ \Phi_{A\times B} & = \Phi_A \Phi_B , \\ \Phi_{A^*} & = \frac{1}{1 - \Phi_A} . \end{align}

Okay, now to get the generating function for the decomposition

$$\{0\}^*\left( 1\{1\}^*0\{0\}^*\right)^*\{1\}^*$$

we need to find the generating functions for the individual parts. Recall that we are going to use a generating function which has two variables, the $x$ variable counts the length of the string whereas the $y$ variable counts the number of $1$ blocks. So we have the following generating functions

\begin{align} \Phi_{0^*}(x, y) & = \frac{1}{1-x}, \\ \Phi_{1(1)^*}(x, y) & = \frac{yx}{1-x}, \\ \Phi_{0(0)^*}(x, y) & = \frac{x}{1-x}, \\ \Phi_{(1(1)^*0(0)^*)^*}(x, y) & = \frac{yx^2}{(1-x)^2}. \end{align}

There is going to be difficulty encoding the last lone $1$ block, however, because if it exists, we wish to tag a $u$ on it, but not otherwise. So we split our count into two cases: either the $1$ block exists or it does not. Then our generating function for our decomposition is

$$\Phi_S(x, y) = \Phi_{0^*}\Phi_{(1(1)^*0(0)^*)^*} + \Phi_{0^*}\Phi_{(1(1)^*0(0)^*)^*}(x, y)\Phi_{1(1)^*}$$

Expanding and simplifying the resulting expression, we get the enormous expression

\begin{align} \Phi_S(x, y) & = \left(\frac{1}{1-x}\right)\left(\frac{1}{1-\frac{yx^2}{(1-x)^2}}\right)\left(1 + \frac{yx}{1-x}\right), \\ & = \frac{1 - (1-y)x}{(1-y)x^2 - 2x + 1}. \end{align}

With the help of the quadratic formula, we are able to factor the denominator into $\left((1+\sqrt{y})x - 1\right)\left((1-\sqrt{y})x - 1\right)$. Using this, we can then go and express our original fraction as partial fractions with linear denominators. Going through that work gives you

$$\Phi_S(x, y) = \frac{1}{2} \left( \frac{1 - \sqrt{y}}{1- x(1-\sqrt{y})} + \frac{1 + \sqrt{y}}{1 - x(1 + \sqrt{y})}\right).$$

Equivalently, if we expand them into formal power series, we have

\begin{align} \Phi_S(x, y) & = \frac{1}{2} \left( (1-\sqrt{y})(1 + x(1-\sqrt{y}) + \dots) + (1+\sqrt{y})(1 + x(1+\sqrt{y}) + \dots )\right), \\ & = \frac{1}{2}\left(\sum^\infty_{n=0}(1-\sqrt{y})^{n+1}x^n + \sum^\infty_{n=0}(1+\sqrt{y})^{n+1}x^n\right). \end{align}

Now, we expand each of the binomials $(1-\sqrt{y})^{n+1}$ and $(1+\sqrt{y})^{n+1}$ by the binomial theorem, and note that each of the odd powered terms will cancel out, since we have a positive and negative term matching each other. This is great since we get rid of all the square roots. Now, we simplify the expression to

\begin{align} \Phi_S(x, y) & = \sum^\infty_{n=0}\left(\sum^{\lfloor \frac{n+1}{2} \rfloor}_{k=0} {n+1 \choose 2k} y^k\right)x^n. \end{align}

Recall that the $x$ variable counted the length of the string whereas the $y$ variable counted the number of $1$ blocks in the string. Also, the point of generating functions is that the coefficient of the $x^ny^k$ term corresponds to the number of string of length $n$ and $k$ blocks of $1$, so in otherwords, we see that the number of $n$-bit strings with $k$ blocks is

$$C(n, k) = {n+1 \choose 2k}.$$

And indeed, this agrees with some of the other answers here, so I think I did this right!


Alright, that was long, hand-wavy but hopefully somewhat useful. If you have questions, feel free to ask! I think it's always nice to have multiple ways to do things, and generating functions is just one of those things that give such a nice general method to do combinatorial problems, though they often prove somewhat messy during the process of derivation. In any case, I hope you enjoyed the idea!

share|improve this answer
    
Why did you make this community wiki? –  joriki Dec 22 '12 at 3:01
    
@joriki: is it fair when composing the generating functions to use the same variables? It seems the $x$ in $\Phi_{0^*}(x, y) = \frac{1}{1-x}$ counts the number of leading zeros while the $x$ in $\Phi_{1(1)^*}(x, y) = \frac{yx}{1-x}$ counts the number of $1$'s after the first, so it should really be $\frac y{1-y}$ and the one for the string of zeros next should be $\Phi_{0(0)^*}(z)=\frac z{1-z}$. –  Ross Millikan Dec 22 '12 at 4:11

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.