Câu 5. (3,0 điểm) Lớp chuyên Toán 11T có 35 học sinh. Thầy giáo chủ nhiệm muốn tổ chức chương trình trải nghiệm gồm bốn chuyến đi khác nhau sao cho mỗi học sinh trong lớp phải tham gia ít nhất một chuyến đi.
a) Tính số cách để thầy giáo chủ nhiệm thực hiện chương trình trải nghiệm đó.
b) Nếu có thêm điều kiện: Với mỗi $k\in \{2;3;4\}$, trong chuyến đi thứ $k$ phải có ít nhất một học sinh đã tham gia chuyến đi thứ $k-1$ thì thầy giáo chủ nhiệm có bao nhiêu cách thực hiện chương trình trải nghiệm đó.

(AI giải đề cho tôi)
Mỗi học sinh chọn một tập con khác rỗng của $\{1,2,3,4\}$ (các chuyến đi anh ấy tham gia), nên mỗi em có $2^4-1=15$ lựa chọn.

a) Số cách: $15^{35}$.

b) Gọi $A_k$ là biến cố 'không có học sinh nào tham gia cả chuyến $k-1$ và chuyến $k$' ($k=2,3,4$). Cần đếm các cách gán không xảy ra $A_2\cup A_3\cup A_4$, dùng bao hàm – loại trừ.

- $|A_k|$: mỗi học sinh phải tránh cặp $\{k-1,k\}$. Số tập con khác rỗng của $\{1,2,3,4\}$ không chứa cả hai phần tử của một cặp cho trước: $15-4=11$ (các tập chứa cả hai phần tử của cặp: $2^2=4$). Vậy $|A_k|=11^{35}$, có 3 biến cố.

- $|A_k\cap A_l|$ với hai cặp kề nhau (chẳng hạn $\{1,2\}$ và $\{2,3\}$): đếm tập con khác rỗng tránh cả hai cặp: không chứa 2: $2^3-1=7$; chứa 2 thì chỉ được ghép với 4: $\{2\},\{2,4\}$: 2. Tổng $9$. Vậy $9^{35}$, có $\left(\genfrac{}{}{0ex}{}{3}{2}\right)=3$ cặp.

- $|A_2\cap A_3\cap A_4|$: tránh cả ba cặp $\{1,2\},\{2,3\},\{3,4\}$: không có 2,3: $2^2-1=3$; có 2 không 3: $\{2\},\{2,4\}$: 2; có 3 không 2: $\{3\},\{1,3\}$: 2; có cả 2,3: bị cấm. Tổng $7$. Vậy $7^{35}$.

Kết quả:
$$N=15^{35}-3\cdot 11^{35}+3\cdot 9^{35}-7^{35}.$$