Número de formas de escritura $n$ como suma

Question

Tengo una pregunta general sobre números:

¿De cuántas maneras podemos escribimos $n$ como la suma de lo números $1$, $2$ y $3$?

Sé que empezamos con las siguientes funciones: $$\frac{1}{1-z} = 1+z+z^2+ \dots$$ $$\frac{1}{1-z^2} = 1+z^2+ z^4+ z^6 + \dots$$ $% $ $\frac{1}{1-z^3} = 1+ z^3+ z^{6}+ z^{9} + \dots$

¿Multiplicando estos juntos conseguimos $$\sum C(n) z^n = \frac{1}{(1-z)(1-z^2)(1-z^3)}$$ where $C # (n) $ is our answer. In other words, by multiplying out the polynomials and looking at the coefficients, I can verify that I get the answer. But how do I know that this gives me the answer? How would I get an explicit formula for $C (n) $? I think I have to do something with partial fractions. So $$\frac{1}{(1-z)(1-z^2)(1-z^3)} = \frac{A}{1-z} + \frac{B}{1-z^2}+ \frac{C}{1-z^3}$$ and we have to solve for $A $, $B $ and $C$?

Answer 1

Aquí es una derivación de una realidad explícita fórmula para $C(n)$, lo que he llamado por debajo de $p_{123}(n)$.

Deje $p_{23}(n)$ denotar el número de particiones de $n$ a $2$s y $3$s. Si usted utiliza $k$ $2$s, entonces usted debe hacer hasta $n-2k$ $3$s, por lo que debemos tener $n - 2k \equiv 0 \pmod 3$, y también se $2k\le n$. Así,

• Si $n \equiv 0 \pmod 3$,$k \equiv 0 \pmod 3$, por lo que cada $k = 3l$ $l=0$ $l=\lfloor n/6 \rfloor$obras.
  Si $n = 6m$ o $n=6m + 3$$p_{23}(n) = m+1$.

• Si $n \equiv 1 \pmod 3$,$k \equiv 2 \pmod 3$, por lo que cada $k = 3l+2$ $l=0$ $l=\lfloor (n-4)/6 \rfloor$obras.
  Si $n = 6m+1$ $p_{23}(n) = m$ e si $n=6m+4$$p_{23}(n) = m+1$.

• Si $n \equiv 2 \pmod 3$,$k \equiv 1 \mod 3$, por lo que cada $k = 3l+1$ $l=0$ $\lfloor (n-2)/6 \rfloor$obras.
  Si $n = 6m+2$ o $n=6m+5$$p_{23}(n) = m+1$.

Así que ahora tenemos una forma cerrada de expresión para $p_{23}(n)$.

Deje $p_{123}(n)$ denotar el número de maneras de escribir $n$ como una suma de $1$s, $2$s y $3$s. Entonces, sumando el número de $1$s utilizamos, $$ p_{123}(n) = \sum_{i=0}^{n} p_{23}(n-i) = \sum_{i=0}^{n} p_{23}(i).$$

Ahora la suma de $p_{23}(i)$ es fácil de calcular para cada consecutivos manojo de 6 números: $$p_{23}(6r) + p_{23}(6r+1) + p_{23}(6r+2) + p_{23}(6r+3) + p_{23}(6r+4) + p_{23}(6r+5)$$ $$ = (r+1) + r + (r+1) + (r+1) + (r+1) + (r+1)$$ $$ = 6r + 5 $$

Así que si $\lfloor n/6 \rfloor = m$, luego

$$\begin{align} p_{123}(n) &= \sum_{i=0}^{n} p_{23}(i) \\ &= \sum_{i=0}^{6m-1} p_{23}(i) + \sum_{i=6m}^{n} p_{23}(i)\\ &= \sum_{r=0}^{m-1} (6r+5) + \sum_{i=6m}^{n} p_{23}(i) \\ &= 6\frac{(m-1)m}{2} + 5m + \sum_{i=6m}^{n} p_{23}(i) \\ &= 3m^2 + 2m + \sum_{i=6m}^{n} p_{23}(i) \end{align}$$

