Question

Cho một lưới gồm các ô vuông. Các nút được đánh số từ 0 đến n theo chiều từ trái sang phải và từ 0 đến m theo chiều từ dưới lên trên. Hỏi có bao nhiêu đường đi khác nhau từ nút (0,0) đến nút (n,m) nếu chỉ cho phép đi trên các cạnh ô vuông theo chiều sang phải hoặc lên trên?

Answer 1

Để đi từ điểm tọa độ (0,0) đến tọa độ (n,m) thì cần n bước qua phải và m bước lên trên, nên cần tổng cộng \(m+n\) bước đi để đến đích.

Chọn m bước lên trên (trong tổng số \(m+n\) bước) có \(C_{m+n}^m\) cách

Còn lại n bước, chọn n cách sang phải, có \(C_n^n\) cách

Vậy tổng cộng có: \(C_{m+n}^m.C_n^n=C_{m+n}^n\) cách