Có N phần tử cần chia thành 2 cụm, mỗi cụm có ít nhất 1 phần tử. Công thức nào sau đây cho ta tổng số cách chia cụm: 

Câu hỏi yêu cầu tìm công thức tính số cách chia N phần tử thành 2 cụm, mỗi cụm có ít nhất 1 phần tử. Phân tích các phương án: * **Phương án a: S(N,2) = 2^N - 1** * Tổng số tập con của một tập N phần tử là 2^N. Tuy nhiên, trong đó bao gồm cả tập rỗng và chính tập N phần tử. Để chia thành 2 cụm, ta cần loại trừ trường hợp tập rỗng. Vì mỗi cách chia như vậy sẽ có một cách chia đối xứng (đảo ngược vai trò 2 cụm), do đó ta cần chia đôi kết quả. Tuy nhiên, công thức này vẫn không chính xác vì nó không loại trừ việc một trong hai cụm rỗng. * **Phương án b: S(N,2) = 2^(N-1)** * Xét một tập hợp N phần tử. Để chia thành hai cụm, ta có thể duyệt qua từng phần tử. Với mỗi phần tử, ta có 2 lựa chọn: hoặc là cho vào cụm thứ nhất, hoặc là cho vào cụm thứ hai. Như vậy, tổng số cách chia là 2^N. Tuy nhiên, cách chia này tính cả trường hợp tất cả các phần tử đều thuộc cụm thứ nhất hoặc tất cả các phần tử đều thuộc cụm thứ hai (tức là một cụm rỗng). Vì mỗi cụm phải có ít nhất 1 phần tử, ta cần trừ đi 2 trường hợp này. Số cách chia sẽ là (2^N - 2) / 2 = 2^(N-1) - 1. Do đó, phương án này chưa chính xác. * **Phương án c: S(N,2) = 2^(N-1) - 1** * Cách giải thích tương tự như phương án b, nhưng đã trừ đi các trường hợp cụm rỗng và chia đôi để tránh trùng lặp. Đây là đáp án chính xác. * **Phương án d: S(N,2) = 2^N** * Phương án này tính tất cả các tập con, bao gồm cả trường hợp tập rỗng và không chia đôi để loại bỏ các cách chia trùng lặp. Vậy, đáp án đúng là: S(N,2) = 2^(N-1) - 1