Llenar una bolsa con frutas de cuatro tipos, con las limitaciones

Question

He aquí una diabólica problema de matemáticas que he encontrado.

De cuántas maneras podemos llenar una bolsa con n frutas sujeción a las siguientes limitaciones?

• El número de manzanas debe ser par.

• El número de plátanos debe ser un múltiplo de 5.

• No puede haber más de cuatro naranjas.

• No puede haber más de una pera.

Este problema es puramente para fines recreativos, pero yo prefiero ver una solución que consiste en "pura" de la cuenta, y no la generación de funciones.

Answer 1

He aquí un tedioso 'solución por contar'.

Deje $S_{op}(n)$ denotar el número de soluciones para el problema original. Deje $S_o(n)$ denotar la solución al problema, excepto que no había peras están incluidos en la bolsa. Deje $S(n)$ denotar la solución al problema con ninguna peras o naranjas en la bolsa, es decir, $S(n)$ es el número de número entero no negativo soluciones de $(a,b)$ a de la ecuación $$2 a + 5 b = n $$

Observe que $$S_{op}(n) = S_o(n) + S_{o}(n-1)$$, as we count in the first summand how many ways there are to bag exactly $n$ fruits with no pears, and in the second summand we count how many ways there are to bag $n-1$ fruits with no pears, it being implicit that we intend to sneak a pear in afterwards to make a full $$n.

En una vena similar, $$ S_o(n) = S(n) + S(n-1) + \cdots + S(n-4) $$ Al hacerlo, hemos demostrado $$ S_{op}(n) = S(n) + 2 \sum_{k = 1}^4 S(n - k) + S(n-5) $$ donde, para hacer la fórmula de la verdad en todos los casos (por pequeño $n$), adoptamos la convención de $S(n) = 0$$n = 1,0,-1,\cdots$.

Contamos $S(n)$; deduje que tenemos $$ S(n) = \begin{cases} \left\lfloor \frac{n}{5} \right\rfloor & n \text{ odd} \\ \left\lfloor \frac{n}{5} \right\rfloor + 1 & n \text{ even} \end{casos} $$ Poniendo todo esto junto le da una solución para el problema original $S_{op}(n)$.

Answer 2

Queremos contar el número de soluciones en enteros de

$2 x_1 + 5 x_2 + x_3 + x_4 = n$ sujeto a $x_i \ge 0$ para todos los $i$, $x_3 \le 4$ y $ x_4 \le 1$.

Según lo sugerido por @oldrinb, este problema tiene una solución elegante a través de la generación de funciones. Deje $a_n$ el número de soluciones, y definir $f(x) = \sum_{n=0}^{\infty} a_n x^n$. A continuación, "claramente" tenemos

$f(x) = (1+x^2+x^4+\dots) (1+x^5+x^{10}+\dots) (1+x+x^2+x^3+x^4) (1+x)$

$= \frac{1}{1-x^2} \cdot \frac{1}{1-x^5} \cdot \frac{1-x^5}{1-x} \cdot (1+x)$

$= (1-x)^{-2}$

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

Por lo $a_n = n+1$.

Dada la sencillez del resultado y el OP de la solicitud para un no-GF solución, buscamos una combinatoria prueba de que el número de soluciones es $n+1$. Para ello, supongamos $n \ge 0$ es dado. Considere una de las $n+1$ pares $(i, n-i)$, $i = 0, 1, 2, \dots ,n$. No son exclusivos de enteros no negativos $x_1$ y $x_4$, $x_4 \le 1$, tal que $2 x_1 + x_4 = i$. Y allí también son únicos enteros no negativos $x_2$ y $x_3$, $x_3 \le 4$, tal que $5 x_2 + x_3 = n-i$. A continuación,$2 x_1 + 5 x_2 + x_3 + x_4 = i + (n-i)= n$. Dada una solución de la ecuación, también podemos generar fácilmente el par $(i, n-i)$; así que tenemos un bijection entre las soluciones de la ecuación y el $n+1$ pares de $(i, n-i)$.