Combinatorics

Nguyên lý Bao hàm-Loại trừ


Tiếp tục các chuyên đề về các phương pháp trong toán học rời rạc và tổ hợp, ta sẽ bàn một cách tổng quan về nguyên lý bao hàm loại trừ (The Principle of Inclusion and Exclusion – PIE). Ngoài một vài bài toán đã khá kinh điển ta sẽ đưa ra nhiều kết quả mới từ một số đề thi và các sách bài tập tổ hợp, các tạp chí…

Một vài đẳng thức cơ bản của PIE:

Xét tập hợp X bất kì, tập hợp con A\subset X và tập I=\{0,1\}. Khi đó ánh xạ \chi_A : X\rightarrow I được gọi là hàm đặc trưng của tập A trên nền tập X nếu được xác định:
\chi_{A}(x)= 1 nếu x\in A và bằng 0 nếu x\in \overline{A}=X\setminus A

Không khó khăn để kiểm chứng:

Với A, B\subset X, khi đó

i. \chi_{\overline{A}}=1-\chi_{A}

ii. \chi_{A\cap B}=\chi_{A}\chi_{B}=\chi_{A}\wedge\chi_{B}
Trong đó ký hiệu (f\wedge g)(x)=\min\{f(x),g(x)\} với x\in D_f\cap D_g

iii. \chi_{A\cup B}=\chi_{A}+\chi_{B} nếu A\cap B=\emptyset

iv. |A|=\displaystyle\sum_{x\in X}{\chi_A(x)}

Từ iv. cho ta nhận xét rằng, để chứng tỏ hai tập hợp có số phần tử bằng nhau thì ta xét đến sự bằng nhau của hai hàm đặc trưng ứng với hai tập đó. Cách nhìn ở đây đã chuyển từ góc độ tập hợp sang hàm số.

Từ iii., không cần điều kiện A\cap B=\emptyset, ta có công thức tổng quát hơn như sau:

v. \chi_{A\cup B}=\chi_{A}+\chi_{B}-\chi_{A\cap B}=\chi_{A}\vee\chi_{B}
Ký hiệu (f\vee g)(x)=\max\{f(x),g(x)\} với x\in D_f\cap D_g

Từ iv. và v., suy ra ngay công thức quen thuộc |A\cup B|=|A|+|B|-|A\cap B| sự tổng quát của công thức này và ứng dụng của nó chính là điều chúng ta đang xét trong bài viết này

Ta sẽ duyệt lại các công thức PIE mà đã phát biểu ở phần trên

Mệnh đề 1. Giả sử A_1, A_2,..., A_n là các tập con của tập X hữu hạn, I là tập con của \{1,2,...,n\}=[n]. Đặt

\displaystyle A_I=\bigcap_{i\in I}{A_i},

quy ước A_{\emptyset}=X. Kí hiệu tập hợp các phần tử của X không thuộc A_IE_{\emptyset}. Khi đó

\displaystyle|E_{\emptyset}|=\sum_{I\subset [n]}{(-1)^{|I|}|A_I|}.

Chứng minh

Giả sử x\in X thuộc vào k tập hợp trong số A_1, A_2,..., A_n
Ta có

\displaystyle\sum_{|I|=r}{\chi_{A_I}(x)}=C_k^r.

Do đó

\displaystyle\sum_{I\subset[n]}{(-1)^{|I|}\chi_{A_I}(x)}=\sum_{r=0}^n\sum_{|I|=r}(-1)^r\chi_{A_I}(x) \displaystyle=\sum_{r=0}^n(-1)^r\sum_{|I|=r}\chi_{A_I}(x)=\sum_{r=0}^n(-1)^r{C_k^r}.

Tổng này bằng 1 nếu k=0, tức là khi \displaystyle x \in E_{\emptyset}; và bằng (1-1)^k=0 nếu k\neq 0, tức là khi x\in \overline{E_{\emptyset}}.

Như vậy

\sum_{I\subset [n]}{(-1)^{|I|}\chi_{A_I}(x)}=\chi_{E_{\emptyset}}(x), \ \forall x\in X.

Cho x nhận các giá trị thuộc tập X và lấy tổng. Từ tính chất iv. suy ra điều phải chứng minh.

