しましょう $b_{n}$ の構成の数を示します $n$ に $k$パーツ。各パーツは1つまたは2つです。の母関数を見つける $b_{n}$

Aug 16 2020

私はこの組み合わせ論の問題で立ち往生しています-

しましょう $n$ 正の整数になり、 $b_{n}$ の構成の数を示します $n$$k$パーツ。各パーツは1つまたは2つです。例えば、$(1, 2, 1, 2, 1)$ そして $(2, 2, 1, 1, 1)$ の2つの構成です $n = 7$$k = 5$ 部品。

まず、次の母関数を見つける必要があります。 $b_{n}$

第二に、それを証明する $b_{n} = {k \choose n-k}$ にとって $k\le n \le2k$ そして $b_{n} = 0$ そうでなければ。

回答

4 PrabhSimranSinghBadwal Aug 16 2020 at 19:48

母関数を計算するために-

{1,2}$^{𝑘}$ それぞれが1または2のいずれかであるk個の部分を持つ構成のセットである。

次に、「製品補題」を適用します $$\varphi_{s}(x) = (\varphi_{(1,2)} (x))^{k} = (x+x^{2})^{k} $$

証明-

nとkの部分の合成は $i$ 一部の部品は2に等しい $0\le i\le k$。1に等しい部品の数は$k-i$、および $n = (k-i) + 2i$、与える $i = n-k$。がある$k$ の位置 $n-k$ パーツが2に等しいため、合計{k \ choosenk}の構成があります。 $n$$k$ パーツ、それぞれ $1$ または $2$。ご了承ください$0\le i\le k$ 意味する $k\le n\le 2k$、それ以外の場合、構成の数はゼロです。

1 GregMartin Aug 17 2020 at 05:39

2番目の質問には素晴らしい組み合わせ論的証明があります:

の構成の数 $n$$k$ それぞれが等しい部分 $1$ または $2$ の構成の数に等しい $n-k$$k$ それぞれが等しい部分 $0$ または $1$。明らかにあるに違いない$n-k$ $1$sそのような構成で、そしてあります $\binom k{n-k}$ それらを配置する方法 $1$の中で $k$ 部品。

cr001 Aug 16 2020 at 19:37

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

(2)の係数 $x^n$ にあります $x^k(1+x)^k$ と同じ $x^{n-k}$$(1+x)^k$。したがって、二項定理によれば、${k\choose n-k}$