Tag Archives: dyck path

เส้นทางของดิกและจำนวนคาตาลัน

บล็อกนี้จะแสดงถึงวิธีไล่เส้นทางของดิก (Dyck path) อย่างเป็นระบบ เส้นทางของดิกสำหรับสี่เหลี่ยมจตุรัสขนาด n x n หน่วย คือ เส้นทางที่ลากจากมุมซ้ายล่าง ไปมุมขวาบน โดยลากไปทางขวาหรือขึ้นข้างบนอย่างใดอย่างหนึ่งเท่านั้น ครั้งละ 1 หน่วย และห้ามลากเหนือเส้นทแยงมุมซ้ายล่าง-ขวาบน คำถามคือ สำหรับแต่ละ n เส้นทางของดิกจะลากได้กี่แบบ เช่น สำหรับสี่เหลี่ยมจตุรัสขนาด 3 x 3 หน่วยจะลากได้ 5 แบบ ดังรูปในแผ่นคำถาม สำหรับสี่เหลี่ยมจตุรัสขนาด 4 x 4 หน่วย จะลากได้ 14 แบบดังรูป แต่จะไล่ให้เป็นระบบได้อย่างไร ? … Continue reading

Posted in บทความ | Tagged , , , | Leave a comment