İzin Vermek $b_{n}$ kompozisyonların sayısını gösterir $n$ içine $k$her bölümün bir veya iki olduğu bölümler. Üreten seriyi bulun $b_{n}$

Question

Bu kombinatorik problemlerle sıkışıp kaldım -

İzin Vermek $n$ pozitif bir tamsayı olsun ve $b_{n}$ kompozisyonların sayısını gösterir $n$ içine $k$her bölümün bir veya iki olduğu bölümler. Örneğin,$(1, 2, 1, 2, 1)$ ve $(2, 2, 1, 1, 1)$ iki kompozisyon $n = 7$ içine $k = 5$ parçalar.

Öncelikle, oluşturucu seriyi bulmamız gerekiyor. $b_{n}$

İkincisi, kanıtlayın $b_{n} = {k \choose n-k}$ için $k\le n \le2k$ ve $b_{n} = 0$ aksi takdirde.

Answer 1

Üreten seriyi hesaplamak için -

{1,2}$^{𝑘}$ her biri 1 veya 2 olan k parçalı kompozisyonlar dizisi.

Ardından, "Ürün Lemması" nı uygulayarak $$\varphi_{s}(x) = (\varphi_{(1,2)} (x))^{k} = (x+x^{2})^{k} $$

Kanıtlamak -

K parçalı n bileşimi, $i$ bazıları için 2'ye eşit parçalar $0\le i\le k$. 1'e eşit parça sayısının$k-i$, ve $n = (k-i) + 2i$, veren $i = n-k$. Var$k$ için pozisyonlar $n-k$ parçalar 2'ye eşittir, yani toplam {k \ select nk} bileşimi $n$ içine $k$ parçalar, her biri $1$ veya $2$. Bunu not et$0\le i\le k$ ima eder $k\le n\le 2k$ve aksi takdirde kompozisyon sayısı sıfırdır.

Answer 2

İkinci soru için güzel bir kombinatoryal kanıt var:

Bestelerin sayısı $n$ içine $k$ her biri eşit parçalar $1$ veya $2$ kompozisyon sayısına eşittir $n-k$ içine $k$ her biri eşit parçalar $0$ veya $1$. Açıkça olmalı$n-k$ $1$s böyle bir kompozisyonda ve var $\binom k{n-k}$ bunları düzenlemenin yolları $1$arasında $k$ parçalar.

Answer 3

(1) $(x+x^2)^k=x^k(1+x)^k$

(2) katsayısı $x^n$ içinde $x^k(1+x)^k$ ile aynı $x^{n-k}$ içinde $(1+x)^k$. Bu nedenle binom teoremine göre${k\choose n-k}$