Cho tập A = {1, 2, 3, 4}. Trong các quan hệ trên tập A cho dưới đây, quan hệ nào là quan hệ tương đương?

Hoán vị kế tiếp của một hoán vị được tìm bằng cách:
1. Tìm từ phải sang trái vị trí i đầu tiên mà a[i] < a[i+1]. Nếu không tồn tại, đây là hoán vị cuối cùng.
2. Tìm từ phải sang trái vị trí j đầu tiên mà a[j] > a[i].
3. Đổi chỗ a[i] và a[j].
4. Đảo ngược đoạn từ i+1 đến cuối mảng.

Trong trường hợp này, hoán vị hiện tại là 2 1 3 4 5 6 7 8 9.

Bước 1: Tìm từ phải sang trái, vị trí i đầu tiên mà a[i] < a[i+1]. Ta thấy vị trí i = 2 (với a[2] = 1) thỏa mãn điều kiện (vì 1 < 3).
Bước 2: Tìm từ phải sang trái, vị trí j đầu tiên mà a[j] > a[i] (tức là a[j] > 1). Ta thấy vị trí j = 3 (với a[3] = 3) thỏa mãn điều kiện.
Bước 3: Đổi chỗ a[i] và a[j], tức là đổi chỗ 1 và 3. Hoán vị trở thành: 2 3 1 4 5 6 7 8 9.
Bước 4: Đảo ngược đoạn từ i+1 đến cuối mảng, tức là đảo ngược đoạn từ vị trí 3 đến vị trí 9 (1 4 5 6 7 8 9). Vì đoạn này đã sắp xếp tăng dần, sau khi đảo ngược sẽ thành giảm dần. Tuy nhiên, trong trường hợp này ta không cần đảo ngược gì cả vì đoạn sau vị trí i+1 (tức vị trí 3) đã được sắp xếp tăng dần.

Vậy hoán vị kế tiếp là 2 3 1 4 5 6 7 8 9.

Thuật toán đệ quy là một phương pháp giải quyết vấn đề bằng cách chia nhỏ bài toán lớn thành các bài toán con có cấu trúc tương tự, cho đến khi đạt được một bài toán cơ sở đủ đơn giản để giải trực tiếp. Quá trình này bao gồm việc gọi lại chính hàm đó với dữ liệu đầu vào nhỏ hơn hoặc đơn giản hơn. Đáp án C mô tả chính xác cách thức hoạt động của thuật toán đệ quy, trong đó bài toán ban đầu được rút gọn liên tiếp tới một bài toán tương tự nhưng có dữ liệu đầu vào nhỏ hơn.

Các phương án khác không mô tả chính xác bản chất của đệ quy:
- Phương án A đúng một phần, nhưng không nhấn mạnh việc bài toán con phải "giống như vậy".
- Phương án B và D đề cập đến việc chia đôi hoặc dữ liệu đầu vào bằng một nửa, đây là một trường hợp đặc biệt của đệ quy (ví dụ: tìm kiếm nhị phân) chứ không phải là định nghĩa tổng quát.

Nguyên lý Dirichlet (hay còn gọi là nguyên lý chuồng bồ câu) phát biểu rằng nếu có N đồ vật được đặt vào K hộp, thì sẽ tồn tại ít nhất một hộp chứa ít nhất [N/K] đồ vật, trong đó [x] là hàm ceiling (lấy số nguyên nhỏ nhất lớn hơn hoặc bằng x). Do đó, đáp án B là đáp án chính xác. Các đáp án còn lại là các công thức liên quan đến số phần tử của tập hợp, nhưng không phải là nguyên lý Dirichlet.

Nguyên lý bù trừ (hay còn gọi là nguyên lý bao hàm - loại trừ) cho hai tập hợp hữu hạn A và B phát biểu rằng: Số phần tử của hợp hai tập hợp A và B bằng tổng số phần tử của A cộng với số phần tử của B trừ đi số phần tử của giao hai tập hợp A và B. Công thức: N(A ∪ B) = N(A) + N(B) - N(A ∩ B). Trong các đáp án đã cho, chỉ có đáp án C thể hiện đúng dạng của công thức này, mặc dù ký hiệu "+" trong N(A+B) cuối cùng có thể gây nhầm lẫn, nhưng đây là đáp án gần đúng nhất so với các lựa chọn khác.

Đáp án A đúng khi A và B rời nhau, tuy nhiên đề bài không nói rõ, do đó đáp án A không tổng quát.

Đáp án B sai vì N(A.B) không có nghĩa và tích hai tập hợp không được tính bằng tích số phần tử.

Đáp án D là nội dung của nguyên lý Dirichlet (hay còn gọi là nguyên lý chuồng chim bồ câu).

Từ "success" có 7 chữ cái, trong đó chữ 's' xuất hiện 3 lần và chữ 'c' xuất hiện 2 lần. Các chữ cái còn lại ('u', 'e') xuất hiện 1 lần. Số lượng xâu khác nhau có thể tạo thành bằng cách hoán vị các chữ cái này được tính theo công thức:

Số hoán vị = 7! / (3! * 2! * 1! * 1!) = (7 * 6 * 5 * 4 * 3 * 2 * 1) / ((3 * 2 * 1) * (2 * 1))
= 5040 / (6 * 2) = 5040 / 12 = 420

Vậy, có 420 xâu khác nhau có thể nhận được bằng cách sắp xếp lại các chữ cái của từ success.