Câu hỏi 43
Cho dãy số nguyên $x_1,x_2,\ldots,x_k$. Một cách sắp xếp lại dãy này (viết các số của dãy theo một thứ tự khác) được gọi là một hoán vị tránh vị trí nếu không số nào trong dãy mới bằng số ban đầu ở vị trí đó. Chẳng hạn, nếu dãy ban đầu là $1,3,3,5$ thì $3,5,1,3$ là một hoán vị tránh vị trí, còn $3,3,1,5$ thì không.
Một cách sắp xếp lại được gọi là kiểu “hai-hai” nếu có đúng hai số trong dãy mới, mỗi số lớn hơn đúng hai đơn vị so với số ban đầu ở vị trí ấy. Ví dụ, $3,5,1,3$ là một cách kiểu “hai-hai” của dãy $1,3,3,5$ (hai giá trị đầu tiên $3$ và $5$ của dãy mới lớn hơn đúng hai đơn vị so với các giá trị ban đầu $1$ và $3$).
Cho $n\ge 2$. Chứng minh số hoán vị tránh vị trí của
$$1,1,2,3,\ldots,n-1,n$$
bằng số cách sắp xếp kiểu “hai-hai” của
$$1,2,3,\ldots,n,n+1.$$
(Lưu ý cả hai dãy đều có $n+1$ số, nhưng dãy thứ nhất chứa hai số $1$.)
Một cách sắp xếp lại được gọi là kiểu “hai-hai” nếu có đúng hai số trong dãy mới, mỗi số lớn hơn đúng hai đơn vị so với số ban đầu ở vị trí ấy. Ví dụ, $3,5,1,3$ là một cách kiểu “hai-hai” của dãy $1,3,3,5$ (hai giá trị đầu tiên $3$ và $5$ của dãy mới lớn hơn đúng hai đơn vị so với các giá trị ban đầu $1$ và $3$).
Cho $n\ge 2$. Chứng minh số hoán vị tránh vị trí của
$$1,1,2,3,\ldots,n-1,n$$
bằng số cách sắp xếp kiểu “hai-hai” của
$$1,2,3,\ldots,n,n+1.$$
(Lưu ý cả hai dãy đều có $n+1$ số, nhưng dãy thứ nhất chứa hai số $1$.)