しましょう $b_{n}$ の構成の数を示します $n$ に $k$パーツ。各パーツは1つまたは2つです。の母関数を見つける $b_{n}$
私はこの組み合わせ論の問題で立ち往生しています-
しましょう $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$ そうでなければ。
回答
母関数を計算するために-
{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$、それ以外の場合、構成の数はゼロです。
2番目の質問には素晴らしい組み合わせ論的証明があります:
の構成の数 $n$ に $k$ それぞれが等しい部分 $1$ または $2$ の構成の数に等しい $n-k$ に $k$ それぞれが等しい部分 $0$ または $1$。明らかにあるに違いない$n-k$ $1$sそのような構成で、そしてあります $\binom k{n-k}$ それらを配置する方法 $1$の中で $k$ 部品。
(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}$