Tính số bộ $(x_1,x_2,...,x_{m+n})$ thỏa mãn đồng thời các điều kiện sau

Cho $m,n$ là các số nguyên dương mà $m\ge n$.Tính số bộ $(x_1,x_2,...,x_{m+n})$ thỏa mãn đồng thời các điều kiện sau

$\text{i)}$   $x_i\in \left \{ -1,1 \right \}\ \ ,\forall i=\overline{1,m+n}$

$\text{ii)}$  $\sum_{i=1}^k x_i\ge 0\ \ ,\forall k=\overline{1,m+n}$

$\text{iii)}$ $\sum_{i=1}^{m+n}x_i=m-n$

Giải

Từ điều kiện (iii) ta suy ra có đúng $m$ số $1$ và $n$ số $-1$ trong dãy.

Với mỗi cặp $(k, \sum_{i=1}^{k}x_i)$ ta gắn với một điểm trong toạ độ, như vậy là sẽ qui về bài toán sau

Tìm số cách đi từ điểm toạ độ $(0, 0)$ đến điểm toạ độ $(m+n, m-n)$ sau $m+n$ bước đi sao cho trong quá trình đi ta không bước xuống khu vực toạ độ $y$ âm, ở đây với mỗi bước đi ta có thể di chuyển từ $(x,y)$ sang $(x+1, y+1)$ hoặc $(x+1, y-1)$

Để đi từ $(0,0)$ đến $(m+n,m-n)$ ta cần $m+n$ bước (mỗi bước sang phải 1 đơn vị). Cần phải "đi lên" $m$ bước và "đi xuống" $n$ bước.

Chỉ phải chọn $m$ điểm trên hành trình để "đi lên" hoặc $n$ điểm trên hành trình để "đi xuống".

Số cách chọn này chính là $C_{m+n}^m=C_{m+n}^n$

Trong số cách này, với mỗi cách đi mà bước vào khu vực toạ độ $y$ âm, ta tạo 1 song ánh như sau

Xét quá trình từ điểm $(0,0)$ đến điểm đầu tiên bước xuống khu vực toạ độ âm $(x, -1)$, lấy đối xứng tất cả các điểm này qua đường thẳng $y=-1$, ta sẽ được 1 cách đi từ $(0,-2)$ đến $(m+n, m-n)$, và ánh xạ này là song ánh

Suy ra số các cách đi này là $C_{m+n}^{m+1}$

Vậy số bộ thoả mãn là $C_{m+n}^{m} - C_{m+n}^{m+1} = \frac{m+1-n}{m+1}C_{m+n}^{m}$