[ptnkmt11]

Nguyên văn bở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”)

Hi Fool's theorem,

Lời giải của bạn có 2 sai lầm

1/Dãy đẹp theo định nghĩa của bạn chưa chắc thỏa mãn điều kiện "BTC sẽ đủ tiền thối", một dãy đẹp là một dãy tại bất cứ vị trí a_i nào trong dãy thì số các số 1 phải lớn hơn số các số 0.

2/ Cách xếp theo hàng dọc không có bị lặp khi xếp m người có 100k và n người có 50k do đó cũng không cần chia (m+n).

Thân
------------------------------

Nguyên văn bởi NguyễnTiếnLHP

Không bác nào làm thử bài hình à? mải vui Tết hết rồi

Từ từ bạn, nhiều bạn từ ngày 30 mới được nghỉ học ở nhà giải toán mà
------------------------------

Nguyên văn bởi huynhcongbang

Theo anh biết thì đây là bài toán quen thuộc còn có tên là bài toán bầu cử. Tuy nhiên, có vẻ như bản chất 2 bài là khác nhau vì bài này cần tính đến thứ tự: phiếu bầu ở bài kia thì giống nhau, các bits nhị phân trong cách đếm kiểu Catalan ở trên thì giống nhau nhưng bài số 5 ở trên lại có tính đến thứ tự nên không làm vậy được.

Chẳng hạn cho $n=1$ thì số cách xếp theo công thức trên sẽ ra là 1. Tuy nhiên, chính xác phải là $m!$. Nếu $n=0$ thì lại càng có vấn đề.

Theo anh biết đáp số bài này là:

$S(m,n)=m!n!f(m,n)$ trong đó $f(m,n)$ xác định bởi:
$f(0,0)=0, f(m,0) = 1$ và $f(m,n) = f(m-1,n) + \sum_{i=1}^{m} f(m,i-1)$.

Đáp số hình như không phức tạp vậy.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]