A half-series is a series of numbers in which every number (except the first) is either double the previous element, or half of the previous element.

Question

How many half-series of length $12$ are there that start with $1$ and end in $2$?

The answer is ${11 \choose 6} = {11 \choose 5}$.

How did they reach that result? Can you explain me?

Answer 1

More generally, if the sequence has length $n$, it starts with $2^a$ and ends in $2^b$, then in order to generate the sequence from the first term to the last one, we use $k$ multiplications by $2$ and $j$ divisions by $2$, in any order, with $k$ and $j$ non negative integers such that $$k+j=n-1\quad\text{and}\quad k-j=b-a.$$ If $n-1+b-a$ is a non-negative even number then $k=(n-1+b-a)/2$ and the procedure can be done in $\binom{n-1}{k}=\binom{n-1}{n-1-k}$ ways (distribute the $k$ multiplications by $2$ over $n-1$ places).

Answer 2

Well, let us find a nice model for this problem. A half-series, as defined is a (possibly finite) sequence of numbers $(a_k)_{k\in\mathbb{N}}$ which has the following property:

For every $k\geq1$: $$2a_{k+1}=a_k\text{ or }a_{k+1}=2a_k$$

So, instead of thinking of such a sequence as a sequence of numbers, we can think of it as a sequence of the two operations we have: doublification ond halving. For our convenience, we use the symbol $1$ for multiplying with $2$ and the symbol $0$ for dividing with $2$. Now every sequence of the above formand of length $n$ can be described by an element of $\{0,1\}^{n-1}$, which is another sequence including the $n-1$ operations we need to calculate all it elements given its first one.

So, to find how many half-series of length $12$ exist, we have to find how many seqeuences with $11$ elements from $\{0,1\}$ there exist with the following porperty:

They have $6$ $1$s and $5$ $0$s.

Why is that? Because our first term is $1$ and our second is $2$, the double of it, and the two operations we have, if apllied together, do not change the given number (the one is the inverse of the other), so we need one more doublification than halvation. Now, it is obvious that to choose a sequence from $\{0,1\}^{11}$ with 6 $1$s we have exactly: $$\binom{11}{6}=\binom{11}{5}$$ ways.

Answer 3

To reach $2$ from $1$ in $11$ steps, we must have used $2\cdot\frac12\cdot2\cdot\frac12\cdot2\cdot\frac12\cdot2\cdot\frac12\cdot2\cdot\frac12\cdot2$ in any order,

thus $\dfrac{11!}{6!5!} = \dbinom{11}6 = \dbinom{11}5$