หลักการเพิ่มเข้า-ตัดออก

หลักการเพิ่มเข้า-ตัดออกใช้นับขนาดของยูเนียนของเซตโดยการบวกและลบขนาดของส่วนที่ซ้อนทับกันสลับกันไป

Definition

เอกลักษณ์การนับที่ระบุว่าจำนวนสมาชิกของยูเนียนของเซตจำกัดเท่ากับผลรวมสลับของจำนวนสมาชิกของส่วนที่ซ้อนทับกันทั้งหมด โดยพิจารณาจากทุกเซตย่อยที่ไม่ว่างเปล่า

Scope

หัวข้อนี้จะนำเสนอสูตรการเพิ่มเข้า-ตัดออกและการประยุกต์ใช้ในการนับวัตถุที่หลีกเลี่ยงคุณสมบัติที่ห้ามไว้: การเรียงสับเปลี่ยนที่ไม่มีจุดตรึง (derangements), ฟังก์ชันทั่วถึง (surjections), ฟังก์ชันทอเชียนของออยเลอร์ (Euler's totient), และจำนวนเต็มที่เป็นจำนวนเฉพาะสัมพัทธ์กับจำนวนที่กำหนดให้ นอกจากนี้ยังแนะนำมุมมองของตะแกรง (sieve viewpoint) และการวางนัยทั่วไปของฟังก์ชันโมเบียส (Mobius-function generalization) บนเซตอันดับบางส่วน (partially ordered sets) ซึ่งเป็นการจัดวางหลักการนี้ในบริบททางพีชคณิตที่กว้างขึ้น

Core questions

• มีองค์ประกอบกี่ชิ้นที่ตรงตามเงื่อนไขอย่างน้อยหนึ่งข้อจากหลายเงื่อนไขที่ทับซ้อนกัน?
• จะนับวัตถุที่หลีกเลี่ยงคุณสมบัติที่ห้ามไว้ทั้งหมดได้อย่างไร?
• การนับการเรียงสับเปลี่ยนที่ไม่มีจุดตรึงและฟังก์ชันทั่วถึงเป็นไปตามหลักการนี้ได้อย่างไร?
• ฟังก์ชันโมเบียสบนโพเซตวางนัยทั่วไปของการเพิ่มเข้า-ตัดออกได้อย่างไร?

Key concepts

• ยูเนียนของเซตที่ทับซ้อนกัน
• ระเบียบวิธีตะแกรง
• การเรียงสับเปลี่ยนที่ไม่มีจุดตรึงผ่านการเพิ่มเข้า-ตัดออก
• การนับฟังก์ชันทั่วถึง
• ฟังก์ชันทอเชียนของออยเลอร์
• ฟังก์ชันโมเบียสบนโพเซต

Key theories

สูตรการเพิ่มเข้า-ตัดออก

จำนวนสมาชิกของยูเนียนของเซต A_1 ถึง A_n เท่ากับผลรวมของขนาดของเซตเดี่ยว ลบด้วยส่วนที่ซ้อนทับกันเป็นคู่ บวกด้วยส่วนที่ซ้อนทับกันสามส่วน และดำเนินต่อไปเรื่อยๆ เพื่อแก้ไขการนับซ้ำขององค์ประกอบที่ใช้ร่วมกันอย่างเป็นระบบ

การผกผันของโมเบียสบนโพเซต

การวางนัยทั่วไปเชิงโพเซตของสแตนลีย์แทนที่เครื่องหมายสลับของการเพิ่มเข้า-ตัดออกด้วยฟังก์ชันโมเบียสของเซตอันดับบางส่วน ซึ่งรวมหลักการนี้เข้ากับสูตรการผกผันทางทฤษฎีจำนวนและทฤษฎีแลตทิซ

Clinical relevance

แนวคิดของตะแกรงได้ถูกนำไปวางนัยทั่วไปในทฤษฎีจำนวน (ตะแกรงของเอราทอสเทนีสและตะแกรงเชิงวิเคราะห์), ความน่าจะเป็น (อสมการบอนเฟอร์โรนีที่จำกัดความน่าจะเป็นของยูเนียน), และการวิเคราะห์ความน่าเชื่อถือของระบบที่มีโหมดความล้มเหลวที่ซ้อนทับกัน

History

หลักการนี้ถูกกล่าวถึงโดย de Moivre และ Sylvester โดยพื้นฐาน และถูกจัดวางให้อยู่ในทฤษฎีทั่วไปของฟังก์ชันโมเบียสบนเซตอันดับบางส่วนโดย Rota ในปี 1964 ซึ่งเป็นจุดสำคัญของคณิตศาสตร์เชิงการจัดสมัยใหม่

Key figures

• Abraham de Moivre
• Gian-Carlo Rota

Seminal works

• stanley2011

Frequently asked questions

ทำไมเครื่องหมายถึงสลับกัน?

องค์ประกอบที่อยู่ในหลายเซตจะถูกนับเพิ่มมากเกินไป การลบส่วนที่ซ้อนทับกันเป็นคู่เป็นการแก้ไขที่มากเกินไป ดังนั้นส่วนที่ซ้อนทับกันสามส่วนจึงถูกบวกกลับเข้าไป ทำให้เกิดรูปแบบสลับที่ทำให้แต่ละองค์ประกอบถูกนับเพียงครั้งเดียวเท่านั้น

ความเชื่อมโยงกับฟังก์ชันโมเบียสคืออะไร?

หลักการเพิ่มเข้า-ตัดออกเป็นกรณีพิเศษของการผกผันของโมเบียสบนแลตทิซบูลีนของเซตย่อย ซึ่งฟังก์ชันโมเบียสมีค่าเป็นบวกหรือลบหนึ่ง