Archive

Archive for the ‘Combinatorics’ Category

Đếm ma trận {0,1}

May 27, 2010 Leave a comment

Xét hai vector sao cho

Một kết quả quen thuộc là:

Số các ma trận với các số hạng 0,1 sao cho tổng dòng thứ i băng , tổng cột thứ j bằng , kí hiệu là B(s,t), bằng số các đồ thị lưỡng phân (có gán nhãn) với phần thứ nhất gồm m đỉnh với bậc tương ứng là bộ , phần thứ hai có n đỉnh với các bậc tương ứng là

Giả sử là ma trận vơi các số hạng 0,1. Kí hiệu là số các ma trận cấp với các số hạng 0,1 và tổng các hàng, các cột tương ứng là sao cho nếu bằng 1 thì .

Trường hợp đặc biệt thì ko có điều kiện rằng buộc gì nên .

Chú ý rằng tỉ số bằng xác suất chọn ngẫu nhiên một ma trận với các số hạng 0,1 với tổng các hàng, các cột tương ứng là s,t, và ma trận này có các số hạng bằng 0 tại các vị trí mà bằng 1.

Ta kí hiệu có nghĩa là các lấy trên các số hạng có giá trị bằng 1, có nghĩa là các lấy trên các số hạng có giá trị bằng 0.

Để ý rằng chính là hệ số của số hạng chứa trong tích

Thế thì theo công thức Cauchy về hệ số ta có:

ở đây mỗi tích phân lấy theo một đường biên đơn, đóng theo ngược chiều kim đồng hồ.

Advertisements
Categories: Combinatorics

Từ công thức Picard đến công thức Euler

May 27, 2010 2 comments

(Bài này phỏng dịch lại theo các bài viết trên tạp chí Kvant)

Lưới nguyên là tập hợp tất cả các điểm trên mặt phẳng tọa độ Đê-các vuông góc với tọa độ nguyên. Một đa giác gọi là nguyên nếu như tất cả các đỉnh của nó đều thuộc về lưới nguyên . Trong bài này chúng ta sẽ tiếp cận công thức Picard cho diện tích các đa giác nguyên và công thức Euler cũng như chỉ ra mối liên hệ giữa chúng.

I – Tam giác nguyên thủy

Một tam giác nguyên được gọi là nguyên thủy nếu như ngoại trừ các đỉnh của nó thì không có điểm nào nằm trong và trên cạnh tam giác có tọa độ nguyên

s152.photobucket.com/albums/s165/dumb_boy1988/fig001.png
Hình 1.

Định lý 1. Tam giác nguyên là nguyên thủy khi và chỉ khi có có diện tích bằng

Chứng minh.

Cho tam giác nguyên thủy , xét hình chữ nhật nguyên nhỏ nhất với các cạnh song song với các trục tọa độ, chứa tam giác

Tất cả các trường hợp có thể xảy ra biểu diễn như trên hình 2.

s152.photobucket.com/albums/s165/dumb_boy1988/fig002.png
Hình 2.

