การแบ่งส่วน (ทฤษฎีจำนวน)

ในทฤษฎีจำนวนและ 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 integers for j in partition(5): print ' + '.join(map(str, j))