La motivación
El siguiente texto es de Problema 606 de Proyecto de Euler :
Un gozinta de la cadena de $n$ es una secuencia $\{1,a,b,...,n\}$ donde cada elemento correctamente divide de la siguiente. Por ejemplo, hay ocho distintos gozinta cadenas para $12$: $$\{1,12\}, \{1,2,12\}, \{1,2,4,12\}, \{1,2,6,12\}, \{1,3,12\}, \{1,3,6,12\}, \{1,4,12\},\{1,6,12\}.$$ Deje $S(n)$ ser la suma de todos los números, $k$, no superando $n$, lo que ha $252$ distintos gozinta cadenas. Se le da $S(106)=8462952$$S(1012)=623291998881978$. Encontrar $S(1036)$, dando los últimos nueve dígitos de su respuesta.
Dado un número $n\in \mathbb N$ podemos escribir su descomposición en factores primos $n=p_1^{k_1}\cdot\ldots\cdot p_m^{k_m}$.
Cada gozinta de la cadena de $(z_1=1,z_1,\ldots,z_{r-1},z_r=n)$ de la longitud de la $r$ $n$ puede ser construida como $$\begin{align} z_r=& p_1^{k_1}\cdot\ldots\cdot p_m^{k_m}\\ z_{r-1}= & p_1^{k_1-t^{(r-1)}_{1}}\cdot\ldots\cdot p_m^{k_m-t^{(r-1)}_{m}}\\ &\vdots\\ z_1 = & p_1^{k_1-\sum_{j=1}^{r-1}t^{(j)}_1}\cdot\ldots\cdot p_m^{k_m-\sum_{j=1}^{r-1}t^{(j)}_m}\\ z_0 =&p_1^{k_1-\sum_{j=0}^{r-1}t^{(j)}_1}\cdot\ldots\cdot p_m^{k_m-\sum_{j=0}^{r-1}t^{(j)}_m}=1 \end{align} $$ a través de la recursión hacia atrás $$z_{s-1}=\frac{z_s}{p_1^{t_1^{(s-1)}}\cdot\ldots\cdot p_m^{t^{(s-1)}_m}}$$ con las tuplas $(t_1^{(0)},\ldots,t_m^{(0)}),\ldots,(t_1^{(r-1)},\ldots,t_m^{(r-1)})$ la satisfacción de las dos restricciones
$$ \begin{align} \sum_{j=0}^{r-1}t_\nu^{(j)}&=k_{\nu} && \forall \nu=1,\ldots, m\tag{1}\\ (t_1^{(j)},\ldots,t_m^{(j)})&\neq(0,\ldots,0) && \forall j=1,\ldots r\tag{2} \end{align}$$
El Problema
Me gustaría entender más acerca de la función de $\alpha((k_1,\ldots,k_m))$ que se asocia el número de gozinta cadenas para $n$ a las multiplicidades de $n$'s de los factores primos.
Observación 1: se podría intentar enumerar las tuplas de satisfacciones $(1),(2)$. Por ejemplo, si uno supone $m=1$, (es decir,$n=p^k$) el problema es equivalente a preguntar cómo muchos ordenó particiones de $k$ existen. Es bien sabido que ese número es $2^{k-1}$. A continuación,$\alpha(k)=2^{k-1}$$k>0$. El problema de la enumeración de las tuplas de satisfacciones $(1),(2)$ podría ser visto como una generalización de entero de partición a $m$-tuplas.
Observación 2: El problema podría ser modelados de forma combinatoria de la siguiente manera. Supongamos que tenemos $m$ contenedores con $k_1,\ldots, k_m$ bolas. En cada una de nuestras $r-1$ convierte debemos extraer al menos una bola. En la última vuelta ( $r-1$ ), le han quitado todas las bolas de las bandejas. En cuántas formas diferentes podemos hacer esto sin la fijación de la duración del juego?
Pregunta
Hay un conocido respuesta en la literatura para el mencionado combinatoria problema? Yo esperaría que sea
- Una referencia siguiendo la idea de la Observación 1, esencialmente correlacionar el resultado para ordenó particiones de $m$-tuplas. No tengo conocimiento de tales resultados y he sido capaz de encontrar los resultados en relación con ordenó particiones de enteros.
- Un enfoque combinatorio siguiente Comentario 2.
Probablemente he utilizado no estándar de notación como no estoy familiarizado con el tema.
Nota: he publicado esta pregunta, aunque se refiere a un Proyecto de Euler pregunta siguiendo la orientación de esta meta respuesta.
