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

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 bất kì, tập hợp con và tập . Khi đó ánh xạ được gọi là hàm đặc trưng của tập trên nền tập nếu được xác định:
nếu và bằng nếu

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

Với , khi đó

i.

ii.
Trong đó ký hiệu với

iii. nếu

iv.

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 , ta có công thức tổng quát hơn như sau:

v.
Ký hiệu với

Từ iv. và v., suy ra ngay công thức quen thuộc 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ử là các tập con của tập hữu hạn, là tập con của . Đặt , quy ước . Kí hiệu tập hợp các phần tử của không thuộc . Khi đó

Chứng minh

Giả sử thuộc vào tập hợp trong số
Ta có .
Do đó

Tổng này bằng nếu , tức là khi ; và bằng nếu , tức là khi .

Như vậy
Cho nhận các giá trị thuộc tập 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ử là các tập con của tập hữu hạn, là tập con của . Đặt , quy ước . Kí hiệu tập hợp các phần tử thuộc sao cho nó không thuộc tập nào khác mà . Khi đó

Chứng minh

Giả sử thuộc vào , với .

Ta có . Do đó

Tổng này bằng 1 nếu , tức là ; và bằng nếu , tức là khi .
Như vậy
Cho nhận các giá trị thuộc tập 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 . 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 với . Theo PIE ta có:

Trong đó là tập các phần tử của không nằm trong tập nào với , và , quy ước .
Xét tương ứng sao cho . Dế thấy là ánh xạ, hơn nữa là song ánh. Mặc khác , 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 thuộc vào đúng tập hợp trong số

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

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

Điều này được suy ra từ .

Mệnh đề 5. Cho 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 . Khi đó hai công thức sau là tương đương
i.
ii.

Chứng minh

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

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

Nếu chọn với . 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 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 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 . Khi đó hai công thức sau là tương đương
i.
ii.

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 phần tử vào một tập hợp phần tử bằng

2. Chứng tỏ rằng số các song ánh từ vào chính nó sao cho bằng

3. Kí hiệu số các song ánh từ vào chính nó sao cho , . Tính và chứng tỏ .

4. Tìm số các song ánh từ vào chính nó sao cho ,

5. Chứng tỏ rằng số các số nguyên dương không vượt quá mà nguyên tố cùng nhau với bằng với phân tích chính tắc thành thừa số nguyên tố
.

6. Xét là các số thuộc mà nguyên tố cùng nhau với (với n>1). Chứng tỏ rằng
.
Trong đó .

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

Trong đó là các số nguyên tố.

8. Xét là các tập con (có thể rỗng) của . Kí hiệu là số tất cả hoán vị của sao cho

Chứng tỏ rằng

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

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ờ ô 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ự là nghiệm của phương trình sau

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

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

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

12. Tìm số các tập con phần tử sao cho
Trong đó là các số nguyên dương cho trước.

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

a.

b.

14. Cho trước , tìm số các bộ tập con của tập A gồm n phần tử sao cho

15. Với ma trận , kí hiệu là ma trận nhận được sau khi thay các cột thứ bằng cột chỉ chứa các số không, là tích các tổng của các hàng của ma trận , khi đó

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

là tập các song ánh từ vào chính nó.

16. Cho trước là các số nguyên dương. Tìm số các ma trận với các số hạng thuộc 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

  1. hungvuong
    April 20, 2010 at 4:55 am

    Give me a file

  2. Anonymous
    July 31, 2016 at 7:54 am

    lỗi fond chữ -_-

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: