Deixei $b_{n}$ denotam o número de composições de $n$ para dentro $k$partes, onde cada parte é uma ou duas. Encontre a série geradora para $b_{n}$
Estou preso a esses problemas combinatórios -
Deixei $n$ seja um número inteiro positivo e deixe $b_{n}$ denotam o número de composições de $n$ para dentro $k$partes, onde cada parte é uma ou duas. Por exemplo,$(1, 2, 1, 2, 1)$ e $(2, 2, 1, 1, 1)$ são duas composições de $n = 7$ para dentro $k = 5$ partes.
Em primeiro lugar, precisamos encontrar a série geradora para $b_{n}$
Em segundo lugar, prove que $b_{n} = {k \choose n-k}$ para $k\le n \le2k$ e $b_{n} = 0$ de outra forma.
Respostas
Para calcular a série geradora -
Vamos {1,2}$^{𝑘}$ ser o conjunto de composições com k partes, cada uma das quais 1 ou 2.
Em seguida, aplicando o "Lema do Produto" $$\varphi_{s}(x) = (\varphi_{(1,2)} (x))^{k} = (x+x^{2})^{k} $$
Provando -
Uma composição de n com k partes terá $i$ partes iguais a 2, para alguns $0\le i\le k$. Observe que o número de partes igual a 1 é$k-i$, e $n = (k-i) + 2i$, dando $i = n-k$. tem$k$ posições para o $n-k$ partes iguais a 2, então há um total de {k \ choose nk} composições de $n$ para dentro $k$ partes, cada uma $1$ ou $2$. Observe que$0\le i\le k$ implica $k\le n\le 2k$, e o número de composições é zero caso contrário.
Há uma boa prova combinatória para a segunda pergunta:
O número de composições de $n$ para dentro $k$ partes cada uma igual a $1$ ou $2$ é igual ao número de composições de $n-k$ para dentro $k$ partes cada uma igual a $0$ ou $1$. É claro que deve haver$n-k$ $1$s em tal composição, e há $\binom k{n-k}$ maneiras de organizar aqueles $1$está entre os $k$ partes.
(1) é $(x+x^2)^k=x^k(1+x)^k$
(2) O coeficiente de $x^n$ é em $x^k(1+x)^k$ igual a $x^{n-k}$ dentro $(1+x)^k$. Portanto, pelo teorema binomial, é${k\choose n-k}$