Mỗi ngày một bài toán tổ hợp, xác suất (Câu số 34): Số hoán vị gần tăng của n số nguyên dương đầu tiên

Với mỗi số nguyên $n\ge 2,$ định nghĩa ${{a}_{1}},\text{ }{{a}_{2}},\text{ }...,\text{ }{{a}_{n}}$ là một hoán vị gần tăng của $n$ số nguyên dương đầu tiên nếu ${{a}_{k}}\le {{a}_{k+1}}+2$ với mọi $k=1,\text{ }2,\text{ }...,\text{ }n-1.$ Ví dụ, $5,3,4,2,1$ và $1,4,2,5,3$ là các hoán vị gần tăng của $5$ số nguyên dương đầu tiên, trong khi $4,5,1,2,3$ thì không. Hỏi có bao nhiêu hoán vị gần tăng của $10$ số nguyên dương đầu tiên?

Giải. Gọi ${{u}_{n}}$ là số hoán vị gần tăng của $n$ số nguyên dương đầu tiên: $1,\text{ }2,\text{ }...,\text{ }n.$

Xét hoán vị gần tăng của $n-1$ số nguyên dương đầu tiên: $1,\text{ }2,\text{ }...,\text{ }n-1$ (có ${{u}_{n-1}}$ hoán vị như vậy).

Khi xếp thêm số $n$ vào để được hoán vị gần tăng của $n$ số nguyên dương đầu tiên: $1,\text{ }2,\text{ }...,\text{ }n$ thì $n$ chỉ được xếp vào một trong ba vị trí: đứng ngay trước số $n-2$ hoặc đứng ngay trước số $n-1$ hoặc đứng ngay sau số $n-1.$

Do đó ${{u}_{n}}=3{{u}_{n-1}}\Rightarrow {{u}_{n}}={{3}^{n-2}}.{{u}_{2}}={{2.3}^{n-2}}\Rightarrow {{u}_{10}}={{2.3}^{8}}=13\text{ }122.$

Mỗi ngày một bài toán tổ hợp, xác suất (Câu số 33): Xếp các quả bóng vào ba cái thùng sao cho thùng nào cũng chứa lẻ quả bóng