## Mở đầu
Đây là bài toán mở rộng của [Derangement](https://en.wikipedia.org/wiki/Derangement). Để mà quen vơi Derangement thì ta phải làm bài [Distributing Apples](https://cses.fi/problemset/task/1716) trước.
**Derangement được định nghĩa là:**
> *Những hoán vị sao cho $ \forall x_i$ đều không nằm ở vị trí $i$*
Và để làm bài *Distributing Apples* thì ta có hai cách giải đó là **dùng bao hàm loại trừ** hoặc **quy hoạch động**
Mình xin chỉ trình bày cách giải cách làm bằng bao hàm loại trừ. Còn cách làm bằng quy hoạch động thì các bạn có thể xem trên [USACO](https://usaco.guide/gold/combo)
## Hướng giải cho bài *Distributing Apples*
Xét tập hợp $P = {p_1, p_2, \ldots , p_n}$ với $n$ là số lượng phần tử
- Gọi $d[x]$ là số lượng hoán vị sao cho $\exists x$ số $p_{i_1}, p_{i_2}, \ldots , p_{i_x}$ sao cho $\forall j \in [1, x]$ đều thoả $p_{i_j} = {i_j}$.
- Gọi $A_i$ là tập hợp các hoán vị sao cho $\exists x$ số $p_{i_1}, p_{i_2}, \ldots , p_{i_x}$ sao cho $\forall j \in [1, x]$ đều thoả $p_{i_j} = {i_j}$.
- Thay vì tìm từng hoán vị một. Thì giờ, ta tìm số lượng hoán vị có thể tạo ra được mà **chưa xét điều kiện gì** $\Rightarrow$ số lượng hoán vị sẽ là $n!$
- Và giờ nhiệm vụ của ta là tìm $\sum^n_{t=1}$ số lượng hoán vị mà tồn tại $t$ phần tử $x_i$ thoả $x_i = i$
- Để tìm ra các hoán vị có tồn tại ít nhất $i$ phần tử nằm ở vị trí không hợp lệ ấy. Cách giải ngây thơ của chúng ta đó là:
- Chọn $i$ phần tử $x$ ở vị trí $x \Rightarrow$ có $C^i_n$ cách chọn
- Sau đó các phần tử còn lại thích ở vị trí nào thì tuỳ. Và lúc này, số lượng hoán vị sẽ là $(n - i)!$
- Nếu vậy thì $d[i] = C^i_n \times (n - i)!$
- Nhưng nếu ta sinh bất kì hoán vị nào ở bước hai thì vẫn sẽ phát sinh thêm một vài phần tử **không hợp lệ**
- Và ta nhận ra $A_1 \subset A_2 \subset A_3 \subset \ldots \subset A_n$
- Và để giải quyết vấn đề lồng nhau, áp dụng nguyên lí bao hàm loại trừ, ta có kết quả của bài toán là:
$$
n!+\sum^n_{k= 1} (-1)^k \times d[k]=n!+\sum^n_{k= 1} (-1)^k \times C^k_n\times (n - k)!
$$
## Hướng giải cho bài *Bài toán hoán vị*
- Ta áp dụng nguyên lí tương tự với bài Derangement nhưng ta chỉ cần tính $d[i]$ với $ i \in [1, k]$
- Bên cạnh đó, do chỉ có $k$ phần tử $\in [1, k]$ mới bắt buộc vị trí phải khác giá trị. Còn lại thì tự do
- Nên thay vì ta tính $C^i_n$ thì giờ ta phải tính $C^i_k$
- Và kết quả của bài toán được tính bằng công thức sau:
$$
n!+\sum^k_{i= 1} (-1)^i \times d[i]=n!+\sum^k_{i = 1} (-1)^i \times C^i_k\times (n - i)!
$$
minhpnk2
Created at
1 likes