Để 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}$

Aug 16 2020

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)$$(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$$b_{n} = 0$ nếu không thì.

Trả lời

4 PrabhSimranSinghBadwal Aug 16 2020 at 19:48

Để 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$$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.

1 GregMartin Aug 17 2020 at 05:39

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.

cr001 Aug 16 2020 at 19:37

(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}$