Xem bài viết đơn
Old 28-01-2014, 02:09 PM   #14
Fool's theorem
+Thành Viên Danh Dự+
 
Fool's theorem's Avatar
 
Tham gia ngày: Oct 2012
Đến từ: T1 K46 Chuyên ĐHSP Hà Nội
Bài gởi: 187
Thanks: 42
Thanked 192 Times in 101 Posts
Gửi tin nhắn qua Yahoo chát tới Fool's theorem
Bài 5
Chuyển bài toán về thành đếm số dãy nhị phân gồm $m$ số $1$ và $n$ số $0$ là $a_1,...a_{m+n}$ thỏa mãn với mọi $i \in {1,2,...,m+n}$ thì dãy con $a_1,a_2,...,a_i$ chứa nhiều số $1$ hơn hoặc bằng số $0$. Gọi dãy như vậy là dãy có tính chất “đẹp”
Đầu tiên ta có dãy nhị phân gồm $m$ số $1$ và $n$ số $0$ là $a_1,...a_{m+n}$ là số cách chọn $m$ vị trí cho số 1 trong $m+n$ vị trí và bằng $ \binom{m+n}{m} $
Tiếp theo ta có nhận xét là
Xét một nhị phân gồm $m$ số $1$ và $n$ số $0$ là $a_1,...a_{m+n}$, dãy này có $m+n$ hoán vị vòng quanh trên đường tròn ($a_1,...a_{m+n}$, $a_2,a_3...a_{m+n},a_1$, $a_3,a_4...a_{m+n},a_1,a_2$,...)
Số hoán vị vòng quanh có tính chất “đẹp” là $m-n$
Thật vậy xếp dãy $a_1,...a_{m+n}$ lên vòng tròn, các hoán vị vòng quanh được lấy theo chiều kim đồng hồ. Ta sẽ bỏ các cặp $1,0$ (Số $1$ đứng trước số $0$ theo chiều kim đồng hồ). Việc này không ảnh hưởng đến tính “đẹp” của các hoán vị vòng quanh và do không có hoán vị “đẹp” nào bắt đầu bằng số $0$ nên việc bỏ các cặp này không ảnh hưởng đến số hoán vị “đẹp”. Do $m \geq n $ nên luôn có ít nhất 1 cặp như vậy và ta cứ bỏ đến khi nào còn $m-n$ số $1$ và không còn số $0$, tức là ta có $m-n$ hoán vị đẹp.
Áp dụng NX này vào thì số dãy thỏa mãn là $\frac{m-n}{m+n} \binom{m+n}{m}$ (Nếu xét gộp tất cả các dãy trùng nhau qua hoán vị vòng quanh thành 1 dãy thì có $\frac{1}{m+n} \binom{m+n}{m}$ dãy, mỗi dãy như vậy khi xét các hoán vị vòng quanh thì sinh ra $m-n$ dãy “đẹp”)
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 
__________________
Hope against hope.

thay đổi nội dung bởi: Fool's theorem, 28-01-2014 lúc 02:16 PM
Fool's theorem is offline   Trả Lời Với Trích Dẫn
 
[page compression: 9.45 k/10.58 k (10.64%)]