Escritura de números como una suma de $2$ ' s y $3$ ' s

Question

Es allí una manera de contar el número de maneras en que un entero positivo $n$, puede ser escrita como una suma de dos y tres? ¿Hay algún patrón? Re-organización de los doses y treses son distintos..(tiene sentido verdad?? o no deberían ser distintos)

Me tropecé apon esta pregunta de un amigo que quería ponerme a prueba, y, francamente, no puedo entenderlo.

Tengo otra vuelta de tuerca en la pregunta que yo podría necesitar un poco de ayuda con: ¿Qué números tienen el número de maneras para que un entero positivo $n$ a ser escrita como una suma de $2$'s y $3$'s = $n$?

Answer 1

Me pueden ayudar a encontrar a una generación de función, pero a juzgar por mis primeras impresiones esto no es un problema sencillo.

Consideremos una infinita suma. Tratamos $x$ como un "dummy" de la variable, y considerar sólo el coeficiente de en frente de esta.

$$\sum_{n=0}^\infty s(n)x^n$$

Donde $s(n)$ denota el valor de la cantidad de formas para crear un número como una suma de 3 y 2. Entonces nos encontramos con que podemos reducir este por las propiedades de las series geométricas infinitas. Si usted es un purista de análisis, seguir adelante y asumir la $|x|<1$. Podemos recrear esta suma como un infinito producto (este concepto de la generación de la función fue una gran idea por Euler cuando él hizo su trabajo inicial sobre la teoría de particiones).

$$\sum_{n=0}^\infty s(n)x^n = \frac{1}{(1-x^{2})(1-x^{3})}$$

Si usted ampliado esta serie, el coeficiente delante de $x^n$ sería el valor que estás buscando, para algún entero $n$.

Los principios detrás de esto no es demasiado complicado, pero me doy cuenta de que, probablemente, esto no tiene sentido ya que yo no completamente formalizar este. Sin embargo, la expansión de esta serie, te puedo dar algunos valores. Usted dijo que usted utiliza un método de fuerza bruta sobre esto, así, se puede comprobar con mis valores.

$s(2) = 1$ (obvio) . . . $s(16)$ = 3 . . . $s(94)$ = 16

Si desea comprobar los valores por ti mismo, compruebe esto hacia fuera y ampliar la serie de Taylor.

Answer 2

Deje $c_k$ el número de maneras en que $k$ puede ser escrita como una suma de dos y tres. Si reorderings no son distintas, el problema es trivial. Por inspección, $c_0 = 1, c_1 = 0, c_2 = c_3 = c_4 = c_5 = 1$. Después de eso, el patrón se repite, pero cada vez más por $1$ con cada grupo de $6$. Es decir,

$$ c_k = \lfloor k/6 \rfloor + c_{k \bmod 6}, \qquad k \geq 6 $$

Si el orden importa, el problema es más complicado. No estoy seguro de que hay una forma cerrada de solución para eso. Voy a pensar que algunos más.

ETA: sospecho que hay una forma cerrada. Es especificado por la relación de recurrencia

$$ c_k = c_{k-3} + c_{k-2} $$

con $c_0 = 1, c_1 = 0, c_2 = 1$. En otras palabras, es como la serie de Fibonacci, sólo hasta llegar de nuevo un paso más allá. La justificación de esta recursividad es que la fabricación de cualquier suma $k$ puede ser alcanzada sólo por alcanzar, en primer lugar, bien $k-3$ o $k-2$, y, a continuación, la adición de tres y dos, respectivamente. Todas las secuencias son distintos, por lo que no hay recuento de que preocuparse.

Trabajando en la forma cerrada ahora.

ETA 2: Ooh, es complicado. No es seguro que esto es lo que su amigo tenía en mente. El cúbicos correspondientes a la recurrencia, $r^3 - r - 1 = 0$, tiene algunos desordenado raíces, dos complejos y uno real. El comportamiento a largo plazo es (como cabría esperar) dominado por la raíz real, pero incluso ese valor es desordenado:

$$ r_1 = \sqrt[3]{\frac{9-\sqrt{69}}{18}} + \sqrt[3]{\frac{9+\sqrt{69}}{18}} \doteq 1.32472 $$

En el límite de $k$ crece sin límite, $c_k \to \alpha_1 r_1^k$ donde $\alpha_1$ es una constante. Probablemente converge muy rápidamente.

ETA 3: Las otras dos raíces complejas, están dadas por

$$ r_2 = - \frac{1-i\sqrt{3}}{2} \sqrt[3]{\frac{9-\sqrt{69}}{18}} - \frac{1+\sqrt{3}}{2} \sqrt[3]{\frac{9+\sqrt{69}}{18}} $$

$$ r_3 = - \frac{1+\sqrt{3}}{2} \sqrt[3]{\frac{9-\sqrt{69}}{18}} - \frac{1-i\sqrt{3}}{2} \sqrt[3]{\frac{9+\sqrt{69}}{18}} $$

Son complejos conjugados. La expresión para $c_k$ es de la forma

$$ c_k = \alpha_1 r_1^k + \alpha_2 r_2^k + \alpha_3 r_3^k $$

Dados los valores iniciales de las $k = 0, 1, 2$, sabemos que

$$ \alpha_1 + \alpha_2 + \alpha_3 = 1 $$ $$ \alpha_1 r_1 + \alpha_2 r_2 + \alpha_3 r_3 = 0 $$ $$ \alpha_1 r_1^2 + \alpha_2 r_2^2 + \alpha_3 r_3^2 = 1 $$

ETA 4: hice algunas figurings en los coeficientes $\alpha_i$. Son muy desordenado. Sus valores son aproximadamente $\alpha_1 \doteq 0.41150, \alpha_2 \doteq 0.29425-0.13811i, \alpha_3 \doteq 0.29425+0.13811i$.

Answer 3

Empezaría a mirar cuántos $a$ y $b$ satisfacer

$$2a + 3b = N$$

La forma más rápida de hacer esto es marcando incluso es cada vez mayor $N - 3b$ $b$.

Answer 4

Sin contar el fin de ($3+3+2$$3+2+3$ son contados una sola vez)

En este caso la pregunta es ¿cuántos pares de no enteros negativos $(x,y)$ están allí, que $2x+3y=N$ y en este caso tenemos:

• Si $N=2t$, entonces el número de soluciones es $\left\lfloor\frac{t}{3} \right\rfloor$
• Si $N=2t+1$, entonces el número de soluciones es $\left\lfloor\frac{t-1}{3} \right\rfloor$

En general, el número de no negativo soluciones de $ax+by=N$ es $\left\lfloor\frac{N}{ab} \right\rfloor$ o $\left\lfloor\frac{N}{ab} \right\rfloor-1$

Recuento de órdenes ($3+3+2$$3+2+3$ se cuentan como dos veces, se consideran distintas )

Yo no conozco a ninguna de las fórmulas para esto, pero se puede escribir como una suma: $$\sum_{2x+3y=N}{x+y\choose x} $$