Supongamos que hay una plaza de aparcamiento con $N$ lotes. Una bicicleta ocupa 1 lote, mientras que un coche ocupa 2 lotes consecutivos. Hay $a$ colores para bicicletas y $b$ colores para los coches. ¿Cuántas formas hay de aparcar coches y bicicletas en la plaza de aparcamiento si el orden y el color importan?
Para $N=a=b=2$ hay 6 maneras; si $N$ se cambia a 1 hay 2 formas. Vea la imagen de abajo.
Aunque este problema es bastante sencillo, quizá pueda servir como motivación para aprender más sobre las funciones generadoras. Tenemos por inspección utilizando $z$ para los lotes, $u$ para bicicletas y $v$ para los coches que están representados por la función generadora
$$(1+uz+u^2z^2+\cdots) \left(\sum_{q\ge 0} (vz^2+v^2z^4+\cdots)^q (uz+u^2z^2+\cdots)^q\right) \\ \times (1+vz^2+v^2z^4+\cdots).$$
Esto se simplifica a
$$\frac{1}{1-uz} \left(\sum_{q\ge 0} \frac{(vz^2)^q}{(1-vz^2)^q} \frac{(uz)^q}{(1-uz)^q}\right) \frac{1}{1-vz^2} \\ = \frac{1}{1-uz} \frac{1}{1-uvz^3/(1-vz^2)/(1-uz)} \frac{1}{1-vz^2} \\ = \frac{1}{(1-uz)(1-vz^2)-uvz^3} = \frac{1}{1-uz-vz^2}.$$
Ahora instanciando $u$ a $a$ y $v$ a $b$ obtenemos la función generadora función
$$\frac{1}{1-az-bz^2}.$$
La ecuación característica de la recurrencia correspondiente se obtenida a partir de $1-a/z-b/z^2 = 0$ o $z^2 = az+b.$ Por lo tanto, la respuesta está dada por la recurrencia $f_n= a f_{n-1} + b f_{n-2}$ que coincide con el resultado que se obtuvo por inspección en los comentarios, que simplemente dice que el ocupante de la derecha es una bicicleta o un coche. Los valores iniciales de valores son $f_0=1$ y $f_1=a.$
Si nos interesa una forma cerrada obtenemos
$$[z^n] \frac{1}{1-z(a+bz)}.$$
Esto es $$\sum_{q=0}^n [z^n] z^q (a+bz)^q = \sum_{q=0}^n [z^{n-q}] (a+bz)^q = \sum_{q=0}^n {q\choose n-q} b^{n-q} a^{2q-n}.$$
Así que tienes eso:
Para $N=1$ hay $a$ formas de seleccionar el color para la única bicicleta.
Para $N=2$ hay $a^2$ formas de seleccionar los colores para dos bicicletas, y $b$ formas de seleccionar un color para un coche. Es decir $a^2+b$ opciones en total.
Siguiendo en esta línea podemos ver:
Para $N=3$ puedes tener tres motos, o un coche y una moto. Así que hay $a^3+2ab$ opciones. (Porque hay $\tbinom 20$ formas de seleccionar la colocación de dos objetos).
Para $N=4$ puedes tener cuatro motos, un coche y dos motos, o dos coches, para un total de $a^4+3 a^2b+ b^2$ opciones.
En resumen, de $\mu(N)$ es el recuento de opciones para $N$ plazas de aparcamiento.
$$\mu(N) =\begin{cases}a &:& N=1 \\ a^2+b &:&N=2\\ a^3+2ab &:& N=3\\ a^4+3a^2b+b^2 &:& N=4 \\ a^5+4a^3b+3ab^2 &:& N=5 \\ a^6+5a^4b+6a^2b^2+b^3 &:& N=6 \\ \vdots &\vdots& \vdots \\ \sum_{j=0}^k\bbox[pink,0.25ex,border:0.1ex dashed magenta]{\qquad\qquad?} & : & N=2k, k\in\Bbb N_+ \\ \sum_{j=0}^k\bbox[pink,0.25ex,border:0.1ex dashed magenta]{\qquad\qquad?} & : & N=2k+1, k\in\Bbb N_+ \end{cases}$$
¿Puedes ver el patrón?
Dejemos que $x,y$ sea el número de bicicletas y coches respectivamente.
Entonces, debemos tener $0\le y \le N/2$ y $N=x+2y$
El número de formas de colocar $y$ coches y $x$ bicicletas, sin tener en cuenta los colores (es decir, considerándolos idénticos) es
$$ {x+y \choose y}={N-y \choose y}$$
Si podemos elegir $a$ colores para el $x$ bicicletas y $b$ colores para el $y$ coches, el número de formas es ahora
$$ {x+y \choose y} a^x b^y={N-y \choose y}a^{N-2y} b^y$$
Por lo tanto, el recuento total es
$$ \sum_{y=0}^{\lfloor N/2 \rfloor}{N-y \choose y}a^{N-2y} b^y$$
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
