Dado un número positivo n, cuantas tuplas $(a_1,...,a_k)$ están allí, que $a_1+..+a_k=n$ con dos restricciones adicionales

Question

Era el problema: Dado un entero positivo $n$, ¿cuántas tuplas $(a_1,...,a_k)$ de todos los números positivos están allí, que $a_1+a_2+...+a_k=n$. Y $0< a_1 \le a_2 \le a_3 \le...\le a_k$. También, $a_k-a_1$ es $0$ o $1$.

Aquí es lo que yo hice:

Para $n=1$, hay una forma en la $1=1$.

Para$n=2$, $2$ formas, $2=1+1,2=2$

Para$n=3$, $3$ formas, $3=1+1+1,3=1+2,3=3$

Para$n=4$, $4$ formas, $4=1+1+1+1,4=1+1+2,4=2+2,4=4$

Así que parece que hay $n$ tuplas que satisfacen las tres condiciones para cada una de las $n$. Pero no estoy seguro de cómo demostrarlo.

Answer 1

Esto también se puede hacer con una simple generación de función. Llame a la la cantidad que desee $T_n.$ primero escogemos el valor de $a_1$ y, a continuación, el las brechas entre valores sucesivos entre el $a_q$ cuales son cero o uno. Tendremos $1\le k\le n$ pero para $k=1$ solo hay uno posibilidad de modo que podemos suponer $2\le k\le n.$ obtenemos $a_1,$ que es positivo,

$$\frac{z}{1-z}$$

pero contribuye a todas las $k$ términos, así que hemos hecho en

$$\frac{z^k}{1-z^k}.$$

Combinamos esto con $k-1$ lagunas de cero o uno. La primera brecha contribuye a $k-1$ términos, la siguiente a $k-2$ y así sucesivamente. El uso de la variable $u$ a marcar las lagunas de este modo, obtener

$$\bbox[5px,border:2px solid #00A000]{ 1 + \sum_{k=2}^n \frac{z^k}{1-z^k} \prod_{q=1}^{k-1} \left(1+uz^{k-q}\right).}$$

Ahora, a partir de la restricción de que $a_k-a_1$ ser cero o uno sigue necesitamos el coeficiente de $[u^0]$ $[u^1].$ establecer $u=0$ para el primero y obtener

$$\sum_{k=2}^n \frac{z^k}{1-z^k}.$$

Podemos diferenciar y establecer $u=0$ para el segundo y obtener

$$\left.\sum_{k=2}^n \frac{z^k}{1-z^k} \prod_{q=1}^{k-1} \left(1+uz^{k-q}\right) \sum_{q=1}^{k-1} \frac{z^{k-q}}{1+uz^{k-q}}\right|_{u=0} \\ = \sum_{k=2}^n \frac{z^k}{1-z^k}\sum_{q=1}^{k-1} z^{k-q}.$$

De ello se deduce que el resultado deseado es dada por

$$\bbox[5px,border:2px solid #00A000]{ 1 + [z^n] \sum_{k=2}^n \frac{z^k}{1-z^k}\sum_{q=1}^{k} z^{k-q}.}$$

La evaluación de este principio nos obtener

$A$1 + [z^n] \sum_{k=2}^n \frac{z^{2k}}{1-z^k}\sum_{q=1}^{k} z^{-q} = 1 + [z^n] \sum_{k=2}^n \frac{z^{2k}}{1-z^k} \frac{1}{z} \sum_{q=0}^{k-1} z^{-q} \\ = 1 + [z^n] \sum_{k=2}^n \frac{z^{2k}}{1-z^k} \frac{1}{z} \frac{1-1/z^k}{1-1/z} = 1 + [z^n] \sum_{k=2}^n \frac{z^{2k}}{1-z^k} \frac{1-1/z^k}{z-1} \\ = 1 + [z^n] \sum_{k=2}^n \frac{z^k}{1-z^k} \frac{z^k-1}{z-1} = 1 - [z^n] \sum_{k=2}^n \frac{z^k}{z-1}.$$

Ahora podemos extender $k$ hasta el infinito, porque los términos de $k\gt n$ no contribuir a que el coeficiente de $[z^n],$ llegar

$A$1 + [z^n] \frac{1}{1-z} \sum_{k\ge 2} z^k = 1 + [z^n] \frac{z^2}{(1-z)^2} \\ = 1 + [z^{n-2}] \frac{1}{(1-z)^2} = 1 + {n-2+1\elegir 1}.$$

Esto produce que el resultado final

$$\bbox[5px,border:2px solid #00A000]{T_n = n.}$$

Yo creo que este cálculo es muy interesante, y tal vez diferente de lo que podría haberse esperado.

Answer 2

Cada solución es una tupla en orden creciente de los números enteros. También, $a_k=a_1$ o $a_k=a_1+1$. Por lo tanto, tenemos todo el $a_1$s al principio y al $a_1+1$s al final. Podemos decir que hay un $l$ instancias de $a_1$ e lo $k-l$ instancias de $a_1+1$. Ya que la suma de las tuplas es $n$, podemos encontrar: $$l*a_1+(k-l)*(a_1+1)=n$$ Simplificar el lado izquierdo: $$a_1k+k-l=n$$ Ahora, $l$ es el número de instancias de $a_1$ en la secuencia. Por lo tanto, $l$ al menos $1$ y en la mayoría de las $k$. Por lo tanto, $k-l$ al menos $0$ y en la mayoría de las $k-1$, lo $k-l$ es básicamente el resto de $n$ cuando se divide por $k$ $a_1$ es el cociente. Por lo tanto, por el Teorema de la División, sabemos que hay entero único de soluciones de $a_1$ $l$ de esta ecuación para cualquier $k$$n$.

Sin embargo, el problema dice que $a_1 > 0$, por lo que necesitamos excluir las soluciones donde $a_1=0$. Al $a_1=0$, obtenemos: $$0k+k-l=n \implies k-l=n$$ Desde $k-l$ es en la mayoría de las $k-1$, esto significa $n$ es en la mayoría de las $k-1$ e lo $n < k$. Por lo tanto, excluir todas las soluciones donde $k > n$.

También, obviamente, $k \geq 1$. Esto nos deja con las soluciones de $k \geq 1$$k \leq n$, por lo que hay $n$ soluciones.

Answer 3

La respuesta es $n$.

Dado $n$, usted necesita una prueba de que para cada una de las $k$ donde$k\leq n$, existe exactamente una tupla.

En primer lugar, usted puede prueba que para cada una de las $k$, existe al menos una tupla.

$n=kt+r$

donde $r<k$.

Hacer la tupla $(a_1,...,a_k)=(t,...,t)$. A continuación, añadir a la última $r$ componentes $1$ unidad para obtener una válida tupla.

En segundo lugar, usted necesita para demostrar que la construcción de la tupla es único, para cada una de las $k$$n$. Si hay otra tupla, de tal forma que sus elementos se agregan a $n$, entonces usted puede conseguir a partir de la primera construyó tupla, por el movimiento de las unidades entre los componentes. Pero, si se mueve una sola unidad, luego de destruir el orden creciente de los componentes.

Finalmente, usted sólo necesita saber cuántos posible $k$ que usted puede tener un número$n$,$n$.