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} $$

I want to define a $$f(n) = \sum_{m=1}^{2^n}\prod_{i=1}^n row_mcol_i$$

I'm not sure if I wrote the above equation correctly but in words it is the following, for each row multiply the columns values together and add it to the result of the previous row.

e.g from the table above we would have the following:

$$f(3) = 1 + g(0) + g(1) + g(0)g(1) + g(2) + g(2)g(0) + g(2)g(1) + g(2)g(1)g(0)$$

Any help in generalising the equation for $f(n)$ would be much appreciated. The tables above are merely to help illustrate the pattern, if possible I would prefer not to reference the rows and columns of some matrix.

Thanks in advance.

  • $\begingroup$ Why are you summing up to $2n$? $\endgroup$ – Ataraxia May 21 '13 at 18:25
  • $\begingroup$ I'm summing up to $2^n$ as this is the number of rows. $\endgroup$ – Manatok May 21 '13 at 18:31
  • $\begingroup$ What would, for example, m=3 be? $\endgroup$ – Ataraxia May 21 '13 at 18:32
  • $\begingroup$ I am trying to get m to correspond to the row, so if m=3 then we would be working on the third row and thus have 1xg(1)x1 = g(1) not sure if that makes sense... $\endgroup$ – Manatok May 21 '13 at 18:36
  • $\begingroup$ Numbering the rows by their power of two won't work, because row 3, 5, 6, 7, 9, etc. are not defined. I would suggest just numbering the rows normally. $\endgroup$ – Ataraxia May 21 '13 at 18:41

This is just $$(1+g(0))(1+g(1))(1+g(2))\dots(1+g(n-1))$$

This could be written as:

$$\prod_{k=0}^{n-1} (1+g(k))$$

Your expression could be written by defining $G(m,k)$ as $1$ if $m$ has zero in the $k$th bit and $g(k)$ otherwise. Then you want:

$$\sum_{m=0}^{2^n-1}\prod_{k=0}^{n-1} G(m,k)$$

But this simplifies to my above expression.

An alternative formulation is to define $[n]=\{0,1,\dots,n-1\}$ and then you can write your formula as:

$$\sum_{S\subseteq [n]} \prod_{k\in S} g(k)$$

This uses the fact that the numbers from $0$ to $2^n-1$ encode the subsets of $[n]$.

  • $\begingroup$ Fantastic! I love the simplicity of it. I tested it out by plugging in some values and it seems to do the trick. Thank you! $\endgroup$ – Manatok May 21 '13 at 18:52

Take the table to be a matrix $A\in \mathbb{R}^{m\times n}$.


  • $\begingroup$ Thanks for your help, I wanted to try steer clear of using a matrix though, the table was just to illustrate the problem. $\endgroup$ – Manatok May 21 '13 at 18:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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