Mỗi ngày một bài toán tổ hợp, xác suất (Câu số 26): Tìm số tập con của một tập hợp không chứa hai số nguyên liên tiếp

Có bao nhiêu tập con $A$ khác rỗng của tập hợp $S=\left\{ 1,2,...,20 \right\}$ thỏa mãn đồng thời hai điều kiện sau:

(a) Không chứa hai số nguyên liên tiếp.

(b) Phần tử nhỏ nhất của $A$ không nhỏ hơn số phần tử của $A$

Giải. Tập con $A$ khác rỗng có $k$ phần tử với $k\ge 1.$

Vì phần tử nhỏ nhất của $A$ không nhỏ hơn số phần tử của $A$ nên các phần tử ${{a}_{1}},{{a}_{2}},...,{{a}_{k}}$ (sắp xếp theo thứ tự tăng dần) của $A$ thuộc $T=\left\{ k,k+1,...,20 \right\}.$

Vì không chứa hai số nguyên liên tiếp nên $k\le {{a}_{1}}<{{a}_{2}}-1<...<{{a}_{k}}-\left( k-1 \right)\le 21-k.$

Giờ ta chỉ cần chọn ra $k$ số từ tập hợp $K=\left\{ k,k+1,...,21-k \right\}$ ta được một tập con thỏa mãn.

Ta có điều kiện $k<21-k$ và $\left( 21-k \right)-k+1\ge k\Rightarrow k\in \left\{ 1,2,...,7 \right\}.$

Vậy số tập con thỏa mãn là $\sum\limits_{k=1}^{7}{C_{22-2k}^{k}}=\sum\limits_{k=1}^{7}{\dfrac{\left( 22-2k \right)!}{k!\left( 22-3k \right)!}}=2744.$

Mỗi ngày một bài toán tổ hợp, xác suất (Câu số 25): Bốn con kiến di chuyển trên các cạnh của một khối tứ diện đều