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}$

Aug 16 2020

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

4 PrabhSimranSinghBadwal Aug 16 2020 at 19:48

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.

1 GregMartin Aug 17 2020 at 05:39

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.

cr001 Aug 16 2020 at 19:37

(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}$