Đến nội dung

NAPOLE

NAPOLE

Đăng ký: 08-09-2006
Offline Đăng nhập: 01-10-2018 - 09:58
-----

#188283 Chứng minh tổ hợp là quen hay lạ

Gửi bởi NAPOLE trong 13-07-2008 - 22:22

Thừơng thường khi ra 1 bài về chứng minh các công thức tổ hợp thì các bạn học sinh của chúng ta hay (rất hay) sử
dụng các công thức về tổ hợp , chỉnh hợp để chứng minh đẳng thức là đúng mà các bạn hay quên đi các chứng minh tổ hợp rất hay và bổ ích cho những ai muốn đào sâu về phần tóan rời rạc .
Sau đây là 1 ví dụ : Chứng minh hằng đẳng thức Pascal
$C(n+1,k)=C(n,k-1)+C(n,k)$
Đứng trước bài tóan này đa số các bạn đều làm các biến đổi đại số rồi đưa ra kết quả là đẳng thức trên đúng mà không hề biết về chứng minh tập hợp của nó . Ở đây mình sẽ đưa ra chứng minh bằng tập hợp của nó như sau :
Giả sử ta có 1 tập hợp $S$ có $n+1$ phần tử. Gọi $a$ là 1 phần tử nào đó thuộc tập $S$ và $T=S-{a}$. Ta thấy để chọn ra $k$ phần tử trong tập gồm $n+1$ phần tử trên ta có 2 cách chọn :
1. Chọn $k$ phần tử thuộc tập T . Ta có $C(n,k)$ cách chọn .
2. Chọn ra phần tử $a$ trước rồi sau đó chọn $k-1$ phần tử từ tập T . Ta có $C(n,k-1)$ cách chọn .
Áp dụng thêm quy tắc cộng ta có đpcm .

Chứng minh trên , mang lại cho tôi 1 cảm giác hứng thú . Nó không chỉ chứng minh đúng hằng đẳng thức Pascal về mặt đại số mà còn chỉ cho chúng ta các cách để tạo nên tập kết quả . Các cách để tạo ra 1 tập lớn hơn từ các tập thành phần . Không dông dài ở đây nữa , chúng ta sẽ đi qua 1 hằng đẳng thức khác khá quen thuộc mà có lẽ dùng CM Đại số sẽ rối rắm hơn CMTổ Hợp .
HẰNG ĐẲNG THỨC VANDERMONDE
Giả sử $m,n$ và $r$ là các số nguyên không âm sao cho $r$ không vượt quá $m$ hay $n$. Chứng minh rằng :

$C(m+n,r)= \sum\limits_{k=0}^{r} C(m,r-k)C(n,k)$


Chứng minh
Giả sử cho một tập có $m$ phần tử và tập thứ hai có $n$ phần tử . Khi đó tổng số cách
chọn $r$ phần tử từ 2 tập trên là $C(m+n,r)$ . Một cách khác để chọn $r$ phần tử từ hợp
của 2 tập trên là chọn $k$ phần tử $(k=0,1,....,r)$ từ tập thứ nhất và $r-k$ phần tử từ tập thứ 2 . Theo quy tắc nhân , điều này có thể làm bằng $C(m,k).C(n,r-k)$ cách . Vì vậy tổng số cách chọn $r$ phần tử từ hợp của 2 tập hợp là :
$C(m+n,r)= \sum\limits_{k=0}^{r} C(m,r-k)C(n,k)$
Đó chính là hằng đẳng thức Vandermonde.

Tiếp nào , các bạn thấy chứng minh trên còn chỉ ra 2 cách để tạo tập kết quả , thật là đơn giản đúng không nào .
Vậy chúng ta hãy định nghĩa một chứng minh tổ hợp là 1 chứng minh như thế nào ?
Định nghĩa :Một chứng minh tổ hợp là 1 chứng minh dùng các lập luận đếm để chứng minh định lí chứ không phải dùng một phương pháp nào khác , ví dụ như kĩ thuật đại số chẳng hạn.

Định nghĩa thì nhìn đơn giản , nhưng các bạn phải tập làm quen với các lập luận đếm (Quy tắc nhân , Quy tắc cộng ...) để có thể nắm vững các phương pháp chứng minh tổ hợp .
Chúng ta có thể mô hình các bài toán đếm để sử dụng các quy tắc đếm 1 cách dễ dàng hơn . Các bạn hãy xem ví dụ sau sẽ thấy rõ hơn :
Chứng minh rằng trong 1 tập hợp có $n$ phần tử thì số tập hợp con của nó (bao gồm cả tập rỗng) là $2^n$

