Chủ đề này có 14 trả lời

[E. Galois]

Như các bạn đã biết, để chứng minh một đẳng thức tổ hợp, ta có nhiều cách. Cách phổ biến nhất hiện nay là sử dụng hàm sinh và nhị thức Newton, thậm chí kết hợp với cả đạo hàm, tích phân tạo thành lời giải rất hay. Một cách khác là sử dụng các tính chất của các số $n!,C_n^k,A_n^k,...$

Song, với mình và một số người bạn trên VMF, có một cách khác có sự cuốn hút kì lạ bởi vẻ đẹp đầy chất trí tuệ của nó. Đó là phương pháp đếm số phần tử của 1 tập hợp bằng 2 cách.

Mục tiêu của topic này là xây dựng 1 chuyên đề dùng phương pháp đếm số phần tử của 1 tập hợp bằng 2 cách để chứng minh đẳng thức tổ hợp. Mình tạm định hướng là sẽ cố gắng hoàn thành tài liệu này để đăng lên trang chủ của VMF và gửi đăng báo THTT.

Bản thân mình tài năng có hạn, lại là chuyên gia làm sai tổ hợp nên mình mong mỏi có được sự tham gia của thầy hxthanh, PSW (PSW chắc chắn đồng ý vì đây cũng là ý tưởng của anh ấy) và toàn thể các bậc anh hùng trong giới tổ hợp của diễn đàn.

Tạm quy định như sau:
- Tất cả các lời giải trong topic này đều phải giải bằng phương pháp đếm số phần tử của 1 tập hợp bằng 2 cách.
- Nguyên tắc: "ăn một quả, trả cục vàng". Nếu bạn giải được 1 bài, bạn hãy đưa thêm 1 đề
- Đề bài cần được đánh số thứ tự nghiêm túc, lời giải rõ ràng; khuyến khích giải bằng nhiều cách.
- Cấm spam dưới mọi hình thức

Bài mở đầu thật dễ mới được:

Bài 1. Chứng minh rằng:
$$C_n^0+C_n^1+...+C_n^n=2^n$$
(Đã được Nguyễn Hưng và dante_dmc4 giải ở dưới)

[hxthanh]

Ok, để mình ủng hộ topic này, Bài 1 tạm thời gác lại đã (để dành cho các bạn khác)

Bài 2:
Chứng minh đẳng thức sau:
$$C_n^0C_m^k+C_n^1C_m^{k-1}+...+C_n^kC_m^0=C_{m+n}^k;\;\;\text{với } k\le n \le m$$
__________________
Lời giải:
Lớp 12A gồm $n$ bạn nam và $m$ bạn nữ cần chọn ra $k$ bạn để lập thành đội Văn Nghệ.
Cách 1:
- Chọn ra $k$ bạn trong tập thể lớp gồm $n+m$ bạn - có $C_{m+n}^k$ cách chọn.
Cách 2:
- Chọn ra $i$ bạn nam và $k-i$ bạn nữ - có $C_n^iC_m^{k-i}$ cách.
- Cho $i$ chạy từ $0$ đến $k$, ta có tổng tất cả các cách chọn như vậy là:
$$C_n^0C_m^k+C_n^1C_m^{k-1}+...+C_n^kC_m^0\;\;\text{ cách}$$
Đẳng thức được chứng minh.

Bài 3: (Tổng quát)
- Với $(0 \le k_i \le n_i);\;i=\overline{1,r}$
Chứng minh rằng: $$\sum\limits_{k_1+k_2+...+k_r=k} C_{n_1}^{k_1}C_{n_2}^{k_2}...C_{n_r}^{k_r}=C_{n_1+n_2+...+n_r}^k$$

[hxthanh]

Bài 4: (Đơn giản) (Đã được E.Galois giải ở dưới)
Chứng minh rằng:
$$C_{2n}^0+C_{2n}^2+...+C_{2n}^{2n}=C_{2n}^1+C_{2n}^3+...+C_{2n}^{2n-1}$$

Bài 5: (Khó)
Chứng minh rằng:
$$\sum_{k=1}^n kC_{n+k}^n=\dfrac{n(n+1)C_{2n+1}^n}{n+2}$$

Bài viết đã được chỉnh sửa nội dung bởi E. Galois: 02-07-2012 - 16:57

[Nguyễn Hưng]

Bài 1. Chứng minh rằng:
$$C_n^0+C_n^1+...+C_n^n=2^n$$

Xét $n$ viên bi, ta cần chọn ra một số viên bất kì (có thể không có viên nào)

* Đếm cách 1:

+ Nếu chọn $0$ viên có $C_n^0$ cách

+ Nếu chọn $1$ viên có $C_n^1$ cách

