허락하다 $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)$ 두 가지 구성 $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}$^{𝑘}$ k 부분으로 구성된 컴포지션의 집합이며, 각 부분은 1 또는 2입니다.

그런 다음 "제품 기본형"을 적용합니다. $$\varphi_{s}(x) = (\varphi_{(1,2)} (x))^{k} = (x+x^{2})^{k} $$

증명-

k 부분을 가진 n의 구성은 $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$, 그렇지 않으면 작곡 수는 0입니다.

1 GregMartin Aug 17 2020 at 05:39

두 번째 질문에 대한 좋은 조합 증거가 있습니다.

작곡의 수 $n$ 으로 $k$ 다음과 같은 부품 $1$ 또는 $2$ 의 작곡 수와 같습니다. $n-k$ 으로 $k$ 다음과 같은 부품 $0$ 또는 $1$. 분명히 있어야합니다$n-k$ $1$이러한 구성에 s가 있고 $\binom k{n-k}$ 그것들을 배열하는 방법 $1$s 중 $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}$