Nghịch đảo Mobius

Nội dung chính của bài viết "Nghịch đảo Mobius" trình bày chứng minh của phép nghịch đảo Mobius trên các tập thứ tự bán phần và một vài ứng dụng của nó. Để hiểu rõ hơn, mời các bạn tham khảo chi tiết nội dung bài viết này.
Nội dung trích xuất từ tài liệu:
Nghịch đảo MobiusT ạ p c h íonline củacộng đồngnhững n g ư ờ i Tạp chí online của cộng đồng những người yêu Toán yê u T o á n ¨ NGHỊCH ĐẢO MOBIUS Ngô Quang Hưng (Đại học Buffalo, Mỹ) Phép nghịch đảo M¨obius khởi nguyên là một công thức trong lý thuyết số. Đến những năm 1960 thì Giáo sư Gian-Carlo Rota cho chúng ta thấy công thức trong lý thuyết số là một trường hợp đặc biệt của một công thức áp dụng trên các tập thứ tự bán phần (poset). Công thức M¨obius tổng quát có nhiều ứng dụng trong Toán và Máy Tính. Trong bài này ta rảo qua chứng minh của phép nghịch đảo M¨obius trên các tập thứ tự bán phần và một vài ứng dụng của nó. 1. Ba ví dụ 1.1. Toán tổ hợp Công thức inclusion-exclusion nói rằng, để đếm tổng số nhóc tì có Chí Phèo là bố hoặc thị Nở là mẹ, thì ta cộng số con của chí Phèo với số con của thị Nở trừ đi số con chung. Nói cách khác, cho n tập hợp hữu hạn A1 , ¨ ¨ ¨ , An thì ta có thể tính lực lượng của hội của chúng bằng công thức: ˇ ˇ ˇŤn ˇ řn ř ˇ ˇ i=1 A i ˇ= ˇ i=1 |A i | ´ 1ďiăjďn |Ai X Aj | + ř n´1 1ďiăjăkďn |Ai X Aj X Ak | ´ ¨ ¨ ¨ + (´1) |A1 X ¨ ¨ ¨ X An | Công thức này một số sách nói là của Abraham de Moivre; nhưng có vẻ nó xuất hiện năm 1854 từ một bài báo của Daniel da Silva, và lần nữa năm 1883 trong một bài báo của Joseph Sylvester [11]. Bài tập 1.1. Năm 1891, Franc¸ois Édouard Anatole Lucas (cha đẻ bài toán tháp Hà Nội) đặt câu hỏi sau đây: “cho một cái bàn tròn và m cặp vợ chồng, có bao nhiêu cách để xếp họ ngồi nam nữ xem kẽ sao cho không cặp vợ chồng nào ngồi kề nhau? Ta có thể dùng công thức IE để trả lời câu hỏi của Lucas. 41 1.2. Lý thuyết số Trong lý thuyết số có một công thức gọi là công thức nghịch đảoTạp chí online của cộng đồng những người yêu Toán M¨obius [10], xinh hơn hoa hậu! Công thức này phát biểu như sau: Cho 2 hàm số f, g bất kỳ trên miền số nguyên dương, ta có ...