Позволять $b_{n}$ обозначают количество составов $n$ в $k$части, где каждая часть - одна или две. Найдите производящий ряд для $b_{n}$
Я застрял в этой комбинаторике -
Позволять $n$ - натуральное число и пусть $b_{n}$ обозначают количество составов $n$ в $k$части, где каждая часть - одна или две. Например,$(1, 2, 1, 2, 1)$ и $(2, 2, 1, 1, 1)$ две композиции $n = 7$ в $k = 5$ части.
Во-первых, нам нужно найти производящий ряд для $b_{n}$
Во-вторых, докажите, что $b_{n} = {k \choose n-k}$ за $k\le n \le2k$ и $b_{n} = 0$ иначе.
Ответы
Чтобы рассчитать производящий ряд -
Пусть {1,2}$^{𝑘}$ - набор композиций из k частей, каждая из которых равна 1 или 2.
Затем, применяя «лемму о произведении» $$\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 \ choose nk} композиций $n$ в $k$ части, каждая либо $1$ или же $2$. Обратите внимание, что$0\le i\le k$ подразумевает $k\le n\le 2k$, иначе количество композиций равно нулю.
На второй вопрос есть хорошее комбинаторное доказательство:
Количество композиций $n$ в $k$ части каждая равна $1$ или же $2$ равно количеству составов $n-k$ в $k$ части каждая равна $0$ или же $1$. Очевидно, должно быть$n-k$ $1$s в такой композиции, и есть $\binom k{n-k}$ способы организации тех $1$s среди $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}$