# f(n) for rows with $2^x$ bits on

This is similar to a question I asked here but now I need to alter it so I have brought across the relevant parts.

Given a binary table with n bits as follows:

$$\begin{array}{cccc|l} 2^{n-1}...&2^2&2^1&2^0&row\\ \hline \\ &0&0&0&1 \\ &0&0&1&2 \\ &0&1&0&3 \\ &0&1&1&4 \\ &1&0&0&5 \\ &1&0&1&6 \\ &1&1&0&7 \\ &1&1&1&8 \end{array}$$

If I replace each $0$ with a $1$ and each $1$ with $g(n)$ as follows

$$\begin{array}{cccc|l} 2^{n-1}...&2^2&2^1&2^0&row\\ \hline \\ &1&1&1&1 \\ &1&1&g(0)&2 \\ &1&g(1)&1&3 \\ &1&g(1)&g(0)&4 \\ &g(2)&1&1&5 \\ &g(2)&1&g(0)&6 \\ &g(2)&g(1)&1&7 \\ &g(2)&g(1)&g(0)&8 \end{array}$$

If I multiply the values in a row together and add up each row, thanks to Thomas Andrews, I now know that I can represent it as follow: $$f(n) = \prod_{k=0}^{n-1} (1+g(k))$$

But now I want to be more selective about the rows that I am adding, instead of adding all of them I only want to add rows that have a $2^x$ number of $g(k)$'s. i.e add all of the rows that have $2,4,8...$ g(k)'s in them.

In my example table above I would add rows 4,6,7 together as these each have 2 $g(k)$'s in them. If n=4 in my above example them we would also need to add row 16 as it would have 4 g(k)'s in its row. If n=5 there would be 5 such rows that have 4 g(k)s in them. I hope this makes sense.

If I were only concerned with rows that have 2 $g(k)$'s in them I could have something as follows:$$f(n) = \sum_{j=1}^{n-1} \sum_{k=j+1}^n g(j)g(k)$$

I can't seem to extend this to all $2^x$ rows and not only $2^1$ rows. I was considering some recursive function but can't seem to figure it out. Any help would be much appreciated.

-

Following the interpretation that you have, consider the expansion as $f(n, x) = \prod ( 1 + g(n) x )$, and then find the coefficients of the terms of degree $2^k$, and then add them up.
If you want to find the sum of those with an even number of $g(k)$, then that is much more approachable.