Trường hợp a., b. rõ ràng tam giác không phải là nguyên thủy vì điểm trên hình vẽ có tọa độ nguyên. Trường hợp bao hàm cả trường hợp c., nếu như giả sử đỉnh có thể nằm trên (trường hợp đặc biệt có thể trùng với . Như vậy ta chỉ cần xét trường hợp , một cách không mất tính tổng quát, xem .

Kí hiệu là số các điểm nguyên nằm bên trong nhưng không nằm trên cạnh của đa giác . Khi đó dễ thấy

Vì trong đoạn không chứa điểm nguyên nên

Tương tự

Tam giác không chứa trong nó điểm nguyên nào nên

ở đây đúng bằng số điểm nguyên nằm trong , và các điểm nguyên nằm trên cạnh , trừ điểm .

Từ đó suy ra

rút gọn ta được

Kí hiệu là diện tích của hình phẳng , thế thì

Như vậy ta đã chứng minh chiều thuận của định lý. Ngược lại, giả sử tồn tại một tam giác nguyên với diện tích bằng mà không nguyên thủy. Khi đó ta cần chứng minh rằng tam giác nguyên luôn có thể phân hoạch thành các tam giác nguyên thủy.

s152.photobucket.com/albums/s165/dumb_boy1988/fig003.png
Hình 3.

Giả sử tam giác nguyên không nguyên thủy chỉ có các điểm nằm trên cạnh là nguyên. Khi đó tồn tại một cạnh chứa trong nó các điểm nguyên, ta nối các điểm này với đỉnh (hình [3]), trong các cạnh nối này không có chứa điểm nguyên nên các tam giác được chia ra, ngoại trừ nhiều nhất hai tam giác chứa cạnh (trong trường hợp trong các cạnh chứa điểm nguyên), đều là nguyên thủy. Kí hiệu hai tam giác không nguyên thủy này là , khi đó từ ta nối tương ứng với các điểm nguyên nằm trên cạnh . Khi đó toàn bộ các tam giác được chia ra đều là nguyên thủy.

s152.photobucket.com/albums/s165/dumb_boy1988/fig004.png
Hình 4.

Giả sử tam giác chứa trong nó một số điểm nguyên nào đó (hình [4]). Ta chọn ra một điểm và nối chúng với các đỉnh , thu được 3 tam giác nhỏ hơn. Ta tiếp tục quá trình chọn và phân hoạch tam giác đối với 3 tam giác nhỏ này. Vì số điểm nguyên nằm bên trong tam giác là hữu hạn nên đến một thời điểm thì quá trình này dừng và thu được các tam giác nguyên bên trong không chứa điểm nguyên nào, có thể trên cạnh có chứa điểm nguyên, và ta tiếp tục áp dụng cách phân hoạch như đã chỉ ra ở phần trên để thu được tất các các tam giác được phân hoạch đều là nguyên thủy.

Như vậy tam giác nguyên không nguyên thủy có thể phân hoạch ít nhất là 2 tam giác nguyên thủy, mà mỗi tam giác này có diện tích là 1/2 như đã chỉ ra ở phần thuận của định lý, từ đó , mâu thuẫn này cho ta chứng minh của phần đảo.

Bài tập 1. Chứng minh rằng với bất kì số luôn tồn tại tam giác nguyên thủy mà các chiều dài cạnh của nó đều lớn hơn .

II – Công thức Picard

Trong phần này khi nhắc đến đa giác, chúng ta xem chúng như là đa giác đơn, nghĩa là đa giác bị chặn và biên của nó là đường gấp khúc không tự cắt. Hình [5] là thí dụ về đa giác không đơn

s152.photobucket.com/albums/s165/dumb_boy1988/fig005.png
Hình 5.

Định lý 2. (Picard) Với đa giác nguyên thì diện tích của nó được tính theo công thức

trong đó là số điểm nguyên nằm trong, và là số điểm nguyên nằm trên cạnh của đa giác ngoại trừ các đỉnh của nó.

s152.photobucket.com/albums/s165/dumb_boy1988/fig006.png
Hình 6.

Thí dụ, như hình [6], ta có , áp dụng công thức Picard, thế thì diện tích đa giác nguyên này là

Chứng minh.

Trước hết bạn đọc hãy tự làm bài tập nhỏ sau

Bài tập 2. Bất kì một đa giác đơn có số đỉnh lớn hơn 4 đều tồn tại một đường chéo nằm hoàn toàn trong đa giác đó.

Từ đó bằng quy nạp dễ dàng chứng minh -giác có thể phân hoạch thành tam giác mà các đỉnh của chúng là các đỉnh của đa giác ban đầu. Do đó tổng các góc trong của một giác đơn đúng bằng .

Mỗi tam giác nhận được từ cách phân hoạch giác nguyên như trên ta có thể tiếp tục chia nhỏ chúng thành các tam giác nguyên thủy như cách đã trình bày ở định lý 1. Diện tích của mỗi tam giác nguyên thủy bằng , do đó số tam giác nguyên thủy được chia ra đúng bằng và do đó không phụ thuộc vào cách chia.

Và điều ta cần chứng minh tương đương với

s152.photobucket.com/albums/s165/dumb_boy1988/fig007.png
Hình 7.

Tổng tất cả các góc thuộc các tam giác nguyên thủy được chia ra mà các góc đó có đỉnh là đỉnh của -giác bằng tổng các góc trong của đa giác này, và bằng (hình [7a]).

Tổng tất cả các góc thuộc các tam giác nguyên thủy được chia ra mà các góc đó có đỉnh nằm trên cạnh và không trùng với đỉnh của giác đúng bằng (hình [7b]).

Tổng tất cả các góc thuộc các tam giác nguyên thủy được chia ra mà các góc đó có đỉnh nằm bên trong đa giác đúng bằng (hình [7c]).

Mặc khác tổng tất cả các góc của tất cả các tam giác nguyên thủy được chia ra đúng bằng . Do dó

hay , là điều cần phải chứng minh.

Chú ý. Giả sử mặt phẳng được phân hoạch thành các hình bình hành bằng nhau bởi hai họ đường thẳng song song cắt nhau. Khi đó các đỉnh của các hình bình hành này lập thành một tập hợp gọi là lưới . Lưới nguyên là một trường hợp riêng khi mà hai họ đường thẳng song song vuông góc nhau, và mỗi hình bình hành trở thành hình vuông.

Giả sử đa giác với các đỉnh nằm trên lưới thỏa mãn công thức Picard mở rộng

Trong đó là diện tích của mỗi hình bình hành trong lưới .

III – Phân tích logic của lời giải

Chúng ta phát biểu lại một lần nữa ba khẳng định mà đã chứng minh ở phần trên

1. Với mỗi đa giác nguyên , ta có công thức Picard

2. Diện tích của mỗi tam giác nguyên thủy bằng .

3. Với bất kì sự phân hoạch đa ngác nguyên thành tam giác nguyên thủy, thế thì

Chúng ta có các lược đồ logic của chứng minh như trên hình 8.

s152.photobucket.com/albums/s165/dumb_boy1988/fig008.png
Hình 8.

Trong hình a, ta chứng minh được công thức Picard 1. một cách độc lập với 2. và 3., từ 1. suy ra 2. thì tầm thường và 3. suy ra từ 1. và 2. (xem bài tập 3)

Trong hình b, đó chính là lược đồ mà chúng ta đã chứng minh. Đầu tiên chứng minh 2. một cách độc lập, rồi từ đó nhận được 3., và công thức Picard là hệ quả của 2. và 3.

Chúng ta sẽ xem xét hai lược đồ chứng minh đáng chú ý còn lại.

Chúng ta có thể chỉ ra 3. suy ra 2. Thật vậy, chú ý rằng diện tích của bất kì tam giác nguyên luôn có dạng . Để làm rõ điều này, chúng ta ngoại tiếp tam giác nguyên này bằng hình chữ nhật nguyên nhỏ nhất có canh song song với hai trục tọa độ. Cũng như ở phần đầu, có tất cả các vị trí mô tả bằng hình [2]. Hình chữ nhật ngoại tiếp có diện tích là số nguyên và các tam giác bổ sung cũng có diện tích dạng một nửa số nguyên hoặc số nguyên, từ đó diện tích tam giác nguyên có dạng số nguyên hoặc nửa số nguyên, và rõ ràng luôn không bé hơn .

Bây giờ xét tam giác nguyên thủy , và là hình chữ nhật nhỏ nhất ngoại tiếp nó, chúng ta chia các phần bổ sung bên ngoài thành để thành thành các tam giác nguyên thủy. Đây la một sự phân hoạch thành các tam giác nguyên thủy , trong đó chứa cả .

Chúng ta cũng có thể phân hoạch thành các tam giác nguyên thủy theo một cách khác: chia đôi theo đường chéo các ô vuông đơn vị cấu thành nên . Giả sử diện tích của thì có tất cả tam giác nguyên thủy, và số tam giác nguyên thủy này là phụ thuộc vào cách phân hoạch. Quay lại các chia đầu tiên, chúng ta có

Lại có với mỗi , suy ra , và đặc biệt .

Bây giờ xem xét sự suy ra 1. từ 2. Xét hàm sau

xác định trên các đa giác nguyên (đơn).

s152.photobucket.com/albums/s165/dumb_boy1988/fig009.png
Hình 9.

Nếu phân hoạch một đa giác nguyên bởi một đường gấp khúc bên trong nó mà các đỉnh của đường gấp khúc là điểm nguyên thanh hai đa giác nguyên , chúng ta viết , xem hình [9]. Dễ dàng kiểm tra sự cộng tính của hàm

và diện tích cũng thỏa mãn sự cộng tính

Do đó nếu công thức Picard đúng cho các các đa giác nguyên thì cũng đúng cho cả . Và như đã biết, đa giác nguyên luôn phân hoạch được thành các tam giác nguyên thủy, trong khi 2. chính là trường hợp đặc biệt công thức Picard cho tam giác nguyên thủy.

Bài tập 3. Sử dụng các ngoại tiếp hình chữ nhật như đã nêu ở định lý 1. và hàm cộng tính để chứng minh 1. một cách độc lập với 2. và 3.

IV – Công thức Euler

Chúng ta gọi một bản đồ đa giác là “đúng” nếu đó là sự phân hoạch đa giác đơn thành các các đa khác đơn khác sao cho bất kì hai đa giác nào được chia ra hoặc là có một cạnh chung hoặc chỉ có một đỉnh chung, hoặc là không có điểm chung nào.

Bản đồ đa giác đúng có thể xem như là một trường hợp riêng của đồ thị phẳng. Ta gọi các đa giác trong phân hoạch là các diện, và các cạnh của các đa giác đó là cạnh của bản đồ.

Đối với đồ thị phẳng (với trường hợp riêng là bản đồ đa giác) chúng ta có công thức Euler quen thuộc liên hệ giữa số đỉnh , số cạnh và số diện

Có thể xem một ví dụ trong hình dưới

s152.photobucket.com/albums/s165/dumb_boy1988/fig010.png
Hình 10.

Từ “bản đồ” nhấn mạnh rằng công thức Euler nói chung đúng cho các phân hoạch cong (xem hình [11]), mà dạng của đường là không quan trọng mà là cách nối giữa các điểm với thỏa mãn điều kiện “đúng”, (Thí dụ, sự phân hoạch ngũ giác thành các tam giác và tứ giác như ở hình 10, ta thay thế các đoạn thẳng bằng các đoạn cong để nhận được bẳng đồ cong “đúng”).

s152.photobucket.com/albums/s165/dumb_boy1988/fig011.png
Hình 11.

Trong trường hợp các diện của bản đồ đa giác đúng đều là tam giác thì ta gọi đây là bản đồ tam giác. Hiển nhiên rằng, với một đa giác đơn trên mặt phẳng có vô hạn cách phân hoạch nó thành bản đồ tam giác. Đồng thời số các diện tam giác luôn thỏa mãn công thức (không chỉ riêng trên lưới nguyên

ở đây lần lượt là số đỉnh của bản đồ nằm trong là số đỉnh nằm trên cạnh của nó. (bạn đọc tự chứng minh công thức này)

Mặc khác, chú ý rằng là số đỉnh của bản đồ nằm trên cạnh của , nên là số cạnh hoàn toàn trong đa giác , và mỗi cạnh này là cạnh chung của hai tam giác. Tổng số cạnh của tất cả các diện tam giác của bản đồ bằng

Từ đây suy ra

Định lý 3. (Euler) Với bất kì bản đồ đa giác “đúng”, ta có đẳng thức sau

Chứng minh

s152.photobucket.com/albums/s165/dumb_boy1988/fig012.png
Hình 12.

Giả sử có bản đồ đa giác với số đỉnh , số cạnh , số diện . Chúng ta đặt trong mỗi diện của bản đồ một điểm, nối mỗi điểm đó với các đỉnh của diện chứa nó. Khi đó thu được bản đồ tam giác (xem hình [12]) với số tam giác được phân hoạch là , số đỉnh nằm trên biên của đa giác ban đầu là , số đỉnh nằm trong đa giác này là , số cạnh là . Do cách bổ sung các đỉnh nên ta có tổng số các đỉnh của

Mỗi diện của bản đồ cũ được phân hoạch thành các diện con, mà số lượng bằng số các cạnh mới được nối nằm trong diện này, do vậy số các cạnh của bản đồ mới là

Sử dụng công thức (*) ứng với bản đồ : , từ đó

Như vậy ta thu được điều phải chứng minh.

Bài tập 4. Kiểm chứng chiều đảo, có nghĩa là từ công thức suy ra đẳng thức .

Bài tập 5. Chứng minh công thức Euler một cách độc lập với công thức .

Như vậy trong bài viết chúng ta đã trình bày mỗi liên hệ logic giữa hai công thức đẹp Euler và Picard, chúng có thể được hiểu như là tương đương nhau.

s152.photobucket.com/albums/s165/dumb_boy1988/fig013.png
Hình 13.

Chúng ta có thể mở rộng hai công thức nà trong trường hợp bản đồ đúng với các “lỗ khoét”, mà mỗi lỗ khoét có dạng đa giác đơn (phần tô đậm trong hình trên)

Định lý 4. Với đa giác nguyên với “lỗ khoét” cũng là những đa giác nguyên có diện tích là

trong đó, là số đỉnh nằm bên trong đa giác và không nằm cạnh của đa giác và trên cạnh của các lỗ khoét, là số đỉnh nằm trên cạnh của đa giác và trên cạnh của các lỗ khoét.

Định lý 5. Với mỗi bản đồ đa giác với lỗ khoét thế thì

Bạn đọc hãy tự chứng minh hai định lý này xem như bài tập.

Bài tập bổ sung.

6. Xét tam giác nguyên sao cho trên cạnh của nó không chứa các điểm nguyên nào khác các đỉnh. Chứng minh rằng nếu một tam giác như vậy chứa trong nó đúng một điểm nguyên thì điểm này chính là trọng tâm của tam giác.

7. Giả sử một -giác nguyên lồi sao cho bên trong và cạnh của nó không chứa một điểm nguyên nào khác các đỉnh, chứng tỏ .

8. Chứng minh rằng với bất kì hai điểm nguyên sao cho giữa đoạn nối chúng không chứa điểm nguyên nào khác, tìm được điểm sao cho tam giác là nguyên thủy. Khoảng cách từ đến bằng bao nhiêu nếu biết độ dài .

9. Xét điểm nguyên ()sao cho bất kì ba điểm nào giữa chúng đều lập thành được tam giác mà các trung tuyến của nó không cắt một điểm nguyên nào khác. Tìm số lớn nhất có thể được.

10. Chứng mình rằng mỗi hình vuông có cạnh bằng nằm trong mặt phẳng chứa không nhiều hơn điểm nguyên.

11. Trong mỗi trường hợp trong hình [14], tính diện tích của các hình bình hành được tô đậm, trong đó cạnh của hình bình hành được chia tương ứng ra thành phần bằng nhau, và biết .

s152.photobucket.com/albums/s165/dumb_boy1988/fig015.png
Hình 14.

13. Mỗi cạnh của tam giác được chia thành ba phần bằng nhau, trên mỗi cạnh nối một điểm chia với đỉnh của tam giác đối diện với nó, như là đã chỉ ra trên hình [15]. So sánh, diện tích tam tô đậm với tam giác .

s152.photobucket.com/albums/s165/dumb_boy1988/fig016.png
Hình 15.

14. Từ trung điểm của mỗi cạnh hình vuông nối với hai đỉnh còn lại của hình vuôn đối diện với nó, như là đã chỉ ra trên hình [16], tính tỉ lệ diện tích giữa hình bát giác được tô đậm với hình vuông này.

s152.photobucket.com/albums/s165/dumb_boy1988/fig017.png
Hình 16.

15. Đặt


với là các hằng số nào đó. Giả sử hàm số này xác định trên các đa giác nguyên và thỏa mãn , nếu như được phân hoạch ra thành hai đa giác nguyên bởi một đường gấp khúc với các đỉnh nguyên. Chứng tỏ rằng .

16. Chứng minh rằng với bất kì đa giác nguyên ta luôn có đẳng thức

ở đây là kí hiệu số tất cả các điểm nằm bên trong cũng như trên các cạnh của đa giác , và là đa giác nhận từ bằng cách phóng to lên hai lần với gốc tọa độ.

17. Hãy chỉ ra trên mặt phẳng 1000 điểm sao cho không có 3 điểm nào trong chúng thẳng hàng và khoảng cách giữa hai điểm bất kì là một số vô tỉ, còn diện tích của một tam giác bất kì, mà 3 đỉnh của nó được chọn ra từ các điểm nói trên, là một số hữu tỉ.

Categories: Combinatorics

Lý thyết các quân xe


A – Mở đầu

Hoán vị với các vị trí cấm

Ta có một mô hình cho một bài toán tổng quát như sau:

Xét các tập khác rỗng và kí hiệu tập các hoán vị với độ dài bằng

Đặt \ | \ \}, tập được gọi là vị trí cấm của , các hoán vị thuộc gọi là hoán vị với các vị trí cấm (permutation with forbidden positions) tương ứng với hệ

Một hoán vị tương đương với một cách sắp đặt con xe trên bàn cờ vua ở các tọa độ (Ở đây ta đánh số các cột và các dòng bằng các số từ trái sáng sang phải và từ trên xuống dưới, là tọa độ của ô nằm ở cột thứ và hàng thứ ), dĩ nhiên là nên không có 2 con nào ăn nhau.

Nếu thì hoán vị này tương ứng với một cách sắp đặt con xe lên bàn cờ sao cho không có hai con nào ăn nhau và con xe nằm ở cột thứ thì không được phép đặt vào các ô vuông có tọa độ thuộc tập , các vị trí này gọi là vị trí cấm (dĩ nhiên với ).

Gọi là tập các cách sắp xếp mà con xe ở cột thứ được đặt vào vị trí cấm. Theo nguyên lý bao hàm-loại trừ ta có kết quả tổng quát


Gọi là số sắp đặt con xe lên bàn cờ sao cho mỗi con xe đều ở vị trí cấm, quy ước . Thế thì

Do đó

Số cách sắp đặt các quân xe

Gọi là số cách sắp đặt k con xe (rook number) lên miền ô vuông (miền ở đây không nhất thiết là phải liên thông) trên bàn cờ sao cho không có 2 con nào ăn nhau.
Hàm sinh gọi là đa thức xe (rook polynomial) của miền , quy ước .
Một miền các ô vuông trên bàn cờ có thể được đặc trưng bởi một trận trên trường với bằng 1 nếu ô nếu ô .

Một số tính chất quan trọng:

1. trong đó là một ô vuông trong , là miền ô vuông nhận được từ C khi bỏ đi là miền ô vuông nhận được từ C khi bỏ đi tất cả các ô có cùng hàng và cùng cột với .

Thật vậy, khi sắp xếp quân xe lên miền , trong đó ô cố định, thì có hai trường hợp xảy ra:

– Ô được sắp một quân xe, khi đó đối với quân xe còn lại thì không thể sắp cùng hàng hoặc cùng cột với . Số cách sắp trong trường hợp này là .

– Ô không được sắp quân xe nào, khi đó đối với quân xe có thể sắp trên miền . Số cách sắp xếp trong trường hợp này là . Vì vậy:

Từ đây dễ suy ra kết quả với dạng hàm sinh.

Miền các ô vuông gọi là một block của miền các ô vuông nếu thỏa mãn:

i. Với bất kì các dòng có chứa ô của và cột không chứa ô nào của thì ô .

ii. Với bất kì dòng i không chứa nào của , và các cột chứa ô của thì .

Ta có một mở rộng (xem thêm ở [1]) của tính chất 1 như sau:

2. Với là miền ô vuông trên bàn cờ và là một block nằm trên hàng và cột thế thì

Trong đó với là miền nhận được bằng cách bỏ các ô của sao cho:

i. Bỏ đi tất cả các ô của

ii. Bỏ đi tất cả các ô thuộc dòng trong số dòng chứa các ô của

iii. Bỏ đi tất cả các ô thuộc cột trong số cột chứa các ô của

Chứng minh này cũng không khó khăn, chi tiết xin dành cho bạn đọc.

3. với là hai miền không có hàng nào chung và cột nào chung, là miền ô vuông bao gồm tất cả các ô vuông của

Thật vậy, vì là hai miền không có hàng nào chung và cột nào chung nên mỗi cách sắp đặt quân xe lên quân xe lên sẽ ứng với mỗi cách sắp đặt quân xe lên miền , với . Vì vậy . Từ đây nhận được kết quả dưới dạng hàm sinh.
Giả sử là một miền ô vuông trên bàn cờ và là miền bù của nó trên bàn cờ , thế thì số cách đặt quân xe lên sẽ bằng số cách sắp đặt quân xe lên bàn cờ và coi các ô thuộc như là các vị trí cấm. Tương tự như phần đầu, kí hiệu với là số cắp sắp đặt mà quân xe thứ nằm vào miền cấm là .

Bằng quy tắc nhân ta tính được

Ở đây ta chú ý rằng số cách sắp quân xe lên bàn cờ bằng , với (chứng minh điều này xem như bài tập), và ta đã áp dụng cho .

Theo nguyên lý bao hàm-loại trừ, ta có

Từ đây ta có một liên hệ đẹp giữ đa thức xe của hai miền ô vuông bù nhau:

4. R_{\overline{B}}(x)=\sum_{k=0}^n\left (\sum_{s=0}^k(-1)^s \frac{(m-s)!(n-s)!}{(n-k)!(n-k)!(k-s)!}r_s(B)\right )x^k
Bài tập.

1. Kí hiệu là đa thức xe của bảng chữ nhật ô. Chứng tỏ rằng

và dạng tương tự

Từ đó suy ra

2. Kí hiệu (Đa thức Laguerre). Chứng tỏ rằng

3. Chứng minh rằng

4. Với là một bảng vuông bất kì, ta viết thay vì . Giả sử là bậc của đa thức , chứng các bất đẳng thức sau
a.
b. với .
c.
d.
e. với .
f. với
g. với

Lý thuyết các quân xe (Rook Theory) mà đối tượng của nó là đa thức xe được nghiên cứu đầu tiên bởi Kaplansky and Riordan vào năm 1946, và sau đó là các mở rộng của Goldman với sự ứng dụng của nhiều phương pháp tổ hợp hiện đại từ những năm 1970. Trong những năm gần đây Haglund đạt được nhiều thành công trong việc gắn kết đa thức xe với nhiều lĩnh vực khác như chuỗi siêu hình học, bài toán đếm ma trận trên trường hữu hạn, lý thuyết biểu diễn nhóm. Lý thuyết các quân xe có quan hệ gần gũi với nhiều ứng dụng trong lý thuyết đồ thị, người ta cũng đã vận dụng đa thức xe cùng với cơ học lượng tử và đại số Weyl. Còn trong Tổ hợp đếm nói riêng, đa thức xe liên quan đến hàng loạt các bài toán đếm về hoán vị, phân hoạch, hình vuông Latin…

Trong phần mở đầu chúng ta đã làm quen với cách tính toán ma thức xe với sự đệ quy của các miền ô vuông. Phần ứng dụng máy tính trong tính toán đa thức xe sẽ được đề cập ở cuối bài viết, xem như là phụ lục.

B – Mở rộng và ứng dụng

1. Bài toán đếm hoán vị bất hòa

Bài toán 1.
(Derangement problem) Tìm số các hoán vị sao cho .

(Bài toán được nghiên cứu đầu tiên bởi Pierre Raymond de Montmort vào năm 1713)
Lời giải

Bài toán tương đương với việc tìm số các cách sắp xếp các quân xe lên bàn cờ ô với và miền các vị trí cấm chính là đường chéo chính của bàn cờ:

Rõ ràng miền này có thể được xem là phân hoạch thành ô vuông đôi một không cùng hàng và cùng cột. Đa thức xe của mỗi ô như vậy là .

i152.photobucket.com/albums/s165/dumb_boy1988/derangement.jpg

Áp dụng tính chất 3, ta có . Suy ra .
Áp dụng bài toán hoán vị với các vị trí cấm, ta thu được công thức tính số các hoán vị thỏa mãn điều kiện bài toán:

Một hoán vị như vậy gọi là vô trật tự (derangement permutation).

Chú ý là khi thì .

Bài toán 2. (Ménage problem) Tìm số cách sắp xếp cặp cô dâu, chú rể vào một bàn tròn chỗ () sao cho các cô dâu, chú rể ngồi luân phiên nhau, nhưng không xảy ra trường hợp chú rể ngồi bên cạnh cô dâu của mình.
(Bài toán được nghiên cứu đầu tiên bởi Édouard Lucas vào năm 1891)
Lời giải

Đầu tiên, ta sắp cô dâu vào bàn, sao cho giữa hai cô dâu để trống một ghế dành cho một chú rể nào đó. Số cách sắp xếp như vậy bằng

Trong mỗi cách sắp xếp các cô dâu, đánh số họ theo chiều kim đồng hồ lần lượt là . Ghế trống bên phải cô dâu thứ ta đánh số là .

Bây giờ ta xếp các chú rể vào ghế trống này sao cho thỏa mãn yêu cầu bài toán.

Giả sử chú rể của cô dâu thứ được sắp vào ghế số .

Thế thì

Ta có thể cho tương ứng một hoán vị () như vậy bằng với một cách sắp các quân xe lên bàn cờ ô với miền các vị trí cấm là:

i152.photobucket.com/albums/s165/dumb_boy1988/menage.jpg

Áp dụng tính chất 1, đối với miền ô vuông khi bỏ đi ô ta được miền , nếu xóa đi dòng và cột chứa ô này ta được miền . Ta có:

Với miền ta loại đi ô được miền , loại đi hàng và cột chứa ô này thu được , tương tự ta nhận được

Với miền , ta loại đi ô thu được miền , loại đi hàng và cột chứa ô này thu được . Thế thì

Từ các quan hệ đệ quy trên, ta rút ra được:

Và với các trường hợp đầu tiên, ta tính được , .

Kết quả cuối cùng, tính được (có thể sử dụng hàm sinh hoặc đa thức đặc trưng):

Áp dụng bài toán hoán vị với các vị trí cấm, ta có số các hoán vị thỏa mãn điều kiện là

Đây là số cách sắp xếp chú rể vào vị trí trống như đã đánh số. Công thức của số cách sắp xếp các cô dâu chú rể thỏa mãn điều kiện bài toán là:

Trường hợp tổng quát của Bài toán 1Bài toán 2, ta gọi hoán vị sao cho -bất hòa (k-discordant). Cho đến nay người ta đã có các kết quả cho bài toán này cho . Trường hợp có thể tiếp cận một cách sơ cấp để tìm quan hệ đệ quy và hàm sinh, trong bài viết không đề cập đến do khá phức tạp, bạn đọc có thể tham khảo ở . Trong trường hợp tổng quát, vấn đề tìm một công thức chính xác để tính số hoán vị -bất hòa vẫn là bài toán mở.

Bài tập.

1. Một hoán vị được gọi là không liên tiếp (nonconsecutive) nếu như thỏa mãn với . Tìm công thức tính số các hoán vị độ dài không liên tiếp và chứng tỏ

2. Chứng minh rằng:

a.

b.

c.

d.

e.

f.

với

g.

với .

3. Tìm công thức tính số các cách sắp xếp quân xe lên bàn cờ sao cho không có hai con nào nằm trên hai đường chéo lớn của bàn cờ.

4. Với (ménage number), chứng minh rằng:
a.

b.

2. Bảng Ferrers

Với thì miền các ô vuông được xác định bởi

gọi là bảng một bảng Ferrers. Như vậy bảng Ferrers được tạo thành từ dãy các cột ô vuông với chiều cao không giảm.

Ta có các định nghĩa:

1. gọi là vector chiều cao của .

2. () với , với gọi là m-vector chiều cao của .

Chú ý rằng . Có thể hiểu một cách đơn giản rằng là vector tạo ra từ bằng cách thêm các giá trị 0 vào vị trí đầu tiên.

3. với gọi là vector m-cấu trúc của .

Dễ dàng kiểm chứng các tính chất sau:

i.

ii. với

iii. khi và chỉ khi

Ngược lại, nếu một vector gồm số nguyên thỏa mãn (i) và (ii) thì nó là một vector n-cấu trúc của một bảng Ferrers xác định duy nhất.

4. () gọi là đa thức m-giai thừa của bảng Ferrers .

Định lý 1. (Factorization theorem) Xét bảng Ferrers F với cột, với có vector m-cấu trúc và đa thức m-giai thừa thế thì

Ở đây nếu và bằng 0 nếu .

Chứng minh

Giả sử có vector chiều cao là và m-vector chiều cao

Với , xét bảng với vector chiều cao

Dễ thấy, vế phải của đẳng thức cần chứng minh đúng bằng .

Ta sẽ tính theo một cách khác. Coi , là bảng hình chữ nhật ô nằm bên dưới (hình vẽ)

i152.photobucket.com/albums/s165/dumb_boy1988/ferrers.jpg

Trong mỗi trường hợp sắp xếp quân xe lên , giả sử trên quân xe, thì số cách sắp xếp các quân xe trên bằng , khi đó còn lại quân xe sắp xếp trên . Sau loại đi cột đã bị chiếm bởi quân xe đã sắp trên thì chỉ còn cột có thể sắp xe lên được trên . Nên đối với quân xe còn lại ta xem như sắp xếp chúng lên một miền chữ nhật , có tất cả cách sắp xếp.
Vì vậy
Đẳng thức cần chứng minh được kiểm chứng với vô hạn điểm là các số tự nhiên, hơn nữa do dạng đa thức nên ta thu được kết quả cho mọi .

Hệ quả 1. Xét bảng Ferrers với thế thì

Hệ quả này suy ra từ định lý 1 với , và tương ứng .

Trường hợp đặc biệt, đối với bảng thế thì , ở đây là số Stirling loại II

Thật vậy, áp dụng hệ quả trên ta có \sum_{k=1}^n r_k [x]_{n-k}=x^n đây là phương trình quen thuộc của số Stirling loại hai.

Ngoài ra chúng ta có thể giải quyết bằng một phương án thuần túy hơn. là số các phân hoạch tập thành khối khác rỗng không giao nhau. Xét mỗi cách sắp xếp quân xe lên bảng . Quân xe được sắp ở vị trí thì ta cho tương ứng hai số nằm cùng một khối trong phân hoạch. Việc kiểm tra đây là một song ánh xin dành cho bạn đọc.

Ta định nghĩa rằng hai miền ô vuông là tương đương (rook equivalence) nếu chúng có cùng đa thức xe. Theo định lý 1 ta suy ra được rằng:

i. Hai bảng Ferrers tương đương nếu và chỉ nếu với nào đó thì đa thức -giai thừa của chúng đồng nhất nhau.

ii. Hai bảng Ferrers tương đương nếu và chỉ nếu với nào đó thì . Ở đây kí hiệu là tập có lặp gồm các thành phần của vector .

Định lý 2. Mỗi bảng Ferrers tương đương với duy nhất một bảng Ferrers với dãy chiều cao các cột là tăng ngặt.

Chứng minh

Trước hết, xét bảng Ferrer với các cột có chiều cao tăng ngặt . Thế thì , trong đó vị trí đầu tiên bằng 0. Khi đó với . Một vector m-cấu trúc như vậy xác định duy nhất một bảng Ferrers, và bảng này có các cột có chiều cao tăng ngặt.

Với là một bảng Ferrers bất kì, theo nhận xét trên ta sẽ xây dựng một bảng Ferrers tương đương với , nghĩa là có để , và các thành phần được sắp tương tự như dạng của .\\

Ta có nên các bảng tương đương thì có cùng số ô. Xét , thế thì . Giả sử là thành phần có giá trị nhỏ nhất trong . Theo tính chất của của vector m-cấu trúc thì cũng xuất hiện trong . Xét vector:

Ở đây là các phần tử của tập có lặp loại đi các phần tử và sắp thứ tự không giảm . Như vậy là một vector m-cấu trúc của một bảng Ferrers với các cột có chiều cao tăng ngặt. Hơn nữa do là phần tử nhỏ nhất trong tập có lặp nên là bảng Ferrers với các cột có chiều cao tăng ngặt duy nhất tương đương với .

Một bài toán nảy sinh là có bao nhiêu bảng Ferrers tương đương với một bảng Ferrers cho trước? Ta thấy rằng đều là các hoán vị của tập có lặp . Như vậy bài toán được giải quyết khi ta đếm được số hoán vị của tập có lặp .

Định lý 3. Số bảng Ferrers tương đương với bảng Ferrers cho trước bằng:

Ở đây là thành phần có giá trị bé nhất trong vector , và là số lần xuất hiện của phần tử trong tập có lặp .

Chứng minh công thức này có thể xem trong .

Bài tập.

1. Cho là dãy tăng bao gồm các số nguyên dương, và bảng Ferrers với . Đặt

Chứng tỏ rằng

2. Có bao nhiêu bảng Ferrers tương đương với bảng Ferrers , trong đó:

a. .

b. .

c. với

C – Lập trình tính toán

1. Sử dụng Mathematica

Bài toán của chúng ta là tìm đa thức xe trên một miền ô vuông cho trước.

Lập hàm RookPolynomial như sau để sinh đa thức xe

RookPolynomial[n_List] := Module[{stacklist, top, SameColumnValues, SameRowValues,
EntriesToEliminate, InclusionList, ExclusionList},
stacklist = {Union[n]};

While[Union[Flatten[stacklist]] =!= {1, x}, top = First[stacklist];
SameColumnValues = Position[top, {_, top[[1, 2]]}];
SameRowValues = Position[top, {top[[1, 1]], _}];
EntriesToEliminate = Union[SameColumnValues, SameRowValues];
InclusionList = Append[Delete[top, EntriesToEliminate], {x}];
ExclusionList = Delete[top, 1];
If[Length[ExclusionList] == 0, ExclusionList = {{1}}];
stacklist = Delete[Append[Append[stacklist, ExclusionList], InclusionList], 1];
While[Union[Flatten[First[stacklist]]] == {x},
stacklist = RotateLeft[stacklist]]];
Total[Apply[Times, stacklist, 2]]]

Input của hàm này là một danh sách, bao gồm tọa độ các ô của miền ô vuông cần tính toán đa thức xe.

Thí dụ. Tính với miền ô vuông .

Ta sử dụng hàm trên như sau:

RookPolynomial[{{1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}}]

Nhấp Shift+Enter, kết quả sẽ là

Out[1]= 1 + 5 x + 10 x^2 + 10 x^3 + 5 x^4 + x^5

2. Sử dụng Maple

Như phần đầu, ta cũng có thể lập một giải thuật tương tự bằng Maple. Nhưng để tránh sự lặp lại, ta xét bài toán tìm đa thức xe trên bàn cờ với miền các vị trí cấm cho trước.

Đầu tiên ta sử dụng hàm complement_ board để tính miền cho phép đặt các quân xe trên bàn cờ, giá trị trả về là một danh sách.

> with(combinat);
> complement_board := proc (F, n)
local i, j, x, L;
L := [];
for i to n do
for j to n do
if `not`(member([i, j], F)) then L := [op(L), [i, j]] end if
end do
end do;
RETURN(L)
end proc;

Hàm non_attacking_rooks_pos tìm tất cả các cách sắp đặt quân xe trên bàn cờ , với miền các vị trí cấm cho dưới dạng một danh sách .

>non_attacking_rooks_pos := proc (F, k, n)

local i, j, ans, cols, R, pos, F0, F1, F2, m, P, x, stop0, is;

P := permute(n, n);

F0 := F; pos := [];

if k = 1 then RETURN(complement_board(F0, n)) end if;

for x in P do

stop0 := 0;

R := choose(n, k);

for is in R do

stop0 := 0;

for i in is do

if member([i, x[i]], F0) then stop0 := 1 end if

end do;

if stop0 = 0 then pos := [op(pos), [seq([i, x[i]], i = is)]] end if

end do

end do;

RETURN(convert(convert(pos, set), list))

end proc

Cuối cùng, hàm rook_polynomial để tính đa thức xe theo biến của bài toán sắp xếp các quân xe trên bàn cờ với miền các vị trí cấm là danh sách .

>rook_polynomial := proc (F, n, x)

local i, a, p;

p := 1+add(nops(non_attacking_rooks_pos(F, i, n))*x^i, i = 1 .. n);

RETURN(p)

end proc

Thí dụ. Sắp xếp các quân xe lên bàn cờ với miền các vị trí cấm là

Ta làm như sau:> rook_polynomial([[1, 1], [2, 2], [3, 3], [4, 4], [5, 5]], 5, x);

Nhấp Enter kết quả sẽ là

1 + 20 x + 130 x^2 + 320 x^3 + 265 x^4 + 44 x ^5

Chú ý là ở đây hàm non_attacking_rooks_pos cho giá trị trả về là một danh sách các cách sắp xếp.

Ta có thể xuất ra tất cả các cách sắp xếp trong từng trường hợp của $n$, $k$ và $F$.

> array_rooks := proc (L, n)

local i, j, A;

A := array(1 .. n, 1 .. n);

for i to n do

for j to n do

A[i, j] := 0;

if member([i, j], L) then A[i, j] := R end if

end do

end do;

print(A)

end proc

Thí dụ.

L:=non_attacking_rooks_pos([[1,2],[1,3],[2,1],[2,3],

[3,2],[3,4],[3,5],[5,4]],5,5):nops(L);

for i from 1 to 4 do array_rooks(L[i],5); end do;

Khi đó kết quả trên màn hình sẽ là số các cách sắp xếp 5 quân xe lên bàn cờ 5\times 5 với miền các vị trí cấm như trên là bằng 18, và 4 cách sắp xếp đầu tiên:

i152.photobucket.com/albums/s165/dumb_boy1988/maple.jpg

Dĩ nhiên để liệt kết hết ta thay 4 trong vòng for bằng nops(L).

Giải thuật cũng áp dụng được đối với các sự sắp xếp các quân xe lên các bảng vuông không có vị trí cấm.

Thí dụ. Đa thức xe của các bảng

Ta làm như sau:

rook_polynomial([],4,x);
rook_polynomial([],5,x);

Kết quả là:

1 + 16 x + 72 x^2 + 96 x^3 + 24 x^4
1 + 25 x + 200 x^2 + 600 x^3 + 600 x^4 + 120 x^5

Tài liệu tham khảo

Abigail Mitchell, A block decomposition algorithm for computing rook polynomials}; preprint at http://arxiv.org/abs/math/0407004v1

