In how many ways can i obtain 4 using 0.125 and multiples?

Question

In how many ways can I obtain $4$ as a sum of : $0.125$, $0.25$, $0.5$, $1$, $2$, $4$ with repetitions of values? The order of the sum is important, for example $(1, 1, 2)$ is different from $(1, 2, 1)$ and different from $(2, 1, 1)$,

Answer 1

$4=32\times 0.125$, so write down $$4 = \underbrace{0.125+\cdots +0.125}_{32 \text{ times}}.$$ Now it is just a matter of in how many appropriate ways you can group the $0.125$ summands to your actual summands. E.g. you can group it like that: $$ 4 = \underbrace{0.125+\cdots +0.125}_{4 \text{ times }\rightarrow\, 0.5} +\underbrace{0.125+\cdots +0.125}_{4 \text{ times }\rightarrow\, 0.5} +\underbrace{0.125+\cdots +0.125}_{8 \text{ times }\rightarrow\, 1} +\underbrace{0.125+\cdots +0.125}_{16\text{ times }\rightarrow\, 2} , $$ which gives $4=0.5+0.5+1+2$. So the question is: in how many ways can you write the number $32$ as an ordered sum of powers of $2$. Lets investigate this recursively: The power $2^0=1$ can only be written in a single way, so define $s_0=1$. The power $2^n$ can be written as $2^n$ or decomposed in $2^{n-1}+2^{n-1}$ and the left and the right summand can both be independently decomposed in $s_{n-1}$ possible ways. So we have $s_n=1+s_{n-1}^2$. As $32=2^5$, you can check that this gives you $s_5=458330$ ways.

Answer 2

Instead of considering $\left\{\frac{1}{8},\frac{1}{4},\frac{1}{2},1,2,4\right\}$ and asking for non-negative integer solutions of the equation \begin{align*} \frac{1}{8}x_1+\frac{1}{4}x_2+\frac{1}{2}x_3+x_4+2x_5+4x_6=4 \end{align*} we can multiply the quantities with $8$, consider the set $\{1,2,4,8,16,32\}$ and ask for non-negative integer solutions of \begin{align*} x_1+2x_2+4x_3+8x_4+16x_5+32x_6=32 \end{align*}

We can reformulate the problem and since the order of the summands matters we ask for the number of compositions of $32$ generated by $$\{1,2,4,8,16,32\}$$

Using generating functions we encode a selection of an element from $\{1,2,4,8,16,32\}$ by \begin{align*} x+x^2+x^4+x^8+x^{16}+x^{32} \end{align*} and ask for the coefficient of $x^{32}$ denoted as $[x^{32}]$ in the geometric series $G(x)$ with

\begin{align*} G(x)&=\frac{1}{1-\left(x+x^2+x^4+x^8+x^{16}+x^{32}\right)}\\ &=\sum_{n=0}^\infty\left(x+x^2+x^4+x^8+x^{16}+x^{32}\right)^n\\ &=1+x+2x^2+3x^3+6x^4+10x^5\\ &\qquad+18x^6+31x^7+\color{blue}{56}x^8+\cdots+47350056 x^{32} + \cdots\tag{1} \end{align*} The last line was expanded with some help of Wolfram Alpha.

Let's look at a small example, the number of compositions of $8$ marked in blue. We see from (1) there are $56$ different possibilities to obtain $8$ as sum of $\{1,2,4,8,16,32\}$. These are \begin{array}{lllrr} 1+1+1+1+1+1+1+1&\qquad &\longrightarrow\qquad &\frac{8!}{8!}=&1\\ 1+1+1+1+1+1+2&\qquad &\longrightarrow\qquad &\frac{7!}{6!1!}=&7\\ 1+1+1+1+2+2&\qquad &\longrightarrow\qquad &\frac{6!}{4!2!}=&15\\ 1+1+1+1+4&\qquad &\longrightarrow\qquad &\frac{5!}{4!1!}=&5\\ 1+1+2+2+2&\qquad &\longrightarrow\qquad &\frac{5!}{2!3!}=&10\\ 1+1+2+4&\qquad &\longrightarrow\qquad &\frac{4!}{2!1!1!}=&12\\ 2+2+2+2&\qquad &\longrightarrow\qquad &\frac{4!}{4!}=&1\\ 2+2+4&\qquad &\longrightarrow\qquad &\frac{3!}{2!1!}=&3\\ 4+4&\qquad &\longrightarrow\qquad &\frac{2!}{2!}=&1\\ 8&\qquad &\longrightarrow\qquad &\frac{1!}{1!}=&1 \end{array} which sum up to

\begin{align*} 1+7+15+5+10+12+1+3+1+1=\color{blue}{56} \end{align*}

In the first column we see a representative and the number in the second column gives the possible rearrangements of this representation.

Using WA we obtain the coefficient $x^{32}$ of $G(x)$ and summarize:

The number of arrangements to sum up $4$ built from $\{\frac{1}{8},\frac{1}{4},\frac{1}{2},1,2,4\}$ is the same as the number of arrangements to sum up $32$ built from $\{1,2,4,8,16,32\}$. This is the coefficient of $x^{32}$ in $G(x)$, namely \begin{align*} [x^{32}]G(x)=[x^{32}]\frac{1}{1-\left(x+x^2+x^4+x^8+x^{16}+x^{32}\right)}=47350056 \end{align*}

Add-on: @N.Shales proposes in his nice comment an easy way to manually obtain the coefficient of $x^{32}$.

Noting that \begin{align*} G(x)=1+\left(x+x^2+x^4+x^8+x^{16}+x^{32}\right)G(x) \end{align*} we derive with $$G(x)=\sum_{n=0}^\infty g_nx^n$$ the recurrence relation

\begin{align*} g_n&=g_{n-1}+g_{n-2}+g_{n-4}+g_{n-8}+g_{n-16}+g_{n-32}\qquad &n> 0\\ g_0&=1\\ g_n&=0\qquad &n<0 \end{align*}