EDIT: he publicado una generalización de esta pregunta a MathOverflow aquí.
Supongamos que tenemos dos funciones binarias $f,g$, que es conmutativa y asociativa, es decir, la satisfacción de $$ f(a,b) = f(b,a) \qquad g(a,b) = g(b,a)$$ $$ f(a,f(b,c)) = f(f(a,b),c) \qquad g(a,g(b,c)) = g(g(a,b),c)$$ para todos los $a,b,c$. Si tenemos $n$ indeterminates $x_1, x_2, \ldots, x_n$, ¿cuál es el número de $a_n$ de las distintas expresiones que nos puede producir el uso de $f,g$ y uno de cada indeterminado?
Por ejemplo, en el caso de $n=3$, las expresiones $f(x_1, f(x_2, x_3))$ $f(x_1, g(x_2, x_3))$ son claramente distintas. Sin embargo, $f(f(x_2, x_1), x_3)$ es equivalente a la primera, y $f(g(x_3, x_2), x_1)$ es equivalente a la segunda.
Usando una simple búsqueda por fuerza bruta, los primeros términos de la secuencia de $(a_n)$ $$1, 2, 8, 52, \ldots$$ que corresponden a varias secuencias en OEIS.
Respuesta
¿Demasiados anuncios?
He aquí una relación de recurrencia para su problema, por lo que vale la pena. Como se ha mencionado en los comentarios, veo que estas expresiones como en la revisión de las combinaciones de dos operaciones, dicen suma y la multiplicación. Así, cada expresión es una suma de productos de sumas de productos (etc.) o de un producto de sumas de productos de sumas (etc.). Para cuantificar esto, vamos a $e_n$ el número de expresiones en $n$ variables que pueden estar hechos de suma y multiplicación y uno de cada variable; $s_n$ es la porción de la $e_n$ que son sumas de dinero (es decir, $p_1+\dots+p_k$ algunos $k$ donde cada una de las $p_i$ es un producto) y $p_n$ es la porción de la $e_n$ que son los productos (es decir, $s_1\times\dots\times s_k$ algunos $k$ donde cada una de las $s_i$ es una suma). A continuación, $e_1=s_1=p_1=1$, e $e_n=s_n+p_n$ por cada $n>1$, y por simetría $s_n=p_n$. Ahora imagine una suma de $k$ de los productos, donde el $i^{\text{th}}$ producto $n_i$ variables. Entonces, dado que cada variable se utiliza sólo una vez $n_1+\dots+n_k=n$. Las variables en estos productos pueden ser dispuestos en $\binom n{n_1,\dots,n_k}$ maneras. Por la conmutatividad y la asociatividad podemos organizar los productos en orden creciente de variables, por lo que el $n_1\le \dots\le n_k$. También a causa de la conmutatividad, los productos con el mismo número de variables que se pueden cambiar con cualquier permutación. Por lo tanto, vamos a $m_1<\dots< m_\ell$ ser la estrictamente creciente de la secuencia de las distintas $n_i$'s, y deje $d_i$ ser el de la multiplicidad que cada una de las $m_i$ aparece en $n_1,\dots, n_k$. Por eso, $d_1 m_1+\dots+d_\ell m_\ell=n$. Esto le da a la relación de recurrencia $$s_n=\sum_{k\ge 2}\sum\binom n{n_1\dots n_k}\frac{(p_{m_1})^{d_1}\cdots (p_{m_l})^{d_\ell}}{d_1!\cdots d_\ell!},$$ donde el interior de la suma de rangos de la $n_i,\ m_i,\ d_i$ variables como las descritas.
Esta relación de recurrencia está de acuerdo con los valores de $1,2,8,52$ que obtuvo por "fuerza bruta". (De hecho, tal vez usted hizo exactamente lo mismo para la obtención de estos valores). También predice 472 por $e_5$.
La siguiente pregunta es evidente si es posible obtener una solución explícita de la relación de recurrencia. En este punto, sinceramente, no lo sé. Sin embargo, parece que éste es el escenario donde la exponencial de la fórmula debe entrar en juego.