William Oscar Jules Moser, The number of very reduced Latin rectangles; Canad. J. Math. 19 (1967) pp. 1011-1017.

Earl Glen Whitehead Jr, Four-discordant permutations; Journal of the Australian Mathematical Society (Series A)(1979), 28, pp. 369-377.

Joseph M. Santmyer, Five discordant permutations; Graphs and Combinatorics (1993), 9, pp. 279-292.

K.P. Kohas, Rook numbers and Rook Polynomials; MCCME, Moskva – 2003 (in Russian).

Richard P. Stanley, Enumerative Combinatorics, Volume 1; Cambridge University Press, 1999.

Mehdi Hassani, Derangements and Applications; Journal of Integer Sequences, Vol. 6 (2003).

Jay R. Goldman, J. T. Joichi, Dennis E. White, Rook Theory. I: Rook Equivalence of Ferrers Boards; Proceedings of the American Mathematical Society, Vol. 52, No. 1 (Oct., 1975), pp. 485-492.

Jay R. Goldman, J. T. Joichi, David L. Reiner, Dennis E. White, Rook Theory. II: Boards of Binomial Type; SIAM Journal on Applied Mathematics, Vol. 31, No. 4 (Dec., 1976), pp. 618-633.

D. C. Foata and M. P. Schutzenberger, On the Rook Polynomials of Ferrers Relations; Colloq. Math. Soc. Janos Bolyai, 4, Combinatorial Theory and its Applications, vol. 2, 1970.

