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}$