+ .............

+ Nếu chọn $n$ viên có $C_n^n$ cách

Vậy tổng cộng có $C_n^0+C_n^1+C_n^2+...+C_n^n$ cách.

* Đếm cách 2:

Mỗi viên bi trong số $n$ viên đều có 2 trạng thái (được chọn hoặc không được chọn). Vậy có $2^n$ cách chọn.

Kết quả của hai cách đếm cho ta đẳng thức cần chứng minh.


Bài 6 (cũng đơn giản): Chứng minh $C_{n - 1}^{k - 1} + C_{n - 1}^k = C_n^k$
(hxthanh đã giải ngay ở dưới)

Bài viết đã được chỉnh sửa nội dung bởi E. Galois: 02-07-2012 - 16:58

[hxthanh]

Bài 6 (cũng đơn giản): Chứng minh $C_{n - 1}^{k - 1} + C_{n - 1}^k = C_n^k$

Thầy Thế hôm nay sẽ lên lớp bài "TAM GIÁC PASCAL". Trước khi vào bài học mới, thầy muốn gọi $k$ học sinh lên bảng kiểm tra bài cũ. Lớp thầy Thế có $n$ học sinh, tất cả đều đang chăm chú và chuẩn bị tinh thần chờ thầy gọi tên, duy nhất có bạn Hưng là ngủ gục trong lớp.

Thầy Thế phân vân:
- Một là mình sẽ gọi $k$ học sinh, trừ cậu Hưng lên bảng (thầy có $C_{n-1}^k$ cách)
- Hoặc hai là mình sẽ gọi cậu Hưng và $k-1$ học sinh nữa nhỉ? (thầy có $C_{n-1}^{k-1}$ cách)

Rõ ràng: Tổng cộng 2 hành động (suy nghĩ) của thầy là tất cả những lựa chọn mà thầy có thể chọn để gọi $k$ học sinh lên bảng.

Theo lẽ thông thường:
- Để gọi $k$ học sinh lên bảng thì thầy Thế có $C_n^k$ cách.

Như vậy đẳng thức được xác định.

Sau một thoáng suy nghĩ, thầy Thế nói với cả lớp rằng: " Vì trò Hưng ngủ gật trong lớp, nên tôi đã chứng minh được "Định lý Nhị thức Pascal" ..." Sau đó thầy Thế bắt đầu bài giảng của mình bằng bài toán này ...

[supermember]

Em nghĩ thì đây là Topic hướng đến Olympiad nên em sẽ bổ sung 1 bài khó để tăng tính " thử thách " và khuyến khích các cao thủ :

Bài 7 :

Cho $ k_1 ; k_2 ; ... ; k_n $ là các số nguyên lớn hơn hoặc bằng 2

Chứng minh đẳng thức tổ hợp :

$\sum\limits_{1 \le i< j \le n} \binom{k_i}{2}\binom{k_j}{2} + 3\sum\limits_{i=1}^{n}\binom{k_i+1}{4} = \binom{\sum\limits_{i=1}^{n}\binom{k_i}{2}}{2}$

Bài viết đã được chỉnh sửa nội dung bởi hxthanh: 23-12-2011 - 12:28
Clear UP!

[Karl Heinrich Marx]

Em nghĩ thì đây là Topic hướng đến Olympiad nên em sẽ bổ sung 1 bài khó để tăng tính " thử thách " và khuyến khích các cao thủ :

Bài 7 :

Cho $ k_1 ; k_2 ; ... ; k_n $ là các số nguyên lớn hơn hoặc bằng 2

Chứng minh đẳng thức tổ hợp :

$\sum\limits_{1 \le i< j \le n} \binom{k_i}{2}\binom{k_j}{2} + 3\sum\limits_{i=1}^{n}\binom{k_i+1}{4} = \binom{\sum\limits_{i=1}^{n}\binom{k_i}{2}}{2}$

Gọi $A_1,A_2,...,A_n$ là các tập gồm $k_1,k_2,...,k_n$ phần tử. Từ $n$ tập này ta tạo được $ \sum\limits_{i=1}^{n}\binom{k_i}{2}$ cặp phần tử thuộc cùng tập. VP là số cách chọn ra 2 cặp như vậy.

Ta có thể đếm số cách chọn 2 cặp này như sau:
nếu 2 cặp này không cùng thuộc 1 tập thì có $\sum\limits_{1 \le i< j \le n} \binom{k_i}{2}\binom{k_j}{2}$ cách chọn.