John Riordan, An introdoction to Combinatorial Analysis, Moskva 1963 (in Russian)

http://www.usna.edu/Users/math/wdj/teach/sm342/rook_polynomials.html

http://mathworld.wolfram.com/notebooks/Combinatorics/RookPolynomial.nb

D. C. Fielder, A Generator of Rook Polynomials; Mathematica J. 9 (2004), pp. 371-375.

Categories: Combinatorics

Số bộ các tập con

May 27, 2009 Leave a comment

Bài toán 1.

Tìm số bộ ba các tập con (X, Y, Z) của tập U gồm n phần tử, sao cho

 

(Ký hiệu )

Áp dụng nhận xét ta có

Tương tự với hai điều kiện dưới:

Mà ta biết rằng U có biểu diễn dạng chuẩn tắc giao đầy đủ:


Theo trên thì

Hơn nữa các tập

đều đôi một giao nhau bằng rỗng (mỗi tập có thể bằng rỗng)

Xét ánh xạ sao cho nếu thì , với

Tức là mỗi bộ có thứ tự thì ứng với duy nhất ánh xạ xác định như trên.
Ngược lại với mỗi ánh xạ thì ứng với duy nhất một bộ có thứ tự
.Chú ý tính chất của ánh xạ thì với .

Như vậy ta đã thiết lập một song ánh từ tập các bộ 5 các tập con trong đó với vào tập các ánh xạ

