Laisser $b_{n}$ désignent le nombre de compositions de $n$ dans $k$parties, où chaque partie est une ou deux. Trouvez la série génératrice pour $b_{n}$

Question

Je suis coincé avec ces problèmes de combinatoire -

Laisser $n$ être un entier positif et soit $b_{n}$ désignent le nombre de compositions de $n$ dans $k$parties, où chaque partie est une ou deux. Par exemple,$(1, 2, 1, 2, 1)$ et $(2, 2, 1, 1, 1)$ sont deux compositions de $n = 7$ dans $k = 5$ les pièces.

Tout d'abord, nous devons trouver la série génératrice pour $b_{n}$

Deuxièmement, prouvez que $b_{n} = {k \choose n-k}$ pour $k\le n \le2k$ et $b_{n} = 0$ autrement.

Answer 1

Afin de calculer la série génératrice -

Soit {1,2}$^{𝑘}$ être l'ensemble des compositions avec k parties, dont chacune vaut 1 ou 2.

Ensuite, en appliquant le "Lemme Produit" $$\varphi_{s}(x) = (\varphi_{(1,2)} (x))^{k} = (x+x^{2})^{k} $$

Prouver -

Une composition de n avec k parties aura $i$ parties égales à 2, pour certains $0\le i\le k$. Notez que le nombre de parties égal à 1 est$k-i$, et $n = (k-i) + 2i$, donnant $i = n-k$. Il y a$k$ positions pour le $n-k$ parties égales à 2, il y a donc un total de {k \ choose nk} compositions de $n$ dans $k$ pièces, chacune soit $1$ ou $2$. Notez que$0\le i\le k$ implique $k\le n\le 2k$, et le nombre de compositions est égal à zéro sinon.

Answer 2

Il y a une belle preuve combinatoire pour la deuxième question:

Le nombre de compositions de $n$ dans $k$ parties égales chacune à $1$ ou $2$ est égal au nombre de compositions de $n-k$ dans $k$ parties égales chacune à $0$ ou $1$. Il doit clairement y avoir$n-k$ $1$s dans une telle composition, et il y a $\binom k{n-k}$ façons d'organiser ces $1$s parmi les $k$ les pièces.

Answer 3

(1) C'est $(x+x^2)^k=x^k(1+x)^k$

(2) Le coefficient de $x^n$ est dans $x^k(1+x)^k$ pareil que $x^{n-k}$ dans $(1+x)^k$. Par conséquent, par théorème binomial, il est${k\choose n-k}$