Chứng minh
Ta giả sử chúng ta có 1 chuỗi nhị phân ( chỉ gồm các chữ số $0,1$) với độ dài $n$. Các bạn hãy để ý nếu tại vị trí thứ $i$ trong chuỗi , nếu phần tử đó thuộc 1 tập con nào đó thì nó sẽ nhận giá trị là $1$ , còn không sẽ có giá trị là $0$ . Vậy với mỗi vị trí chúng ta có 2 cách chọn là $0$ hay $1$ . Chuỗi chúng ta có độ dài là $n$ . Vậy thì áp dụng quy tắc nhân : Số tập con $=2.2....2=2^{n}$ . Đó là điều phải chứng minh . :D


Từ bài toán trên ta có thể suy ra được bài toán :
Nếu $n$ là 1 số nguyên không âm thì

$\sum\limits_{k=0}^{n}C(n,k)=2^n$


Có thể chứng minh bài toán trên bằng cách dùng định lí nhị thức (gợi ý xem $2^n=(1+1)^n$) .

Bài Tập
1. Cho $r \leq n$ . Chứng minh rằng :
$C(n+1,r+1)=\sum\limits_{j=r}^{n}C(j,r)$.
2.Chứng minh công thức
$C(n,r ).C(n,k)=C(n,k).C(n-k,r-k)$
trong đó $n,r,k$ là các số nguyên ko âm và $r \leq n$ và $k \leq r$
3.Chứng minh :
$\sum\limits_{k=1}^{n}k.C(n,k)^2=n.C(2n-1,n-1)$
4. Chứng minh
$\sum\limits_{k=1}^{n}k.C(n,k)=n.2^{n-1}$
5.Chứng minh rằng :
$\sum\limits_{k=0}^{r}C(n+k,k)=C(n+r+1,r)$


Bạn nào có lời giải thì hãy vào đây post lên nhé


#152842 $(9ac+bd)(ad+bc)=a^2d^2+10abcd+b^2+c^2$

Gửi bởi NAPOLE trong 03-04-2007 - 07:35

Tìm $a,b,c,d$ nguyên dương thỏa mãn đồng thời hai điều kiện:
1) $bd>ad+bc$
2) $(9ac+bd)(ad+bc)=a^2d^2+10abcd+b^2+c^2$


#149847 $x^4+2y^3-x=-\dfrac{1}{4}+3\sqrt{3}$

Gửi bởi NAPOLE trong 06-03-2007 - 16:42

Giải hệ :  

$$\left\{\begin{matrix}x^4+2y^3-x=-\dfrac{1}{4}+3\sqrt{3}\\y^4+2x^3-y=-\dfrac{1}{4}-3\sqrt{3}\end{matrix}\right.$$

===================================
Good luck




#149826 $\sqrt{x^2-p}+2{x^2-1}=x$

Gửi bởi NAPOLE trong 06-03-2007 - 07:23

Giải phương trình
$$\sqrt{x^2-p}+2{x^2-1}=x$$
Với $p$ là hằng số thực.


#133986 $4xy+4(x^2+y^2)+\dfrac{3}{(x+y)^2}=\dfrac...

Gửi bởi NAPOLE trong 28-11-2006 - 07:53

Giải hệ PT sau :


$$\left\{\begin{matrix}4xy+4(x^2+y^2)+\dfrac{3}{(x+y)^2}&=\dfrac{85}{3}\\2x+ \dfrac{1}{x+y}&=\dfrac{13}{3}\end{matrix}\right.$$



#131051 $31x^5+165x^4+310x^3+330x^2+155x+33=0$

Gửi bởi NAPOLE trong 18-11-2006 - 08:16

Giải phương trình sau :
$$31x^5+165x^4+310x^3+330x^2+155x+33=0$$


#123231 Dùng hằng đẳng thức để giải bài tập

Gửi bởi NAPOLE trong 21-10-2006 - 06:47

Tui thấy cái đẳng thức này là hay xài đối với THCS nhất :
$a^{3}+b^{3}+c^{3}-3abc=(a+b+c)(a^2+b^2+c^2-ab-bc-ca)$
Dùng nó để giải pt bậc 3 hay trục căn là tuyệt vời:
Vd :TRục căn ở mẫu:
$\dfrac{1}{ \sqrt[3]{5} +\sqrt[3]{2}+\sqrt[3]{3}}$


#120963 Các bạn thích nhà toán học nào nhất?

Gửi bởi NAPOLE trong 12-10-2006 - 06:43

Sao ít người nói về Euler thế nhỉ ?Ông là một nhà toán học thiên tài nhưng tộii thay lại bị mù ở 17 năm cuối đời :cry .Nhưng chính lúc này là lúc ông viết ra hơn 1/2 số tác phẩm của mình !Quá siêu phải ko ?Ông chính là một tấm gương sáng cho mình noi theo (Tất nhiên mình ko muốn mù giống Euler.Hì hì)