¿Cuántas veces se $k$ ocurren en la composición de $n$?

Question

¿Cuántas veces el número de $k$ ocurren en la composición de $n$?

Composición de Entero

En resumen, la diferencia entre la partición de un número entero y la composición es el orden de los números. En la partición, no importa el orden, mientras que, en la composición, lo hace. Es por eso que las Particiones son a veces llamado como ordenó Composiciones.

Ejemplo: $k$ = $1$ & $n$ = $5$

La composición de 5 son:

$5$

$4 + 1$

$3 + 2$

$3 + 1 + 1$

$2 + 3$

$2 + 2 + 1$

$2 + 1 + 2$

$2 + 1 + 1 + 1$

$1 + 4$

$1 + 3 + 1$

$1 + 2 + 2$

$1 + 2 + 1 + 1$

$1 + 1 + 3$

$1 + 1 + 2 + 1$

$1 + 1 + 1 + 2$

$1 + 1 + 1 + 1 + 1$

En todos los $1$ se produce $28$ veces en la composición de $5$

Del mismo modo hay alguna relación entre el $k$ $n$ para todos los $n \geq 0$ & $k \leq n$

Answer 1

Supongamos que $k$ (que $0<k<n$) se produce en la posición p en una composición de $n$: $$\ldots+k+\ldots$$ por que me refiero a que todo a su izquierda es una composición de $p$, y de todo lo que a su derecho es una composición de $n-p-k$.

Si $p>0$$n-p-k>0$, $2^{p-1}$ composiciones de $p$ $2^{n-p-k-1}$ composiciones de $n-p-k$, por lo tanto no se $2^{p-1}\cdot2^{n-p-k-1}=2^{n-k-2}$ posibilidades para el resto de la composición de $n$. Si $p=0$ o $n-p-k=0$, $2^{n-k-1}$ posibilidades para el resto de la composición de $n$.

Suma más de $p$, usted encontrará que para $k<n$ la respuesta es: $$2\cdot2^{n-k-1}+\sum_{p=1}^{n-k-1}2^{n-k-2}=(n-k+3)\cdot2^{n-k-2}$$

Answer 2

En primer lugar, para $k=1$. Deje $a(n)$ ser el número de veces que $1$ aparece en las composiciones de $n+1$ (según la OEIS de indexación). A continuación, una composición de $n+1$ termina en $1,2,3,\dots$. Las composiciones que termina en $1$ contribuir $a(n-1)+2^{n-1}$ (ya que hay que $2^{n-1}$ total composiciones de $n$). Las composiciones que termina en $j$, $j\geq 2$, contribuir $a(n-j)$; así llegamos a la recurrencia $$ a(n)=2^{n-1}+\sum_{j=0}^{n-1} (j), $$ con $a(0)=1$. Un sencillo de inducción de la prueba (sólo manipular un par de sumas) muestra $a(n)=(n+3)2^{n-2}$$n\geq1$.

Para un general $k$, la recursividad es esencialmente el mismo, pero con diferentes condiciones iniciales. Deje $a_k(n)$ ser el número de veces que $k$ aparece en las composiciones de $n+1$. Entonces claramente $a_j=0$$j<k-1$$a_{k-1}=1$. Ahora como antes de condición de una composición basada en su última carta. Tenemos $$ a_k(n)=2^{n-k-1}+\sum_{j=0}^{n-1}a_k(j)=2^{n-k-1}+\sum_{j=k-1}^{n-1}a_k(j) $$ Voy a dejar los detalles, pero a partir de la inspección se puede ver a partir de un cambio de variables y la inducción que $$a_k(n)=a_1(n-k+1)=(n-k+4)2^{n-k-1}$$

Answer 3

Es de forma recursiva definida. Piense en ello, si k sucede en la composición de n, entonces fue etiquetado en una composición de n-k. Esto implica, que hay, al menos, como muchos k en las composiciones de n, ya que hay composiciones de n-k). así se puede resumir el número de tales composiciones de los anteriores números positivos en la progresión aritmética $kx+(n \bmod k)$. Así que, para que k=1, n=5 ejemplo tenemos:

composiciones de 1:

$$\color{red}1$$

para 2 tenemos : $$\color{rojo} 1,\color {verde}1\\ \color{verde}2 $$ para 3 tenemos: $$\color{verde}{1,1},\color{blue}1\\ \color{verde}2,\color{blue}1\\ \color{blue}3$$

para 4 tenemos: $$\color{blue}{1,1,1},\color{color púrpura}1\\ \color{blue}{2,1},\color{color púrpura}1\\ \color{blue}{3},\color{color púrpura}1\\\color{color púrpura}{2,2}\\\color{color púrpura}4$$

y para 5 tenemos:

$$\color{color púrpura}{1,1,1,1},\color{cal}1\\ \color{color púrpura}{2,1,1},\color{cal}1\\ \color{purple}{3,1},\color{lime}1\\\color{purple}{2,2},\color{lime}1\\\color{purple}4,\color{lime}1\\\color{lime}5$$

Por lo tanto, vamos a $f(n,k)$ a ser el número de tales composiciones para el valor de n, y sea g(v) el número de composiciones de v total:

$$f(n,k)=\sum_{i\gt0,i\equiv n\bmod k}^n g(v) +f(n\bmod k,k)$$

Answer 4

La generación de la función aquí es

$$G(z, u) = \sum_{q\ge 1} \left(uz^k - z^k + \frac{z}{1-z}\right)^q.$$

Entonces tenemos que

$$\left.\frac{\partial}{\partial u} G(z, u) \right|_{u=1} \\ = \left. \sum_{q\ge 1} q \left(uz^k - z^k + \frac{z}{1-z}\right)^{p-1} z^k\right|_{u=1} = z^k \sum_{q\ge 1} p \left(\frac{z}{1-z}\right)^{p-1} \\ = z^k \frac{1}{(1-z/(1-z))^2} = z^k \frac{1-2z+z^2}{(1-2z)^2}.$$

La extracción de los coeficientes encontramos por $n\ge k+2$

$$[z^{n-k}] \frac{1}{(1-2z)^2} - 2[z^{n-k-1}] \frac{1}{(1-2z)^2} + [z^{n-k-2}] \frac{1}{(1-2z)^2} \\ = 2^{n-k} (n-k+1) - 2^{n-k} (n-k) + 2^{n-k-2} (n-k-1) \\ = 2^{n-k} + 2^{n-k-2} (n-k-1) = 2^{n-k-2} (n-k+3).$$

Obtenemos $n=k+1$

$$2^{n-k} (n-k+1) - 2^{n-k} (n-k) = 2$$

que corresponde a $(1,k)$ $(k,1)$ y para $n=k$

$$2^{n-k} (n-k+1) = 1.$$

Estos sólo dependen de la $n-k$ como se señaló en los comentarios.