C++ Hoán vị n lấy r với k phần tử luôn liền nhau

Cho n, r, k. Tìm số cách chọn r phần tử từ n sao cho k phần tử cụ thể luôn xuất hiện liền nhau. Ví dụ:

Input: n=8, r=5, k=2 → Output: 960
Input: n=6, r=2, k=2 → Output: 2

Phương pháp giải

Xét k phần tử liền nhau như một "siêu phần tử". Ta có (r-k+1) vị trí đặt khối này trong r vị trí. Số cách sắp xếp trong khối: k!. Số cách chọn (r-k) phần tử còn lại từ (n-k) phần tử: P(n-k, r-k). Công thức:

Kết quả = k! × (r-k+1) × P(n-k, r-k)

Ví dụ minh họa

#include <bits/stdc++.h>
using namespace std;

int fact(int n) {
    if (n <= 1) return 1;
    return n * fact(n-1);
}

int npr(int n, int r) {
    return fact(n) / fact(n-r);
}

int countPermutations(int n, int r, int k) {
    return fact(k) * (r - k + 1) * npr(n - k, r - k);
}

int main() {
    int n = 8, r = 5, k = 2;
    cout << countPermutations(n, r, k);
    return 0;
}

Kết quả

960

Giải thích

Công thức: k! (sắp xếp trong khối) × (r-k+1) (vị trí đặt khối) × P(n-k, r-k) (chọn và sắp xếp phần còn lại).

Kết luận

Đã giải bài toán hoán vị n lấy r với k phần tử liền nhau bằng công thức tổ hợp. Code C++ chuyển được sang C, Java, Python. Hy vọng hữu ích.