Contar Diferentes formas de sumar números

Question

Busco información sobre el recuento de las posibles formas de sumar números. Por ejemplo, supongamos que se puede utilizar 1,2 y 4. ¿Cuántas combinaciones posibles hay para crear cualquier número?

Por ejemplo,

Para 1: $$ 1$$

Para 2: $$ 2, 1+1$$

Para 3: $$2+1, 1+1+1$$

Para 4: $$4, 2+2, 1+1+2$$

Para 5: $$4+1, 2+2+1, 2+1+1+1, 1+1+1+1+1$$

Esto es para una pregunta que estoy trabajando en un para una clase de álgebra lineal de primer año. Acabamos de ser introducidos a la escritura de pruebas y el razonamiento lógico, etc. Los números que se nos dan son 1,2 y 3. Sin embargo, estoy tratando de obtener información de fondo en primer lugar para que pueda tratar de resolver por mí mismo. He estudiado estadística, así que conozco las combinaciones, pero no de esta forma.

Me doy cuenta de que para cada número $n$ existe una combinación $\sum_{1}^{n}1$ que es igual al número. He hecho algunas tablas con distintas combinaciones para los números del 1 al 9. Estoy probando diferentes formas de organizar las diferentes combinaciones. Agradecería cualquier ayuda.

Answer 1

Sea $a_n$ sea el número de particiones de $n$ con sumandos sólo en $\{1,2,4\}$ , $b_n$ el número de particiones con sumandos en $\{1,2\}$ . Entonces tenemos $$b_n = \left\lfloor\frac n2\right\rfloor+1$$ porque podemos tomar entre $0$ y $\left\lfloor\frac n2\right\rfloor$ doses y rellenar con unos. Entonces tenemos $$a_n=\sum_{k=0}^{\left\lfloor\frac n4\right\rfloor}b_n.$$ No voy a dar una fórmula explícita, pero se puede adivinar que $a_n$ es aproximadamente cuadrática.

También puede encontrar $a_n$ como coeficiente de $x^n$ en la expansión en serie de potencias de $$ \frac1{(1-x)(1-x^2)(1-x^4)}.$$

Answer 2

Una pista: toma cualquier número y empieza por la combinación "más pequeña" (la que utilice el menor número posible de números). Por ejemplo, 5 = 3 + 2.

Answer 3

Sea T(n) el número de formas de crear la suma. A menudo se puede generar una recurrencia que funcione.

Supongamos que tiene la notación $T_r(n)$ para el caso en que el mayor componente de la suma sea $r$ , entonces o la suma tiene un 4, o el número mayor es 2, o es 1 (que es sólo un caso), así que: $$T(n)=T(n-4)+T_2(n-2)+1$$ Esto debería permitirle hacer algunos progresos razonables.