Như vậy số các bộ hay số các bộ cần tìm bằng

Bài toán 2. Với và tập gồm phần tử, tính số tất cả các bộ các tập con có thứ tự sao cho với .

Đặt

Đặt
với .

Theo PIE:

(trong đó quy ­ước khi thì coi )

Tính được ,

Tổng quát .

Như­ vậy số cần tìm là

(To be continued)

Categories: Combinatorics Tags:

Định lý Hall và SDRs

May 18, 2009 2 comments

Bài toán mở đầu của chúng ta là:

Cho n chàng trai, nếu một nhóm k chàng trai bất kì quen với ít nhất k cô gái (1\le k\le n). Chứng tỏ rằng đây là điều kiện cần và đủ để tổ chức một đám cưới tập thể sao cho mỗi chàng trai cưới một cô gái mình quen

 

Có thể mô hình lại bài toán bằng tập hợp. Gọi A_i, \ \ i=1,2,..,n là tập các cô gái mà chàng trai thứ i quen. Khi đó với mọi i_1,i_2,...,i_k \in\{1,2,...,n\} thỏa mãn

 

|A_{i_1}\cup A_{i_2}\cup...\cup A_{i_k}|\ge k (Điều kiện Hall)

 

khi và chỉ khi tồn tại (a_1,...,a_n)\in A_1\times A_2 \times ...\times A_n sao cho a_i\neq a_j với i\neq j

 

