Dejar $b_{n}$ denotar el número de composiciones de $n$ dentro $k$partes, donde cada parte es una o dos. Encuentre la serie generadora para $b_{n}$
Estoy atrapado con estos problemas de combinatoria:
Dejar $n$ ser un entero positivo y dejar $b_{n}$ denotar el número de composiciones de $n$ dentro $k$partes, donde cada parte es una o dos. Por ejemplo,$(1, 2, 1, 2, 1)$ y $(2, 2, 1, 1, 1)$ son dos composiciones de $n = 7$ dentro $k = 5$ partes.
En primer lugar, necesitamos encontrar la serie generadora para $b_{n}$
En segundo lugar, demuestre que $b_{n} = {k \choose n-k}$ para $k\le n \le2k$ y $b_{n} = 0$ de otra manera.
Respuestas
Para calcular la serie generadora -
Deje {1,2}$^{𝑘}$ ser el conjunto de composiciones con k partes, cada una de las cuales es 1 o 2.
Luego, aplicando el "Lema del producto" $$\varphi_{s}(x) = (\varphi_{(1,2)} (x))^{k} = (x+x^{2})^{k} $$
Demostrando -
Una composición de n con k partes tendrá $i$ partes iguales a 2, para algunos $0\le i\le k$. Tenga en cuenta que el número de partes igual a 1 es$k-i$y $n = (k-i) + 2i$, dando $i = n-k$. Existen$k$ posiciones para el $n-k$ partes iguales a 2, por lo que hay un total de {k \ elija nk} composiciones de $n$ dentro $k$ partes, cada una $1$ o $2$. Tenga en cuenta que$0\le i\le k$ implica $k\le n\le 2k$, y el número de composiciones es cero en caso contrario.
Hay una buena prueba combinatoria para la segunda pregunta:
El número de composiciones de $n$ dentro $k$ partes cada una igual a $1$ o $2$ es igual al número de composiciones de $n-k$ dentro $k$ partes cada una igual a $0$ o $1$. Claramente debe haber$n-k$ $1$s en tal composición, y hay $\binom k{n-k}$ formas de organizar esos $1$s entre los $k$ partes.
(1) es $(x+x^2)^k=x^k(1+x)^k$
(2) El coeficiente de $x^n$ es en $x^k(1+x)^k$ igual que $x^{n-k}$ en $(1+x)^k$. Por lo tanto, por teorema binomial es${k\choose n-k}$