การแบ่งส่วน (ทฤษฎีจำนวน)
ในทฤษฎีจำนวนและ combinatorics พาร์ติชันของจำนวนเต็มบวก n หรือที่เรียกว่าพาร์ติชันจำนวนเต็มเป็นวิธีการเขียน n เป็นผลรวมของจำนวนเต็มบวก ผลรวมสองรายการที่แตกต่างกันตามลำดับของพาร์ทิชันเดียวกันเท่านั้น (ถ้าคำสั่งมีความสำคัญผลรวมจะกลายเป็นองค์ประกอบ) ตัวอย่างเช่น 4 สามารถแบ่งพาร์ติชันได้ 5 วิธีดังนี้
4
3 + 1
2 + 2
2 + 1 + 1
1 + 1 + 1 + 1
องค์ประกอบที่ขึ้นอยู่กับลำดับที่ 1 + 3 เป็นพาร์ติชันเดียวกับ 3 + 1 ในขณะที่องค์ประกอบที่แตกต่างกัน 2 + 1 + 2 + 1 และ 1 + 1 + 2 หมายถึงพาร์ติชันเดียวกัน 2 + 1 + 1ข้อสรุปในพาร์ทิชันเรียกอีกอย่างหนึ่งว่า จำนวนพาร์ทิชันของ n จะได้จากฟังก์ชันพาร์ทิชัน p (n) ดังนั้น p (4) = 5. สัญกรณ์λ⊢ n หมายความว่าλเป็นพาร์ติชันของ nพาร์ติชันสามารถแสดงภาพได้ด้วยไดอะแกรม Diagrams หรือ Ferrers พวกเขาเกิดขึ้นในหลายสาขาของคณิตศาสตร์และฟิสิกส์รวมทั้งการศึกษาสมมาตรพหุนามกลุ่มสมมาตรและทฤษฎีการแสดงกลุ่มโดยทั่วไป
ตัวอย่าง
พาร์ติชันของ 5 มี 7 แบบ คือ
5
4 +1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1
ในบางแหล่งพาร์ทิชันจะถือว่าเป็นลำดับของ summands มากกว่าเป็นการแสดงออกที่มีเครื่องหมายบวก ยกตัวอย่างเช่นพาร์ติชัน 2 + 2 + 1 อาจเขียนแทนเป็น tuple (2, 2, 1) หรือในแบบกระชับมากยิ่งขึ้น (2² ,1) โดยที่ superscript แสดงจำนวน repetitions ของคำตอบ
ตัวอย่างโค้ดการแบ่งของพาร์ติชัน
def partition(n, c=[], k=1): if n == 0: yield c for i in range(k, n + 1): for p in partition(n - i, c + [i], i): yield p# Example: Partition 10 as a sum of integersfor j in partition(5): print ' + '.join(map(str, j))
ดูเพิ่ม
- พาร์ติชั่นของเซต