tailieunhanh - 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. | T ạ p c h í online của cộng đồng nhữ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ụ . 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 . 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 quot Ta có thể dùng công thức IE để trả lời câu hỏi của Lucas. 41 . 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 đảo Tạ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ó ÿ f n g d @n ě 1 d n tương đương với ÿ g n µ d f n d @n ě 1 d n trong đó µ d là hàm M obius định nghĩa như sau amp 1 d là tích của một số chẵn các số nguyên tố khác nhau µ d 1 d là tích của một số lẻ các số nguyên tố khác nhau 0 d có ước số là bình .