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 |