Để cho $b_{n}$ biểu thị số lượng các tác phẩm của $n$ thành $k$các bộ phận, trong đó mỗi bộ phận là một hoặc hai. Tìm chuỗi tạo cho $b_{n}$
Tôi đang gặp khó khăn với vấn đề tổ hợp này -
Để cho $n$ là một số nguyên dương và để $b_{n}$ biểu thị số lượng các tác phẩm của $n$ thành $k$các bộ phận, trong đó mỗi bộ phận là một hoặc hai. Ví dụ,$(1, 2, 1, 2, 1)$ và $(2, 2, 1, 1, 1)$ là hai tác phẩm của $n = 7$ thành $k = 5$ các bộ phận.
Trước tiên, chúng ta cần tìm chuỗi tạo cho $b_{n}$
Thứ hai, chứng minh rằng $b_{n} = {k \choose n-k}$ cho $k\le n \le2k$ và $b_{n} = 0$ nếu không thì.
Trả lời
Để tính toán chuỗi tạo -
Hãy {1,2}$^{𝑘}$ là tập hợp các tác phẩm có k phần, mỗi phần là 1 hoặc 2.
Sau đó, áp dụng "Bổ đề sản phẩm" $$\varphi_{s}(x) = (\varphi_{(1,2)} (x))^{k} = (x+x^{2})^{k} $$
Chứng minh -
Một thành phần gồm n với k phần sẽ có $i$ phần bằng 2, đối với một số $0\le i\le k$. Lưu ý rằng số phần bằng 1 là$k-i$và $n = (k-i) + 2i$, cho $i = n-k$. Có$k$ vị trí cho $n-k$ các phần bằng 2, do đó có tổng số {k \ select nk} tác phẩm của $n$ thành $k$ các bộ phận, mỗi bộ phận $1$ hoặc là $2$. Lưu ý rằng$0\le i\le k$ ngụ ý $k\le n\le 2k$, và số lượng các sáng tác bằng 0 nếu không.
Có một bằng chứng tổ hợp tuyệt vời cho câu hỏi thứ hai:
Số lượng sáng tác của $n$ thành $k$ mỗi phần bằng $1$ hoặc là $2$ bằng với số lượng tác phẩm của $n-k$ thành $k$ mỗi phần bằng $0$ hoặc là $1$. Rõ ràng là phải có$n-k$ $1$trong một bố cục như vậy, và có $\binom k{n-k}$ cách sắp xếp những $1$s trong số $k$ các bộ phận.
(1) Nó là $(x+x^2)^k=x^k(1+x)^k$
(2) Hệ số của $x^n$ trong $x^k(1+x)^k$ giống như $x^{n-k}$ trong $(1+x)^k$. Do đó theo định lý nhị thức, nó là${k\choose n-k}$