จำนวนแคทาแลน

จากวิกิพีเดีย สารานุกรมเสรี

ในคณิตศาสตร์เชิงการจัด จำนวนแคทาแลน (Catalan numbers) ปรากฏอยู่ในปัญหาการนับหลายๆปัญหา โดยส่วนใหญ่มักอยู่ในรูปการเรียกซ้ำ (recursive) จำนวนแคทาแลนถูกตั้งชื่อโดยนักคณิตศาสตร์ชาวเบลเยียมชื่อ Eugène Charles Catalan (ค.ศ. 1814–1894)

จำนวนแคทาแลนตัวที่ n สามารถหาได้โดยใช้สูตรสัมประสิทธิ์ทวินาม ดังนี้

$C_n = \frac{1}{n+1}{2n\choose n} = \frac{(2n)!}{(n+1)!\,n!}$ สำหรับ $n\ge 0$

จำนวนแคทาแลนตัวที่ 0, 1, 2, 3, … คือ

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, …

[แก้] คุณสมบัติ

C_n สามารถเขียนอีกแบบได้

$C_n = {2n\choose n} - {2n\choose n-1}$ สำหรับ $n\ge 1$

ซึ่งแสดงให้เห็นว่า C_n เป็นจำนวนธรรมชาติ

จำนวนแคทาแลน เขียนในรูปความสัมพันธ์เวียนเกิด ได้ดังนี้

$C_0 = 1 \quad$ และ $C_{n+1}=\sum_{i=0}^{n}C_i\,C_{n-i}$ สำหรับ $n\ge 0$

หรือเขียนอีกแบบได้

$C_0 = 1 \quad$ และ $C_{n+1}=\frac{2(2n+1)}{n+2}C_n$

ซึ่งสามารถคำนวณได้ง่ายกว่า

จำนวนแคทาแลนมีค่าประมาณ

$C_n \sim \frac{4^n}{n^{3/2}\sqrt{\pi}}$

[แก้] การประยุกต์ใช้

C_n คือจำนวนของ Dyck word ที่มีความยาว 2n. Dyck word คือ ข้อความที่ประกอบด้วย X และ Y อย่างละ n ตัว และเมื่ออ่านข้อความจากทางซ้ายทีละตัวอักษร จะไม่มีทางนับจำนวนตัว Y ได้มากกว่าตัว X. ตัวอย่าง Dyck words ที่มีความยาว 6

XXXYYY XYXXYY XYXYXY XXYYXY XXYXYY

C_n คือจำนวนวงเล็บ n คู่ทั้งหมดที่อยู่ในลำดับที่ถูกต้อง

((())) ()(()) ()()() (())() (()())

C_n คือจำนวนต้นไม้ทวิภาค (binary tree) ที่มีใบ n + 1 ใบทั้งหมดที่เป็นไปได้

C_n คือ จำนวนวิถีทางเดียว (monotonic path) ทั้งหมดบนตารางขนาด n × n ช่อง ที่ไม่ตัดเส้นทแยงมุม. วิถีทางเดียว คือ เส้นทางที่เริ่มจากมุมล่างซ้าย และจบที่มุมบนขวา โดยเส้นเชื่อมจะชี้ไปทางขวา หรือข้างบนได้เท่านั้น. ตัวอย่างกรณี n = 3:

C_n คือจำนวนวิธีตัดรูปหลายเหลี่ยมที่มี n + 2 ด้านให้เป็นรูปสามเหลี่ยม โดยการตัดจะตัดจากจุดยอดของรูป และตัดเป็นเส้นตรง. ตัวอย่าง กรณี n = 4:

[แก้] ประวัติ

ลำดับแคทาแลนถูกค้นพบตั้งแต่คริสต์ศตวรรษที่ 18 โดยเลออนฮาร์ด ออยเลอร์ ซึ่งเขาสนใจจำนวนวิธีตัดรูปหลายเหลี่ยมเป็นรูปสามเหลี่ยม. ลำดับนี้ถูกตั้งชื่อโดย Eugène Charles Catalan เขาได้ค้นพบว่าจำนวนแคทาแลนมีความเกี่ยวข้องกับจำนวนวงเล็บทั้งหมดที่เป็นไปได้

[แก้] อ้างอิง

Stanley, R.P. (1999): Enumerative Combinatorics, Vol. 2. Cambridge University Press. (pp. 219-229)

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

ดึงข้อมูลจาก "http://th.wikipedia.org../../../%E0%B8%88/%E0%B8%B3/%E0%B8%99/%E0%B8%88%E0%B8%B3%E0%B8%99%E0%B8%A7%E0%B8%99%E0%B9%81%E0%B8%84%E0%B8%97%E0%B8%B2%E0%B9%81%E0%B8%A5%E0%B8%99.html".

หมวดหมู่: บทความเกี่ยวกับ คณิตศาสตร์ ที่ยังไม่สมบูรณ์ | ลำดับจำนวนเต็ม | การเรียงสับเปลี่ยน