Específicamente,

• Si $n = 6m$ $p_{123}(n) = (3m^2 + 2m) + (m+1) = 3m^2 + 3m + 1$

• Si $n = 6m+1$ $p_{123}(n) = (3m^2 + 3m + 1) + m = 3m^2 + 4m + 1$

• Si $n = 6m+2$ $p_{123}(n) = (3m^2 + 4m + 1) + (m+1) = 3m^2 + 5m + 2$

• Si $n = 6m+3$ $p_{123}(n) = (3m^2 + 5m + 2) + (m+1) = 3m^2 + 6m + 3$

• Si $n = 6m+4$ $p_{123}(n) = (3m^2 + 6m + 3) + (m+1) = 3m^2 + 7m + 4$

• Si $n = 6m+5$ $p_{123}(n) = (3m^2 + 7m + 4) + (m+1) = 3m^2 + 8m + 5.$

Esto puede ser escrito como $\frac{n^2}{12} + \frac{n}{2} + c$ donde $c$ es $1$, $\frac5{12}$, $\frac23$, $\frac34$, $\frac23$, o $\frac5{12}$ dependiendo de si $n$ modulo $6$ es $0$, $1$, $2$, $3$, $4$ o $5$ respectivamente.

---

Aunque todo esto parece muy ad hoc, creo que puede ser generalizado a cualquier conjunto general $\{a_1, a_2, \dots, a_k\}$. Usted todavía tiene que tomar de los casos y evaluar las sumas acerca de $k$ a veces, y obtendrá un polinomio de grado $k-1$, y (supongo) en la mayoría de las $\mathrm{lcm}(a_1, \dots, a_k)$ de los casos. No creo que esto sea necesariamente messier hacer a mano que en realidad llevar a cabo las funciones de generación -> fracciones parciales -> ... enfoque de finalización.

Answer 2

Leer cualquier libro en la generación de funciones de entender el porqué $1/(1-z)(1-z^2)(1-z^3)$ es la correcta generación de la función.

La fracción parcial de descomposición es más complicado de lo que usted describe. Primero tenemos que encontrar todas las raíces en el denominador y sus multiplicidades. Estas son las $1$ (multiplicidad $3$), $-1$ y $\frac{1}{2} \pm \frac{\sqrt{3}}{2} i$ (cada uno que aparece con multiplicidad $1$). Por lo tanto, la fracción parcial de descomposición es de la forma $$ \frac{A}{1-z} + \frac{B}{(1-z)^2} + \frac{C}{(1-z)^3} + \frac{D}{1+z} + \frac{E}{1 + z + z^2}. $$ El último término incorpora tanto las raíces de las $\frac{1}{2} \pm \frac{\sqrt{3}}{2} i$. Una vez que encuentres $A,B,C,D,E$, usted necesita para encontrar las fórmulas para que todas estas funciones de generación, y, a continuación, usted obtendrá una fórmula para $C(n)$.

Answer 3

Para la primera parte de la pregunta: Como Yuval señala, es típico el uso de funciones de generación, se supone que usted ha leído acerca de ellos para entender por qué $C(n)$ puede ser expresado de esa manera.

Una (ligeramente marginales) forma de verlo, en caso de que usted está familiarizado con discretos (secuencias de señales), circunvoluciones y transformadas de Fourier:

Decir $C_1(n)$ nos da, para cada una de las $n$ el número de formas de expresar el número de $n$ como una suma de unos; y $C_2(n)$ de la misma, como una suma de dos en dos.

Dicen que queremos calcular $C_{12}(n)$, el número de formas de expresar el número de $n$ como una suma de 1 y 2. Podemos partición $n = n_1 + n_2$, $n_1$ la suma de 1, etc; para que la partición en particular, el número total de maneras tendría que ser $C_1(n_1) C_2(n_2)$. Pero hay que contar todas las posibles particiones, por lo que

$$C_{12}(n) = \sum_{n_1+n_2=n} C_1(n_1) C_2(n_2) = \sum_{n_1=0}^n C_1(n_1) C_2(n-n_1) $$

