Đến nội dung

Hình ảnh

Bằng cách lý luận tổ hợp, hãy chứng tỏ rằng $\sum_{k=0}^{n}\binom{n}{k}=2^n$

- - - - -

  • Please log in to reply
Chủ đề này có 3 trả lời

#1
Nobodyv3

Nobodyv3

    Generating Functions Faithful

  • Thành viên
  • 913 Bài viết

Bằng cách lý luận tổ hợp, hãy chứng tỏ rằng :
i) $\sum_{k=0}^{n}\binom{n}{k}=2^n$
ii)$\binom {n}{k}=\binom {n}{n-k}$
iii)$\frac {(2n)!}{2^n\cdot n!}=(2n-1)(2n-3)...3\cdot 1$
iv) Với mọi số nguyên dương  $n\geq k $:
$\binom {n}{k}+\binom {n}{k-1}=\binom {n+1}{k}$
v) $k\binom {n}{k}=n\binom {n-1}{k-1}$
vi) $1+2+...+n=\frac {n(n+1)}{2}$
vii) Thiết lập đẳng thức tổ hợp trong tình huống : từ m bạn nam và n bạn nữ lập thành 1 tổ có k bạn.


Bài viết đã được chỉnh sửa nội dung bởi perfectstrong: 17-03-2023 - 16:18
Tiêu đề & LaTeX

<p>
advice
Once is chance. Twice is coincidence. Thrice is a pattern.

#2
hxthanh

hxthanh

    Tín đồ $\sum$

  • Hiệp sỹ
  • 3726 Bài viết
1.Chọn ra một tập con bất kỳ từ $n$ đối tượng khác nhau. Mỗi đối tượng có đúng 2 trạng thái được chọn hoặc không.
2. Việc chọn ra $k$ đối tượng (trong $n$ đối tượng) tương đương với không chọn $(n-k)$ đối tượng
3. Sắp xếp $2n$ đối tượng tương đương với sắp xếp $n$ cặp đối tượng.
4. Trong $n+1$ đối tượng có một đối tượng $A$. Cần chọn ra $k$ đối tượng
- Có $A$ có $n\choose k-1$ cách
- Không có $A$ có $n\choose k$ cách
5. Chọn ra $k$ người trong $n$ người khác nhau và có 1 người chọn làm lãnh đạo
- Chọn ra $k$ người có $n\choose k$. Chọn lãnh đạo có $k$ cách
- Chọn 1 lãnh đạo có $n$ cách. Chọn $k-1$ người khác có $n-1\choose k-1$ cách.
6. Chưa nghĩ ra :luoi:
7. $m$ nam $n$ nữ chọn một tổ $k$ bạn
- Có $m+n\choose k$ cách
- Nếu chọn $i$ nam và $k-i$ nữ thì có $m \choose i$ và(nhân) $n\choose k-i$ cách
Hay $\sum_{i=0}^k {m\choose i}{n\choose k-i}=\sum_{i+j=k} {m\choose i}{n\choose j}={m+n\choose k}$

#3
chanhquocnghiem

chanhquocnghiem

    Thiếu tá

  • Thành viên
  • 2494 Bài viết

Bằng cách lý luận tổ hợp, hãy chứng tỏ rằng :
i) $\sum_{k=0}^{n}\binom{n}{k}=2^n$
ii)$\binom {n}{k}=\binom {n}{n-k}$
iii)$\frac {(2n)!}{2^n\cdot n!}=(2n-1)(2n-3)...3\cdot 1$
iv) Với mọi số nguyên dương  $n\geq k $:
$\binom {n}{k}+\binom {n}{k-1}=\binom {n+1}{k}$
v) $k\binom {n}{k}=n\binom {n-1}{k-1}$
vi) $1+2+...+n=\frac {n(n+1)}{2}$
vii) Thiết lập đẳng thức tổ hợp trong tình huống : từ m bạn nam và n bạn nữ lập thành 1 tổ có k bạn.

Câu 6 : Chọn $2$ đỉnh từ một đa giác có $n+1$ đỉnh.

- Chọn $2$ đỉnh trong đó có $A_1$ : $n$ cách.

- Chọn $2$ đỉnh, trong đó không có $A_1$ và có $A_2$ : $n-1$ cách.
- Chọn $2$ đỉnh, trong đó không có $A_1,A_2$ và có $A_3$ : $n-2$ cách.

- Chọn $2$ đỉnh, trong đó không có $A_1,A_2,A_3$ và có $A_4$ : $n-3$ cách.

- ...................................................

- ...................................................

- Chọn $2$ đỉnh, trong đó không có $A_1,A_2,...,A_{n-1}$ và có $A_n$ : $1$ cách.

  $\Rightarrow 1+2+3+...+n=\binom{n+1}{2}=\frac{n(n+1)}{2}$


Bài viết đã được chỉnh sửa nội dung bởi chanhquocnghiem: 17-03-2023 - 20:37

...

Ðêm nay tiễn đưa

Giây phút cuối vẫn còn tay ấm tay
Mai sẽ thấm cơn lạnh khi gió lay
Và những lúc mưa gọi thương nhớ đầy ...

 

http://www.wolframal...-15)(x^2-8x+12)


#4
Nobodyv3

Nobodyv3

    Generating Functions Faithful

  • Thành viên
  • 913 Bài viết
vi) Giả sử ta có bài toán : " Tính số xâu nhị phân kích thước n+1 có đúng hai bit 1."
Giải:
+ Cách 1: Số xâu nhị phân kích thước n+1 có đúng hai bít 1 là : $\binom {n+1}{2}=\frac {n(n+1)}{2}$
+ Cách 2: Ta sẽ tính số xâu nhị phân tùy theo vị trí đầu tiên của bit 1 trong xâu (từ trái qua phải ).
- Bit 1 đầu tiên đứng ở vị trí thứ nhất : có $n$ cách chọn vị trí cho bit 1 còn lại.
- Bit 1 đầu tiên đứng ở vị trí thứ hai : có $n-1$ cách chọn vị trí cho bit 1 còn lại.
- Bit 1 đầu tiên đứng ở vị trí thứ ba : có $n-2$ cách chọn vị trí cho bit 1 còn lại.
.......
......
- Bit 1 đầu tiên đứng ở vị trí thứ n-1 : có $2$ cách chọn vị trí cho bit 1 còn lại.
- Bit 1 đầu tiên đứng ở vị trí thứ n : có $1$ cách chọn vị trí cho bit 1 còn lại.
Vậy số xâu nhị phân kích thước n+1 có đúng hai bít 1 là :$n+(n-1)+(n-2)+...+2+1$
Kết luận :
Cách 1 và cách 2 là 2 lời giải đúng của cùng một bài toán cho nên :
$$1+2+....+(n-2)+(n-1)+n=\frac {n(n+1)}{2}\quad\quad\square$$
<p>
advice
Once is chance. Twice is coincidence. Thrice is a pattern.




0 người đang xem chủ đề

0 thành viên, 0 khách, 0 thành viên ẩn danh