Nếu 2 cặp này cùng thuộc 1 tập $A_i$ nào đó có $k_i$ phần tử, ta chèn vào tập này một phần tử ảo là $x_i$ với qui ước nếu trong 4 số được chọn từ $A_i$ trong đó có phần tử $x_i$ thì đồng nghĩa với trong 2 cặp ban đầu có 1 phần tử lặp lại 2 lần trong 3 phần tử còn lại.

Sau khi chọn ra 4 phần tử nếu ko có $x_i$ thì ta có $\binom{3}{2}=3$ cách tạo chúng thành 2 cặp. Nếu có $x_i$ thì có 3 cách gán giá trị cho $x_i$ (là một trong 3 giá trị còn lại) với mỗi giá trị $x_i$ chỉ cho đúng 1 cách phân cặp.

Tóm lại ở trường hợp này sẽ có $3\sum\limits_{i=1}^{n}\binom{k_i+1}{4}$.

Do vậy bài toán được chứng minh.

Bài viết đã được chỉnh sửa nội dung bởi hxthanh: 23-12-2011 - 20:38

[PSW]

Bạn ơi ; bạn cố gắng trình bày cho " chuẩn " 1 chút . Đừng để font lung tung thế này ; khó chỉnh bạn ạ . Vì những người quản lý Topic này sẽ phải đọc Post của bạn để kiểm tra tính đúng sai nên mình mong bạn cố gắng ; cẩn thận

Đây là lời giải bài này ; nó cũng gần giống lời giải của bạn trên

File gửi kèm

•  viewcontent.pdf   234.55K   854 Số lần tải

Bài viết đã được chỉnh sửa nội dung bởi PSW: 25-12-2011 - 19:07

[PSW]

OK ; tiếp tục bằng 1 bài khó :

Bài 8 :

Cho $m ; n $ là những số nguyên không âm . Chứng minh rằng :

$\mathcal{E}(m;n) = \sum\limits_{k=0}^{n}\left ( -1 \right )^{k}\binom{n}{k}\binom{m-k}{m-k-n}=1$

Với $ m \ge 2n $

Bài viết đã được chỉnh sửa nội dung bởi hxthanh: 26-12-2011 - 06:44

[E. Galois]

Bài 4: (Đơn giản)
Chứng minh rằng:
$$C_{2n}^0+C_{2n}^2+...+C_{2n}^{2n}=C_{2n}^1+C_{2n}^3+...+C_{2n}^{2n-1}$$

Áp dụng bài số 1, đẳng thức cần chứng minh tương đương với:
$$C_{2n}^0+C_{2n}^2+...+C_{2n}^{2n}=2^{2n-1}$$
Xét bài toán: Có $2n$ đồ vật, hỏi có bao nhiêu cách lấy ra một số chẵn đồ vật (có thể không có đồ vật nào)?

Cách giải 1
Ta thực hiện $2n$ hành động, Hành động thứ $i (i=1,...,2n)$ ta làm với đồ vật thứ $i$, mỗi hành động ta có 2 phương án: Lấy $(L)$ hoặc là không lấy $(K)$. Ta có $2^{2n}$ cách.
Nhưng vì muốn lấy được một số chẵn đồ vật, mỗi lần chọn $(L)$ (hoặc $(K)$) một đồ vật, ta sẽ phải chọn $(L)$ (hoặc $(K)$) thêm 1 đồ vật khác. Như vậy mỗi cách lấy đã được đếm 2 lần. Do đó ta có số cách lấy là: $\dfrac{2^{2n}}{2} = 2^{2n-1}$

Cách giải 2
Ta có các trường hợp sau:
- TH$1$: Lấy $0$ đồ vật, có $C_{2n}^0$ cách
- TH$2$: Lấy $2$ đồ vật, có $C_{2n}^2$ cách
...
- TH $n+1$: Lấy $2n$ đồ vật, có $C_{2n}^{2n}$ cách
Vậy áp dụng quy tắc cộng ta có: $C_{2n}^0+C_{2n}^2+...+C_{2n}^{2n}$ cách

Do vậy, ta có đpcm.


Ăn một quả trả cục bạc
Bài 9. Chứng minh rằng
$$C_n^1+2C_n^2+3C_n^3+...+nC_n^n=n.2^{n-1}$$
(đã được Nguyễn Hưng giải ở dưới)

[hxthanh]

Bài 10:
Cho $n$ là số nguyên dương bất kỳ. Chứng minh rằng:

$$\sum\limits_{i=k}^{\left\lfloor\frac{n}{2}\right\rfloor} C_{n}^{2i}C_{i}^{k}=2^{n-2k-1}\left(C_{n-k}^{k}+C_{n-k-1}^{n-2k}\right)$$

[dante_dmc4]

Bài 1. Chứng minh rằng:
$$ C_n^0+C_n^1+...+C_n^n=2^n $$