Usted puede reconocer esta convolución de las secuencias, y recordar que una de convolución se traduce como producto de la transformada de Fourier de dominio (o la transformada de Laplace, o la transformada en Z - básicamente el mismo que el de generación de función). Pero $C_1(n)$ $C_2(n)$ son fáciles de encontrar, así como sus funciones de generación, por lo que también es fácil averiguar la generación de la función de $C_{12}$, como su producto. Y hay que ir.

Answer 4

Denotar por $N_3=\{1,2,3\}\,$, entonces su pregunta puede reformularse:

Encontrar el número de particiones de un número natural n en piezas sobre el conjunto de $N_3$ ese número se denota

$p(n,N_3)$, $n=6k+l$, donde $ k\in \{0,1,2,...\}$,e $ l\in \{0,1,2,3,4,5\}\,$

El uso de las recurrencias (sin funciones de generación) me parece que la solución exacta es.

[1] $p(6k,N_3)=3k^2+3k+1$

[2] $p(6k+1,N_3)=3k^2+4k+1$

[3] $p(6k+2,N_3)=3k^2+5k+2$

[4] $p(6k+3,N_3)=3k^2+6k+3$

[5] $p(6k+4,N_3)=3k^2+7k+4$

[6] $p(6k+5,N_3)=3k^2+8k+5$

Para explicar cada fórmula se necesita mucha introducción

ejemplo: $p(10,N_3)=14$ porque

[1,1,1,1,1,1,1,1,1,1]

[1,1,1,1,1,1,1,1,2]

[1,1,1,1,1,1,1,3]

[1,1,1,1,1,1,2,2]

[1,1,1,1,1,2,3]

[1,1,1,1,2,2,2]

[1,1,2,2,2,2]

[1,1,1,1,3,3]

[1,1,1,2,2,3]

[1,1,2,2,2,2]

[1,2,2,2,3]

[2,2,2,2,2]

[1,3,3,3]

[2,2,3,3]

Desde nuestras fórmulas que hemos

$p(10,N_3)=p(6\times 1+4)=3\times 1^2+7\times 1+4=14$ no $k=1$

Answer 5

Usted puede escribir un relatividad fórmula explícita para $C(n)$. Primero de todo, escribir

$$ \frac{1}{1-z}=1+z+z^2+\cdots =\sum _{n=0}^\infty a_nz^n $$ $$ \frac{1}{1-z^2}=1+z^2+z^4+\cdots =\sum _{n=0}^\infty b_nz^n $$ $$ \frac{1}{1-z^3}=1+z^3+z^4+\cdots =\sum _{n=0}^\infty c_nz^n. $$

Vemos, entonces, que $$ C(n)=\sum _{i+j+k=n}a_ib_jc_kz $$

Por lo tanto, se suma sobre todos los aspectos positivos maneras de agregar $i$, $j$, y $k$, para obtener el $n$. Sin embargo, $b_j$ es distinto de cero iff $j$ es un múltiplo de a $2$, en cuyo caso $b_j=1$, y similiary $c_k$ es distinto de cero iff $k$ es un múltiplo de a $3$, en cuyo caso $c_k=1$. De ello se desprende que el plazo $a_ib_jc_k$ es distinto de cero, en cuyo caso se devuelve sólo $1$, iff $j$ es un múltiplo de a $2$ $k$ es un múltiplo de a $3$, por lo que el $n=i+j+k$ es una suma de $i$, $j$ dos, y $k$ grupos de tres. Se puede comprobar que, dada una descomposición de la $n$ a $i$, $j$ dos, y $k$ tres, existe un término correspondiente en la anterior suma que evaulates a $1$, y por el contrario, cada término corresponde a exactamente un ejemplo de la descomposición. Por lo tanto, usted está, de hecho, sumar una $1$ para cada uno posiblemente forma de escribir $n$ como una suma de unos, dos, y tres, y, por tanto, $C(n)$ es el resultado deseado.

Espero que ayude. Yo creo que puede ser un poco confuso la primera vez que lo lea. Déjeme saber si usted tiene alguna pregunta acerca de lo que significaba.