Đây là cũng là nội dung của định lý Hall (Định lý này được phát biểu bởi Philip Hall năm 1935, và nó được biết đến đầy đủ với chứng minh và các kết quả của Marshall Hall năm 1948) còn gọi là định lý Đám cưới (Hall’s Marriage Theorem)

 

Một bộ (a_1,...,a_n) như vậy gọi là một hệ đại diện phân biệt cho hệ tập hợp (A_1,A_2,...,A_n) (system of distinct representatives, viết tắt là SDR), phần tử a_i\in A_i gọi là đại diện cho A_i, lưu ý rằng a_i\neq a_j với i\neq j. Như vậy nếu như hệ tập (A_1,...,A_n) thỏa mãn điều kiện Hall thì tồn tại một SDR cho hệ đó và điều ngược lại nếu một hệ có SDR thì nó thỏa mãn điều kiện Hall. Một SDR nếu có nói chung là không duy nhất, bài toán cần quan tâm là có bao nhiêu SDR của một hệ tập hợp cho trước.

 

Cho A=(a_{ij})_n, kí hiệu perA=\sum_{\sigma\in S_n}a_{1\sigma(1)}a_{2\sigma(2)}...a_{n\sigma(n)}

 

Xét họ các tập A_1, A_2,..., A_n là các tập con của [n]. Ma trận liên thuộc của hệ này là A=(a_{ij}) được xác định như sau:

