Problem finding explicit function without multiple $\sum$s

Question

For $1≤n \in \mathbb{N}$, I want a function $f$ to have the following value:

The sum of all possible products $a_1 * a_2 * ... * a_n$, with $a_i \in \{1, 2, 3, 4\}$ and $a_1 ≤ a_2 ≤ ... ≤ a_n$.

For example:
$f(1) = 1 + 2 + 3 + 4 = 10$
$f(2) = 1*1 + 1*2 + 1*3 + 1*4 + 2*2 + 2*3 + 2*4 + 3*3 + 3*4 + 4*4 = 65$
$f(3) = 350$
$f(4) = 1701$

I know I could do it with $\sum$s, for example for
$f(3) = \sum_{k=1}^{4} \sum_{l=1}^{k} \sum_{m=1}^{l} k*l*m$

The problem however is that I would need one nested sum per $n$, which is not optimal. I would much rather prefer a function without any sums.

Any ideas?

Answer 1

https://oeis.org/A000453

There is a formula section on that page that can be adjusted to work with this specific sequence. I'll type it here in case OEIS goes down at some point (though I sincerely hope that never happens). $$f(n)=\frac{4^{n+4}-4\cdot3^{n+4}+6\cdot2^{n+4}-4}{24}$$

Answer 2

Your $f(3)$ can be written: \begin{align} f(3) &= \sum_{1 \le k \le 4} \sum_{1 \le l \le k} \sum_{1 \le m \le l} k \cdot l \cdot m \\ &= \sum_{1 \le k \le 4} k \sum_{1 \le l \le k} l \sum_{1 \le m \le l} m \\ &= \sum_{1 \le k \le 4} k \sum_{1 \le l \le k} l \cdot \frac{l (l + 1)}{2} \end{align} The inner sum is now a cubic polynomial in $l$, which can be written in closed (if messy) terms. This gives you a quintic in $k$, which again has a closed form.