¿De cuántas maneras puedes escribir un número n como una suma de 1s, 2s y 3s?

Question

Dado $n \in \mathbb{N}$ ¿de cuántas maneras distintas se puede escribir $n=a+2b+3c$ para $a,b,c \in \mathbb{N}$.

Tengo una idea, como si yo uso una 3-tupla para representar a $(a,b,c)$, me puede hacer una lista de todos ellos a través de dos funciones de $f((a,b,c)) = (a-2,b+1,c)$ e $g((a,b,c)) = (a-1,b-1,c+1)$. Que hace un bonito patrón que debe ser fácil de calcular, para cualquier n sin embargo estoy luchando por encontrar una verdadera ecuación que funciona cada vez. Ahora mismo tengo uno que funciona a veces ser; Deje $x = \left \lfloor{n/2}\right \rfloor $, $y = \left \lfloor{n/6}\right \rfloor $ e $z = x-y$. A continuación, la función de $f(n)$ es el recuento. $f(n) = 1+x+(c/2)(c+1)+bc-b(b+1)$. Sin embargo, yo sé que es malo.

EDITAR: Lo siento olvidé de agregar que f(n) debe ser una función de sólo n.

Answer 1

$f(n)$ satisface la recurrencia $$ f(n) = f(n-1)+f(n-2)-f(n-4)-f(n-5)+f(n-6)\etiqueta{$n\ge 1$} $$ Esto puede ser demostrado a partir del principio de inclusión, de exclusión, de manera similar a esta respuesta. Deje $E^n$ el conjunto de tripletas $(a,b,c)$ para que $a+2b+3c=n$, lo $f(n)=|E^n|$. Además, vamos a

• $E^n_1=\{(a,b,c)\in E^n\mid a\ge 1\}$
• $E^n_2=\{(a,b,c)\in E^n\mid b\ge 1\}$
• $E^n_3=\{(a,b,c)\in E^n\mid c\ge 1\}$

Utilizando el principio de inclusión, exclusión, puede mostrar para cualquier $n\ge 1$que $$ |E^n|=|E^n_1|+|E^n_2|+|E^n_3|-|E^n_1\cap E^n_2|-|E^n_1\cap E^n_3|-|E^n_2\cap E^n_3|+|E^n_1\cap E^n_2\cap E^n_3| $$ Además, usted puede mostrar a $|E^n_1|=|E^{n-1}|$, a través de la bijection $(a,b,c)\mapsto (a-1,b,c)$, e $|E^n_1\cap E^n_2|=E^{n-3}$ través $(a-1,b-2,c)$. Utilizando similares bijections, se obtiene la recurrencia anunciado anteriormente.

De todos modos, la solución del anterior lineal de recurrencia después de la determinación de la base de los casos los rendimientos $$ f(n)= \frac1{72}(6n^2+36n+9(-1)^n+16\cos(2\pi n/3) + 47) $$ Tengo este de Wolfram|Alpha.

Answer 2

Deje $f(n)$ el número de maneras de hacer que los $n$ como una suma de $1$s, $g(n)$ el número de maneras de hacer que los $n$ como una suma de $1$s y $2$s y $h(n)$ el número de maneras de hacer que los $n$ como una suma de $1$s, $2$s y $3$s.

Debe ser obvio que la $f(n) = 1$.

$g(0) = f(0) = 1$ e $g(1) = f(1) = 1$, ya que no habrá ninguna $2$s para estos pequeños números. Para $n \ge 2$, $g(n) = f(n) + g(n - 2) = 1 + g(n-2)$.

Para $n \lt 3$, $h(n) = g(n)$. Para $n \ge 3$, $h(n) = g(n) + h(n-3)$.

$$ h(n) h(n-3) = g(n)\\ g(n) g(n-2) = 1\\ h(n) h(n-3) - (h(n-2) - h(n-5)) = 1\\ h(n) h(n-2) - h(n-3) + h(n-5) = 1\\ h(n-1) - h(n-3) - h(n-4) + h(n-6) = 1\\ h(n) h(n-1) - h(n-2) - h(n-3) + h(n-3) + h(n-4) + h(n-5) - h(n-6) = 1 - 1 = 0\\ h(n) = h(n-1) + h(n-2) - h(n-4) - h(n-5) + h(n-6)\\ $$

Así que ahora tenemos una recurrencia lineal. Para la serie de recurrencia lineal, $F(n) = F(n-1) + F(n-2)$, que tenga un polinomio de $x^2 - x - 1$, y que el polinomio tiene raíces $\frac{1 \pm \sqrt{5}}{2}$, y la forma cerrada de la serie de Fibonacci se basa en una combinación lineal de exponenciales de esas raíces, $Fib(n) = k_1 \left(\frac{1 + \sqrt{5}}{2}\right)^n + k_2\left(\frac{1 - \sqrt{5}}{2}\right)^n$.

Por lo que el polinomio asociado con la $h(n)$ recurrencia es $x^6 - x^5 - x^4 + x^2 + x - 1$. Que los factores de a $ (x + \frac12 + \frac{\sqrt{3}}{2}i)(x + \frac12 - \frac{\sqrt{3}}{2}i) (x - 1)^3 (x + 1)$ Que se traduce en una forma cerrada expresión de la forma $(k_1 + k_2 n + k_3 n^2)(1)^n + k_4(-1)^n + k_5(-\frac12 - \frac{\sqrt{3}}{2}i)^n + k_6(-\frac12 + \frac{\sqrt{3}}{2}i)^n$.