Đến nội dung


Hình ảnh

Số cách tịnh tiến $n$ quân tốt đi $m$ ô


  • Please log in to reply
Chưa có bài trả lời

#1 hxthanh

hxthanh

  • Thành viên
  • 3327 Bài viết
  • Giới tính:Nam

Đã gửi 16-11-2013 - 23:37

Một "bàn cờ" kích thước $1\times (m+n)$ ô. Có $n$ quân tốt đứng ở $n$ ô đầu tiên của bàn cờ. Cần phải tịnh tiến $n$ quân tốt đến $n$ ô cuối cùng (mỗi quân tiến $m$ bước). Mỗi bước đi chỉ được phép di chuyển 1 quân tốt bất kỳ tiến 1 ô về phía cuối bàn cờ nhưng không được "dẫm đạp" lên quân tốt khác. Gọi $S(n,m)$ là số cách di chuyển $n$ quân tốt tịnh tiến $m$ bước.

Chứng minh rằng: $$S(n,m)=\frac{1!2!...(n-1)!}{m!(m+1)!...(m+n-1)!}\times(mn)!$$

 

Ví dụ: $S(2,3)=\dfrac{1!}{3!4!}\times (2.3)!=5$

 

$\begin{matrix}\begin{array}{|c|c|c|c|c|} \hline \circ&\circ&\;&\;&\;\\ \hline\end{array} & &\\ \downarrow & &\\ \begin{array}{|c|c|c|c|c|} \hline \circ&\;&\circ&\;&\;\\ \hline\end{array} & &\\ \downarrow & \searrow & \\ \begin{array}{|c|c|c|c|c|} \hline \circ&\;&\;&\circ&\;\\ \hline\end{array} & &\begin{array}{|c|c|c|c|c|} \hline \;&\circ&\circ&\;&\;\\ \hline\end{array}\\ \downarrow & \searrow & \downarrow\\ \begin{array}{|c|c|c|c|c|} \hline \circ&\;&\;&\;&\circ\\ \hline\end{array} & &\begin{array}{|c|c|c|c|c|} \hline \;&\circ&\;&\circ&\;\\ \hline\end{array}\\ \downarrow & \swarrow & \downarrow \\ \begin{array}{|c|c|c|c|c|} \hline \;&\circ&\;&\;&\circ\\ \hline\end{array} & &\begin{array}{|c|c|c|c|c|} \hline \;&\;&\circ&\circ&\;\\ \hline\end{array}\\ \downarrow & \swarrow &  \\ \begin{array}{|c|c|c|c|c|} \hline \;&\;&\circ&\;&\circ\\ \hline\end{array} & &\\  \downarrow & &\\ \begin{array}{|c|c|c|c|c|} \hline \;&\;&\;&\circ&\circ\\ \hline\end{array} & &\end{matrix}$


Cuộc sống thật nhàm chán! Ngày mai của ngày hôm qua chẳng khác nào ngày hôm qua của ngày mai, cũng như ngày hôm nay vậy!




0 người đang xem chủ đề

0 thành viên, 0 khách, 0 thành viên ẩn danh