Phát biểu của mệnh đề gọi là Nguyên Lý Bao hàm-Loại trừ, tiếng Anh là Principle of Inclusion-Exclusion – PIE, tiếng Nga là Принцип включения-исключения

Tiếp theo là một sự tổng quát

Mệnh đề 2. Giả sử A_1, A_2,..., A_n là các tập con của tập X hữu hạn, I là tập con của \{1,2,...,n\}=[n]. Đặt

\displaystyle A_I=\bigcap_{i\in I}{A_i},

quy ước A_{\emptyset}=X. Kí hiệu tập hợp các phần tử thuộc A_I sao cho nó không thuộc tập A_i nào khác mà i\notin IE_I . Khi đó

|E_I|=\sum_{J\supset I}(-1)^{|J\setminus I|}|A_J|.

Chứng minh

Giả sử x\in X thuộc vào A_{J'}, J'\supset I, với |I|=m|J'|=m+k.

Ta có

\displaystyle\sum_{J\supset I, |J|=m+r}\chi_{A_J}(x)=C^{r}_{k}.

Do đó

\displaystyle\sum_{J\supset I}(-1)^{|J\setminus I|}\chi_{A_J}(x)=\sum_{r=0}^{n-m}\sum_{J\supset I, |J|=m+r}(-1)^r\chi_{A_J}(x) \displaystyle=\sum_{r=0}^{n-m}(-1)^r\sum_{J\supset I, |J|=m+r}\chi_{A_J}(x) \displaystyle=\sum_{r=0}^{n-m}(-1)^rC^{r}_{k}

Tổng này bằng 1 nếu k=0, tức là x\in E_I; và bằng (1-1)^{k}=0 nếu k\neq 0, tức là khi x\in \overline{E_I}.
Như vậy

\sum_{J\supset I}(-1)^{|J\setminus I|}\chi_{A_J}(x)=\chi_{E_I}(x), \ \forall x\in X

Cho x nhận các giá trị thuộc tập X và lấy tổng ta thu được điều phải chứng minh.

Mềnh đề 1 là trường hợp đặc biệt khi lấy I=\emptyset. Ta gọi kết quả này là PIE tổng quát.

Tuy nhiên bản thân nó là tương đương với PIE, nghĩa là nó cũng có thể suy ra từ mệnh đề

1. Thật vậy, xét các tập B_j=A_{I\cup\{j\}} với j\in [n]\setminus I. Theo PIE ta có:

\displaystyle|E'_{\emptyset}|=\sum_{J\subset [n]\setminus I}(-1)^{|J|}|B_J|

Trong đó E'_{\emptyset} là tập các phần tử của A_I không nằm trong tập B_j nào với j\in [n]\setminus I, và

\displaystyle B_J=\bigcap_{j\in J}B_j, quy ước B_{\emptyset}=A_I.

Xét tương ứng \phi:\mathcal{P}([n]\setminus I)\rightarrow \{K\subset [n] \ | \ K\supset I\} sao cho \phi(J)=J\cup I. Dế thấy \phi là ánh xạ, hơn nữa là song ánh. Mặc khác B_{J}=A_{J\cup I}, do đó ta có kết quả của mệnh đề 2.

Hệ quả sau được suy ra trực tiếp từ mệnh đề 2:

Mệnh đề 3. Số phần tử của X thuộc vào đúng m tập hợp trong số A_1, A_2,..., A_n

\displaystyle\mathbf{N}_m=\sum_{m\le|J|\le n}(-1)^{|J|-m}C_{|J|}^m|A_J|.

Nếu chọn m bằng 0, lại thu được PIE.

Mệnh đề 4. Số phần tử của X thuộc vào đúng không ít hơn m tập trong số A_1, A_2, ..., A_n

\overline{\mathbf{N}}_m=\sum_{m\le|J|\le n}(-1)^{|J|-m}C_{|J|-1}^{m-1}|A_J|.

Điều này được suy ra từ \overline{\mathbf{N}}_{m+1}=\overline{\mathbf{N}}_{m}-\mathbf{N}_m.

Mệnh đề 5. Cho f, g là một hàm tập nhận giá trị thực xác định với mỗi tập con của [n]. Khi đó hai công thức sau là tương đương
i. \displaystyle f(I)=\sum_{J\supset I}g(J).
ii. \displaystyle g(I)=\sum_{J\supset I}(-1)^{|J\setminus I|}f(J).

Chứng minh

Giả sử (i.) thỏa mãn, ta có

\displaystyle\sum_{J\supset I}(-1)^{|J\setminus I|}f(J)=\sum_{J\supset I}(-1)^{|J\setminus I|}\sum_{K\supset J}g(K)=\sum_{J\supset I}\sum_{K\supset J}(-1)^{|J\setminus I|}g(K)

\displaystyle=\sum_{K\supset I}g(K)\sum_{K\supset J\supset I}(-1)^{|J\setminus I|}=g(I)

Ngược lại, giả sử (ii.) thỏa mãn thì

\displaystyle\sum_{J\supset I}g(J)=\sum_{J\supset I}\sum_{K\supset J}(-1)^{|K\setminus J|}f(K)=\sum_{K\supset I}f(K)\sum_{K\supset J\supset I}(-1)^{|K\setminus J|}=f(I)

Nếu chọn S=[n]f(I)=|A_I|, g(I)=|E_I| với I\subset [n] . Do (i.) hiển nhiên thỏa mãn nên ta có (ii.), chính là nguyên lý PIE tổng quát. Mệnh đề trên cũng lý giải bản chất tại sao mệnh đề 1 lại tương đương với mệnh đề 2.

Xét f'(I)=f([n]\setminus I), g'(I)=f([n]\setminus I) và áp dụng mệnh đề 5, ta có mệnh đề tương đương ứng với sự đổi chiều của quan hệ bao hàm

Mệnh đề 6. Cho f, g là một hàm tập nhận giá trị thực xác định với mỗi tập con của [n]. Khi đó hai công thức sau là tương đương
i. \displaystyle f(I)=\sum_{J\subset I}g(J)
ii. \displaystyle g(I)=\sum_{J\subset I}(-1)^{|J\setminus I|}f(J)

Các bài toán:

1. Chứng tỏ rằng số các toàn ánh từ một tập hợp m phần tử vào một tập hợp n phần tử bằng

\displaystyle\sum_{i=0}^n(-1)^iC_n^i(n-i)^m.

2. Chứng tỏ rằng số các song ánh \sigma từ (1,2,...,n) vào chính nó sao cho \sigma(i)\neq i, \ i=1,2,...,n bằng

D_n=\displaystyle n!\sum_{i=0}^n\frac{(-1)^i}{i!}.

3. Kí hiệu số các song ánh \sigma từ \{1,2,...,n\} vào chính nó sao cho \sigma(i)\neq i+1, i=1,2,...,n-1Q_n. Tính Q_n và chứng tỏ D_n+D_{n-1}=Q_n.

4. Tìm số các song ánh \sigma từ \{1,2,...,n\} vào chính nó sao cho \sigma(i)\notin \{i,i+1\}, i=1,2,...,n-1

5. Chứng tỏ rằng số các số nguyên dương không vượt quá n mà nguyên tố cùng nhau với n bằng

\displaystyle\varphi(n)=n\prod_{i=1}^k(1-\frac{1}{p_k})

với phân tích chính tắc thành thừa số nguyên tố
n={p_1}^{{\alpha}_1}{p_2}^{{\alpha}_2}...{p_k}^{{\alpha}_k}.

6. Xét a_1,a_2,...,a_{\varphi(n)} là các số thuộc \{1,2,...,n\} mà nguyên tố cùng nhau với n (với n>1). Chứng tỏ rằng

\displaystyle\sum_{i=1}^{\varphi(n)}{a_i^2}=\frac{\varphi(n)}{6}(2n^2+(-1)^kp_1p_2...p_k).

Trong đó n={p_1}^{{\alpha}_1}{p_2}^{{\alpha}_2}...{p_k}^{{\alpha}_k}.

7. Kí hiệu p(x) là số các số nguyên tố không vượt quá x. Chứng tỏ

\displaystyle p(n)-p(\sqrt{n})=n-1-\sum_{k=1}^{p(\sqrt{n})}(-1)^{k-1}\sum_{2\le p_1<...<p_k\le\sqrt{n}}[\frac{n}{p_1p_2...p_k}].

Trong đó p_1, p_2, p_3,... là các số nguyên tố.

8. Xét S=\{1,2,...,n\}X_1,X_2,...,X_n là các tập con (có thể rỗng) của S. Kí hiệu p(X_1,X_2,...,X_n) là số tất cả hoán vị (a_1,a_2,...,a_n) của S sao cho
a_1\notin X_1, a_2\notin X_2,...,a_n\notin X_n

Chứng tỏ rằng

\displaystyle p(X_1,X_2,...,X_n)=\sum_{k=0}^n(-1)^kr_k(n-k)!.

Trong đó r_k là số các sắp đặt k quân xe lên bàn cờ n\times n ô sao cho chúng không ăn lẫn nhau và quân xe thứ k ở vào vị trí (k,x_k) với x_k\in X_k.

Bằng cách sử dụng các “quân xe” hãy giải lại bài 2,3,4.

9. Tìm số sắp đặt các quân xe lên bàn cờ 2n\times 2n ô sao cho không có hai quân xe nào ăn nhau và chúng không nằm trên 2 đường chéo chính của bàn cờ.

10. Tìm số các bộ có thứ tự (x_1,x_2,...,x_m) là nghiệm của phương trình sau

x_1+x_2+...+x_m=p

với 1\le x_i\le n,\ i=1,2,...,m. Trong đó m,n,p là các số nguyên dương cho trước.

11. Tìm số các bộ có thứ tự (x_1,x_2,...,x_m) là nghiệm của phương trình đồng dư sau

x_1+x_2+...+x_m\equiv0 \ (\text{mod} \ p)

với 1\le x_i\le n,\ i=1,2,...,m. Trong đó m,n,p là các số nguyên dương cho trước.

12. Tìm số các tập con m phần tử \{x_1,x_2,...,x_m\}\subset\{1,2,...,n\} sao cho

x_1+x_2+...+x_m\equiv0 \ (\text{mod} \ p)

Trong đó m,n,p là các số nguyên dương cho trước.

13. Kí hiệu E(m,n,p) là số các cách sắp xếp m đồ vật khác nhau vào n chiếc hộp khác nhau, sao cho có đúng p chiếc hộp không có đồ vật nào. Kí hiệu F(m,n,p) là số cách sắp xếp m đồ vật khác nhau vào n chiếc hộp khác nhau, sao cho có không ít hơn p chiếc hộp không có đồ vật nào. Chứng tỏ rằng

a. \displaystyle E(m,n,p)=C_n^p\sum_{k=0}^{n-p}(-1)^kC^k_{n-p}(n-p-k)^m

b. \displaystyle E(m,n,p)=C_n^p\sum_{k=0}^{n-p}(-1)^kC^k_{n-p}(n-p-k)^m\frac{p}{p+k}

14. Cho trước n\ge k\ge 1, tìm số các bộ tập con (A_1, A_2,..., A_k) của tập A gồm n phần tử sao cho A_i\cap A_j=\emptyset|A_i|\neq \emptyset

15. Với ma trận A=(a_{ij})_m, kí hiệu A_{i_1,i_2,...,i_k} là ma trận nhận được sau khi thay các cột thứ i_1,i_2,...,i_k bằng cột chỉ chứa các số không,

\displaystyle S(X)= \prod_{i=1}^n \sum_{k=1}^n a_{ik}

là tích các tổng của các hàng của ma trận X=(x_{ij}). Chứng minh rằng khi đó

\displaystyle \text{per}(A)=S(A)+\sum_{k=1}^m(-1)^k\sum_{1\le i_1<...<i_k\le m} S(A_{i_1,i_2,...,i_k}).

Trong đó permanent của ma trận A kí hiệu là

\displaystyle\text{per}(A)=\sum_{\sigma\in S_n}a_{1\sigma(1)}a_{2\sigma(2)}...a_{m\sigma(m)},

với S_n là tập các song ánh từ \{1,2,...,n\} vào chính nó.

16. Cho trước m,n,p là các số nguyên dương. Tìm số các ma trận m\times n với các số hạng thuộc \{1,2,...,p\} sao cho tổng các số hạng ở mỗi hàng và mỗi cột đều không chia hết cho p.