a_{ij}=\left\{\begin{array}{ll}1, \ \ \ \ i \in A_j\\ 0, \ \ \ \ i \notin A_j \end{array}\right.

 

Rõ ràng perA chính bằng số SDR của họ A_1, A_2,...,A_n do a_{1\sigma(1)}a_{2\sigma(2)}...a_{n\sigma(n)} bằng 1 khi và chỉ khi \sigma(i)\in A_i với mọi i tức là \{\sigma(1), \sigma(2),...,\sigma(n)\} là SDR của A_1, A_2,...,A_n.

 

Trong phần đầu tiên, ta sẽ bàn tới chứng minh của định lý Hall. Phần tiếp theo sẽ nói đến một số vấn đề tổ hợp được phát triển liên quan đến các SDR.

 

A – Chứng minh Định lý Hall.

 

I. Lời giải thứ nhất.

 

Để đơn giản ta viết A_I thay cho \bigcup_{i\in I}A_i. Điều kiện Hall viết lại như sau:

 

                               với mọi

 

+ Nếu hệ (A_i)_{ i\in E} có SDR, hiển nhiên Điều kiện Hall được thỏa mãn.

 

+ Ngược lại, giả sử Điều kiện Hall được thỏa mãn cho hệ (A_i)_{ i\in E}, chú ý là mọi hệ con (A_i)_{ i\in K} với K\subset E cũng thỏa mãn Điều kiện Hall. Ta chứng minh sự tồn tại SDR cho hệ này theo quy nạp theo số các tập trong hệ. Nếu hệ chỉ gồm 1 tập thì định lý là hiển nhiên. Giả sử định lý đúng với tất cả các trường hợp số các tập trong hệ bé hơn n.

 

Ta chia ra hai trường hợp:

 

1. Có một tập con I của E khác trống và khác E sao cho | A_I |=| I |.

 

Đặt là tập có số phần tử bé nhất như vậy.  Đặt A'_i=A_i\setminus A_J. Điều kiện Hall cũng thỏa mãn với hệ con nên theo giả thiết quy nạp, hệ này có SDR là  
 

Với tập ,  do Điều kiện Hall nên |A_{J\cup K}|\ge |J\cup K|.

 

Chú ý là |A'_K|=|A_{J\cup K}|-|A_J|, \ |A_J|=|J||K|=|J\cup K|-|J|. Suy ra |A'_K|\ge |K| tức là Điều kiện Hall thỏa mãn cho hệ (A'_i)_{i \in E\setminus J}

 

Tương tự cũng từ giả thiết quy nạp hệ (A'_i)_{i \in E\setminus J} có SDR là .
Khi đó (x_j)_{j\in J}\cup (x_j)_{j\in E\setminus J} là một SDR của hệ (A_i)_{i\in E}

 

2. Trường hợp ngược lại

 

Do Điều kiện Hall được thỏa mãn nên |A_i|\ge|\{i\}|=1, với i=1,2,...,n. Tồn tại x_n\in A_n.

 

Với j=1,2,...,n-1 đặt A'_j=A_j\setminus \{x_n\}. Xét  khác trống, thế thì:

 

| A'_J | \ge | A_J |-1 > | J |-1 (chú ý là không có dấu bằng do giả sử ban đầu) hay |A'_J|\ge |J|

 

Vậy hệ (A'_1,A'_2,...,A'_{n-1}) cũng thỏa mãn Điều kiện Hall. Theo nguyên lý quy nạp suy ra hệ này có SDR là (x_1,x_2,...,x_{n-1}). Và cuối cùng (x_1,x_2,...,x_{n-1},x_n) chính là SDR của (A_i)_{i\in E}.

 

Định lý được chứng minh hoàn toàn. 

 

Sau đây là một cách chứng minh khác ngắn ngọn, trực tiếp hơn:

 

II. Lời giải thứ hai. (Rado)

 

Giả sử hệ (A_1,...,A_n) thỏa mãn Điều kiện Hall. Ta bắt đầu bỏ đi phần tử thuộc mỗi tập A_i sao cho Điều kiện Hall vẫn được thỏa mãn. Cuối cùng thu được hệ tối giản  vẫn thỏa mãn Điều kiện Hall, với B_i\subset A_i, từ tối giản ở đây hiểu là nếu như bỏ đi một phần tử từ một tập B_i bất kì nào đó thì Điều kiện Hall không còn được thỏa mãn.

 

Ta chứng minh rằng .  Thật vậy, không mất tính tổng quát giả sử B_1 có chứa phần tử khác nhau là x,y. Do nếu bỏ đi x hoặc y thì điều kiện Hall không còn thỏa mãn nên có hai tập chỉ số   sao cho:

 

Với X=(B_1\setminus\{x\})\cup\bigcup_{i\in P}B_i, Y=(B_1\setminus\{y\})\cup\bigcup_{i\in P}B_i thì |X|\le |P||Y|\le |Q|

 

Mặc khác

 

X\cup Y=B_1\cup ( \bigcup_{i\in P\cap Q}B_i )

 

và 

 

 

 

Từ Điều kiện Hall suy ra |X\cup Y|\ge 1+|P\cup Q| và   

 

Áp dụng Nguyên lý bao hàm loại trừ và nhận xét trên thì

|P|+|Q|\ge |X|+|Y|=|X\cap Y|+|X\cup Y|\ge 1+|P\cap Q|+|P\cup Q|=1+|P|+|Q|

 

Điều vô lý này dẫn đến khẳng định |B_i|=1, i=1,2,...,n.

 

Các tập B_i như vậy phải đôi một không giao nhau, vì ngược lại nếu có  sao cho B_i=B_j=\{x\} thì hợp của hai tập này B_i\cup B_j=\{x\} có số phần tử là 1, trái với điều kiện Hall.

 

Như vậy chọn được x_i\in B_i\subset A_i, \ i=1,2,...,n , sao cho x_i\neq x_j để lập thành SDR của hệ (A_1,...,A_n)

 

III. Lời giải thứ ba

 

Có lẽ lời giải thứ hai ở trên là sáng sủa nhất. Đã có rất nhiều lời giải cho định lý thú vị này mà cho đến nay nó vẫn là một chủ đề rất cuốn hút. Cách đây mấy năm có một lời giải mới của một sinh viên và 1 giảng viên người Trung Quốc khá độc đáo và sáng tạo. Xin trình bày lại trên ý tưởng của Hui-Qin và Zhi-Wei, ĐH Najing.

 

Định lý 1. A_1, A_2,...,A_n, \ n>1 là tập con của tập X. Giả sử (a_i)_{i=1}^{n-1} là SDR của ( A_i )_{ i=1 }^{ n-1 } . Với J\subset\{1,2,...,n\} có chứa phần tử n thì có đúng |\bigcup_{j\in J}A_j|-|J|+1 cách chọn phần tử a\in X để hợp với a_1,a_2,a_{n-1} và sắp lại để tạo thành một SDR (a'_1,...,a'_n) của (A_i)_{i=1}^{n}, với a'_i đại diện cho A_i, \ i\notin J.

 

Xét một graph  với các đỉnh đánh số là 1,2,...,n sao cho  (đỉnh   kề với ) nếu và chỉ nếu . Đặt 
 

J=\{j\in\{1,2,...,n\} \ | \ tồn tại một đường đi từ j đến n \} A=\bigcup_{j\in J}A_j

 

Như vậy ta có nhận xét: a_i\in A khi và chỉ khi tồn tại j\in J để a_i\in A_j hay tồn tại j\in J để (i,j)\in E, điều này cũng tương đương với tồn tại một đường đi từ i đến n hay i\in J.

 

Suy ra \{ i\in \{1,2,...,n-1\} \ | \ a_i\in A\}=J\setminus\{n\}

 

Đặt B=A\setminus\{a_i \ | \ i\in J\setminus\{n\} \ \}. Hiển nhiên B\cap\{a_1,...,a_{n-1}\}=\emptyset|B|=|A|-|J|+1

 

Xét $latex a\in  X $ sao cho \{ a \} \cup \{ a_1, ... , a_{n-1} \} = ( a'_1 , ... ,a'_n ) là một SDR của (A_i)_{i=1}^{n} với  đại diện cho A_i, \ i\notin J. Rõ ràng thì a\in Ba đại diện cho A_j nào đó với j\in J

 

Mặt khác:

 

– Nếu thì tồn tại sao cho . Nếu thì đặt tạo thành thỏa mãn yêu cầu.

 

– Nếu thì tồn tại một đường đi từ đỉnh j đến n, đặt đường đi đó là , với . Chú ý là . Ta đặt , hiển nhiên với mọi . Nếu ta đặt , khi đó là SDR thỏa mãn điều kiện bài toán.

 

Vậy định lý đã được chứng minh.

 

Điều thú vị suy ra từ mệnh đề này là với bất kì một SDR nào đó của hệ thì có tối thiểu cách để mở rộng thành một SDR của hệ . Ở đây :

 

                                             

 

Như vậy định lý Hall chỉ là hệ quả của đánh giá tuyệt đẹp trên!

 

IV. Các hệ quả.

 

Các định lý sau là hệ quả của định lý Hall cũng có nhiều ứng dụng quan trọng

 

Định lý 2. Xét hệ các tập con của tập . Nếu như:

 

i/ |A_i|=m, \ i=1,2,...,n

 

ii/ Mỗi phần tử của X có mặt đúng m lần trong (A_i)_{i=1}^n

 

Thế thì hệ trên có một SDR

 

Chứng minh

 

. Có tổng cộng phần tử trong . Mỗi phần tử thuộc X xuất hiện đúng m lần trong (A_1,...,A_n) suy ra mỗi phần tử trong S\subset X xuất hiện không quá $latex  m$ lần. Vậy |S|\ge \frac{mk}{m}=k, Điều kiện Hall được thỏa mãn nên hệ có SDR. 

 

Định lý 3.  Xét hệ (A_i)_{i=1}^n thỏa mãn Điều kiện Hall. Với m=min\{|A_1|,|A_2|,...,|A_n|\} thế thì số SDR tối thiểu của hệ này là [m]_{min\{m,n\}}. (Ở đây ta sử dụng kí hiệu chỉnh hợp [n]_k=n(n-1)...(n-k+1))

 

Chứng minh

 

Nếu n=1, đây là điều hiển nhiên. Giả sử định lý đúng với các giá trị bé hơn n

 

Ta xét hai trường hợp như đã đặt ra trong phép chứng minh đầu tiên của định lý Hall:

 

1. Khi đó m\le |J| \le n nên hệ (A_j)_{j\in J} có tối thiểu m! SDR theo giả thiết quy nạp. Mỗi SDR của  có thể mở rộng thành 1 SDR của (A_i)_{i=1}^n, (điều này suy ra từ cách xây dựng quy nạp trong trường hợp đầu của phép chứng minh đầu tiên của định lý Hall)

 

2. Có tối thiểu m cách chọn $latex x_n$. Mỗi tập hợp trong hệ (A'_i)_{i=1}^{n-1} có tối thiểu  phần tử và thỏa mãn Điều kiện Hall nên theo giả thiết quy nạp có tối thiểu [m-1]_{min\{m-1,n-1\}} SDR cho này.

 

Vậy theo nguyên lý quy nạp, định lý được chứng minh hoàn toàn.

 

Chú ý là theo kết quả trong lời giải thứ 3 của định lý Hall thì cũng dễ dàng suy ra định lý trên.

 

B – Ứng dụng

 

1. Định lý Birkhoff – von Neumann

 

Ma trận ngẫu nhiên kép là ma trận vuông với các số hạng không âm sao cho tổng các số hạng trên mỗi hàng và tổng các số hạng trên mỗi cột đều bằng 1.

 

Ma trận thế là ma trận nhận được bằng cách hoán vị các dòng của ma trận đơn vị. Đối với ma trận cấp $n$, nếu như đánh số các dòng của ma trận đơn vị thì một ma trận thế nhận được bằng cách hoán đổi các dòng sẽ tương ứng với một phép thế cấp $n$. Do đó số các ma trận thế bằng n!

 

Định lý 4. (Birkhoff – von Neumann) Một ma trận là ngẫu nhiên kép nếu và chỉ nếu nó được biểu diễn qua một tổ hợp lồi tuyến tính các ma trận thế. Có nghĩa là X\in \Omega_n khi và chỉ khi tồn tại biểu diễn biễu diễn X=\sum_{\sigma\in S_n}{\lambda}_{\sigma}I_{\sigma}

với I_{\sigma} là ma trận thế tương ứng với phép thế \sigma\sum_{\sigma\in S_n}{\lambda}_{\sigma}=1

 

Ta sẽ chứng minh bằng quy nạp định lý này sử dụng Điều kiện Hall cho SDR hay hệ các đại diện phân biệt

 

Chứng minh

 

Đặt N là số tất cả các số hạng dương trong X , rõ ràng N\ge n. Nếu như N=n thì các số hạng này bằng 1, bản thân nó là một ma trận thế. Ta quy nạp theo giá trị của N

 

Bây giờ giả sử mệnh đúng với các giá trị bé hơn N>n, ta chứng minh mệnh đề đúng với trường hợp ma trận ngẫu nhiên kép X=(x_{ij})_nN số hạng dương. Đặt A_i=\{j \ | \ x_{ij}>0\} với i=1,2,...,n. Xét các tập A_{i_1},A_{i_2},...,A_{i_k} nào đó với , chú ý rằng k bằng tổng của tất cả các số hạng dương ở các cột i_1,i_2,...,i_k của X, và dĩ nhiên nó sẽ nhỏ hơn hoặc bằng tổng các số hạng ở những dòng mà có ít nhất một số hạng dương nằm ở các cột i_1,i_2,..,i_k, tổng này lại chính là số các dòng như vậy và bằng |A_{i_1}\cup A_{i_2}\cup....\cup A_{i_k}|.

 

Có nghĩa là điều kiện Hall đã được thỏa mãn, khi đó tồn tại một SDR, ta đặt SDR này là \sigma=\{\sigma(1),....,\sigma(n)\} đại diện cho A_1,A_2,...,A_n. Thế thì \sigma là một phép thế cấp n

 

Đặt {\lambda}_{\sigma}=min\{x_{i,\sigma(i)}, i=1,2,...,n\}.

 

Nếu {\lambda}_{\sigma}=1 thì X là ma trận thế, trường hợp ngược lại ta đặt:

 

Y=\frac{1}{1-{\lambda}_{\sigma}}(X-1-{\lambda}_{\sigma} I_{\sigma}), I_{\sigma} là ma trận thế ứng với phép thế \sigma

 

Như vậy X={\lambda}_{\sigma}I_{\lambda}+(1-{\lambda}_{\sigma})Y

 

Y là ma trận ngẫu nhiên kép với số các phần tử dương bé hơn X. Theo nguyên lý quy nạp, định lý được chứng minh hoàn toàn. \nabla

 

2. Hình vuông Latin

 

Hình vuông Latin bậc là n là bảng số vuông n\times n lập từ các số 1,2,3,...,n sao mỗi hàng và mỗi cột của nó là hoán vị của các số này. Rõ ràng là mỗi số từ tập [n]={1,2,..,n} xuất hiện đúng một lần trên mỗi hàng hoặc cột.

 

Ngoài ra còn có định nghĩa về hình chữ nhật Latin kích thước m\times n (m\le n), đó là đó là một bảng chữ nhật mà mỗi hàng của nó là một hoán vị của [n] và mỗi cột của nó là một chỉnh hợp chập m của [n].

 

Tập các số hạng của bảng vuông có thể là một tập n phần tử khác nhau, ta chọn tập [n] mà không mất tính tổng quát và đơn giản hóa sự biểu diễn.

 

Với n bất kì bạn có thể chỉ ra một hình vuông Latin bậc n như sau:

 

\begin{array}{cccccc}1 & 2 & 3 &...& k-1 & k\\2 & 3 & 4 &...& k & 1\\3 & 4 & 5 &...& 1 & 2\\...&...&...&...&...&...\\k-1 & k & 1 &...& k-3& k-2\\k & 1 & 2 &...& k-2 & k-1\end{array}

 

Bài toán đặt ra là ước lượng số hình vuông Latin cấp n, kí hiệu là L(n). Ta quan tâm đến cận trên và cận dưới của L(n)

 

Định lý 5. 

 

Chứng minh.

 

Ta có nhận xét sau: Từ một hình chữ nhật Latin kích thước m\times n (m<n) có ít nhất (n-m)! cách thêm vào một hàng để trở thành một hình chữ nhật Latin (m+1)\times n.

 

Thật vậy, gọi A_i là tập các số của [n] không có mặt ở hàng thứ i của hình chữ nhật Latin.

 

Rõ ràng các số  được thêm vào như hàng thứ k+1 để bảng số mới là hình chữ nhật Latin, khi và chỉ khi nó là một SDR của (A_1, A_2,..,A_n).

 

Ta có |A_i|=n-m, theo Hệ quả định lý Hall thì có ít nhất (n-m)! SDR. Kết quả định lý thu được là do quy nạp theo nhận xét trên. \nabla

 

Ta sẽ tiếp tục về câu chuyện cận dưới của L(n)

 

Như phần đâu đã nhấn mạnh số SDR của một hệ tập con bằng permanent ma trận nhị phân liên thuộc của hệ đó. Tuy công thức permanent có vẻ tương tự như định thức, nhưng thật sự là không có nhiều quy tắc tính toán tường minh cho permanent.

 

Ta sử dụng kết quả sau đây về cận dưới của ma trận ngẫu nhiên kép được Van der Waerden đưa ra năm 1926 và một thời coi như một giả thuyết cho đến khi có những chứng minh độc lập của Egorychev, Falikman năm 1981.

 

Định lý 6. (Van der Waerden) Nếu ma trận A ngẫu nhiên kép, thế thì \displaystyle perA\ge \frac{n!}{n^n}, đẳng thức xảy ra khi và chỉ khi mỗi số hạng của A đều bằng \displaystyle\frac{1}{n}

 

Ta có một kết quả chặt hơn hệ quả của định lý Hall đã nêu:

 

Định lý 7.  Nếu A_1,A_2,...,A_n là tập con của \{1,2,...,n\} và thỏa mãn:

 

i.  |A_i|=m

 

ii. Mỗi phần tử của [n] chứa trong đúng m tập hợp của A_1,A_2,...,A_n

 

Khi đó số SDR của hệ A_1,A_2,...,A_n tối thiểu là \displaystyle\frac{n!m^n}{n^n}

 

Chứng minh

 

Chú ý là ma trận liên thuộc A của họ A_1,A_2,...,A_n có tổng các hàng và tổng các cột bằng m.

 

Theo định lý Van der Waerden ta có \displaystyle\frac{1}{m^n}perA=per(\frac{1}{m}A)\ge \frac{n!}{n^n}

 

Từ đó \displaystyle perA\ge\frac{n!m^n}{n^n}

 

Đây cũng là điều phải chứng minh. \nabla

 

Cũng tương tự như cách chứng minh định lý 1, từ kết quả định lý 6 ta thu được ước lượng chặt hơn cho biên dưới của L(n)

L(n)\ge \frac{n!n^n}{n^n}\frac{n!(n-1)^n}{n^n}...\frac{n!2^n}{n^n}\frac{n!1^n}{n^n}=\frac{(n!)^{2n}}{n^{n^2}}

 

 

C – Một vài bài toán luyện tập

 

1. Giả sử (A_1,A_2,...,A_n) là một hệ các tập con của tập hữu hạn X. Giả sử rằng ma trận nhị phân liên thuộc của hệ này khả nghịch. Chứng tỏ rằng hệ này có một SDR.

 

2. Nếu (A_1,A_2,...,A_n) là một hệ các tập con của tập X hữu hạn thỏa mãn |\displaystyle\bigcup_{j\in J}A_j|\ge |J|-r

 

với mọi J\subset\{1,2,...,n\}, chứng minh rằng có một hệ con kích thước n-r mà có một SDR.

 

3. Cho (A_1,A_2,...,A_n), (B_1,B_2,...,B_n) là hai phân hoạch (có thứ tự) của một tập X hữu hạn.

 

M=(m_{ij})_n gọi là ma trận liên thuộc với các số hạng m_{ij}=|A_i\cap B_j|, \ i,j\in\{1,2,...,n\}.

 

Chứng minh rằng $latex M$ là ma trận ngẫu nhiên kép nếu và chỉ nếu |A_i|=|B_i|=\displaystyle\frac{|X|}{n}, \ i=1,2,...,n

 

4. Chứng minh rằng  L(n)\le\frac{ (n!)^n}{e^{n-1}}

 

 

Tài liệu tham khảo

 

 

1. Peter J. Cameron; Combinatorics – Topics, Techniques and Algorithms – Cambridge University Press, 1997.

 

2. Charles F. Laywine, Gary L. Mullen; Discrete mathematics using Latin squares – Wiley Interscience Publication, 1998.

 

3. K. A. Ribnikova; Combinatorial Analysis, Problems and Exercises (in Russian) – Nauka Publication, 1982.

 

4. H. Minc; Permanents (in Russian) – Mir Publication, 1982.

 

5. Zhi-Wei Sun; Hall’s Theorem revisited – Proc. Amer. Math. Soc. 129 (2001), no. 10, 3129–3131.

 

6. Hui-Qin Cao and Zhi-Wei Sun; On sums of distinct representatives – Acta Arith. 87 (1998), 159–169.

 

Categories: Combinatorics Tags: ,

Xác suất hai số nguyên dương nguyên tố cùng nhau


Đầu tiên xét bài toán: “Tìm số cặp sao cho “.

Với phân tích chính tắc , nếu b thỏa mãn thì b chia hết ít nhất một trong các ước nguyên tố của . Số các số b như vậy nằm từ 1 đến n là:

Lần lượt cho nhận giá trị từ 1 đến và lấy tổng các giá trị m(b), chú ý số lần lặp của số hạng đúng bằng số các số nằm từ 1 đến n chia hết cho , và bằng

Do đó, theo quy tắc cộng dễ dàng thu được số các bộ thỏa mãn

trong đó các các số nguyên tố từ 1 đến

Ta kí hiệu các số các bộ này ứng với n là l(n)

Ta nhận thấy rằng P=1-\lim_{n\to\infty}\frac{l(n)}{n^2} sẽ bằng xác suất để 2 số nguyên dương được chọn ngẫu nhiên là nguyên tố cùng nhau. Ta đi tìm xác suất thú vị này theo một cách khác.

Chú ý là xác suất để hai số tự nhiên ngẫu nhiên ko nhận số nguyên tố p làm ước số sẽ là
Từ đó ta có xác xuất cần tính sẽ là


Ta lại chú ý công thức

nên ta viết lại P dưới dạng

Ta chú ý đến định lí Unique Factorization thì mỗi số tự nhiên điều biểu diễn duy nhất dưới dạng tích các số nguyên tố

Và ta thấy trong tích trên chứa đủ các số có dạng trên nên ta viết lại tích dưới dạng

(update from http://mathvn.org)

Categories: Combinatorics Tags: ,

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

May 3, 2009 2 comments

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 0″ border=”0″ alt=”” align=”absMiddle” />, 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 0″ border=”0″ alt=”” align=”absMiddle” />, 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ỏ
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 đó 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 đó

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à per(A)=\sum_{\sigma\in S_n}a_{1\sigma(1)}a_{2\sigma(2)}...a_{m\sigma(m)},

S_n 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