Trên bàn cờ 5 x 4 ô vuông như hình vẽ, người chơi chỉ được di chuyển quân theo

Trên bàn cờ 5 x 4 ô vuông như hình vẽ, người chơi chỉ được di chuyển quân theo các cạnh của hình vuông, mỗi bước đi được 1 cạnh. Có bao nhiêu cách di chuyển quân từ điểm A tới điểm B bằng 9 bước ?

Trả lời

Để đi từ A đến B qua 9 bước thì chỉ có 1 cách đi duy nhất là các bước đi đều phải đi từ dưới lên hoặc đi từ trái qua phải.

Gọi M(i; j) là điểm bất kì nằm ở hàng i cột j với $i=\overline{1;5}$ và _{$j=\overline{1;6}$}.

Để đến được điểm M thì chỉ có 3 cách đi đó là từ điểm có tọa độ (i − 1; j) hoặc (i; j − 1) như hình vẽ dưới:

Gọi số cách đi đến M là f(i; j) thì theo quy tắc cộng ta có

$f\left(i;j\right)=f\left(i-1;j\right)+f\left(i;j-1\right)$

Từ đó ta được kết quả sau:

Vậy có 126 cách đi thỏa mãn