Mình có 1 cách khác cho bài này.
Xét 1 tập hợp A gồm n phần tử. Số tập con của tập hợp này là $$2^n$$ (có thể CM bằng quy nạp)
Ta đếm số tập con theo 1 cách khác:
Số tập con gồm 0 phần tử $$C_n^0$$
...
Số tập con gồm k phần tử: $$C_n^k$$
Vậy VT là tổng số tập con của tập A nên ta có đpcm.

Bài đề nghị: Cm công thức tính số phần tử của hợp các tập hợp theo cách đếm.
Cho n tập hợp $$A_1; A_2,...,A_n$$. Tính
$$A_1UA_2U...UA_n$$

#Galois: Bài 9 của anh e mới chỉ giải đc theo cách đa thức
Xét đa thức $$ F(x)=(1+x)^n $$ Khai triển ra theo nhị thức Newton rồi lấy đạo hàm 2 vế tại x=1 là có đpcm

Bài viết đã được chỉnh sửa nội dung bởi dante_dmc4: 24-03-2012 - 20:44

[Nguyễn Hưng]

Bài 9. Chứng minh rằng
$$C_n^1+2C_n^2+3C_n^3+...+nC_n^n=n.2^{n-1}$$

Tranh thủ làm nhanh mấy bài dễ để mọi người tập trung mấy bài khó ^^

Bài toán: chọn trong $n$ người một số nhân lực để bổ sung cho công ty, trong đó có 1 giám đốc

Đếm cách 1: chọn $k$ người trong $n$ người, sau đó chọn 1 giám đốc từ $k$ người, có $kC_n^k$ cách chọn
Cho $k$ từ 1 đến $n$, có $C_n^1+2C_n^2+3C_n^3+...+nC_n^n$ cách

Đếm cách 2: chọn 1 giám đốc từ $n$ người trước, sau đó mỗi người trong $n-1$ người còn lại có 2 trạng thái: được tuyển và không được tuyển, nên cách đếm này cho đáp số $n.2^{n-1}$

[hxthanh]

...
Bài 3: (Tổng quát)
- Với $(0 \le k_i \le n_i);\;i=\overline{1,r}$
Chứng minh rằng: $$\sum\limits_{k_1+k_2+...+k_r=k} C_{n_1}^{k_1}C_{n_2}^{k_2}...C_{n_r}^{k_r}=C_{n_1+n_2+...+n_r}^k$$

___________
Lâu lâu không thấy topic hoạt động, đẩy lên 1 phát
___________

Thầy Thế có một khay đựng bút chì màu, các cây bút hình thức thì khác nhau nhưng chung quy lại có tất cả $r$ màu $(m_1,m_2, ..., m_r)$
$n_1$ bút màu $m_1$; $n_2$ bút màu $m_2$; ...;$n_r$ bút màu $m_r$
Thầy muốn tặng trò Thanh $k$ cây bút bất kỳ
Cách thứ nhất:
- Chọn ra $k_1$ bút màu $m_1$ có $C_{n_1}^{k_1}$ cách
- Chọn ra $k_2$ bút màu $m_2$ có $C_{n_2}^{k_2}$ cách
...
- Chọn ra $k_r$ bút màu $m_r$ có $C_{n_r}^{k_r}$ cách

Các số lượng lượng $k_1,k_2,...,k_r$ thầy Thế có thể chọn bất kỳ miễn sao tổng số $k_1+k_2+...+k_r=k$ cây bút
Như vậy thầy Thế có tất cả:
$\sum\limits_{k_1+k_2+...+k_r=k} C_{n_1}^{k_1}C_{n_2}^{k_2}...C_{n_r}^{k_r}$
các cách để chọn ra $k$ cây bút tặng trò Thanh.

Cách khác!
Thầy Thế lấy ngẫu nhiên ra $k$ cây bút trong tổng số $n_1+n_2+...+n_r$ cây bút của thầy
dĩ nhiên sẽ có:
$C_{n_1+n_2+...+n_r}^k$ cách để thầy chọn.
Từ đó ta thu được đẳng thức cần chứng minh

[batigoal]

OK ; tiếp tục bằng 1 bài khó :

Bài 8 :

Cho $m ; n $ là những số nguyên không âm . Chứng minh rằng :

$\mathcal{E}(m;n) = \sum\limits_{k=0}^{n}\left ( -1 \right )^{k}\binom{n}{k}\binom{m-k}{m-k-n}=1$

Với $ m \ge 2n $

PSW đưa ra đáp án bài này mình tham khảo với nhé. Mình chỉ làm được theo hàm sinh còn đếm bằng 2 cách thì hiện chưa làm được