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

บล็อกนี้จะแสดงถึงวิธีไล่เส้นทางของดิก (Dyck path) อย่างเป็นระบบ

right-and-up-2

เส้นทางของดิกสำหรับสี่เหลี่ยมจตุรัสขนาด n x n หน่วย คือ เส้นทางที่ลากจากมุมซ้ายล่าง ไปมุมขวาบน โดยลากไปทางขวาหรือขึ้นข้างบนอย่างใดอย่างหนึ่งเท่านั้น ครั้งละ 1 หน่วย และห้ามลากเหนือเส้นทแยงมุมซ้ายล่าง-ขวาบน คำถามคือ สำหรับแต่ละ n เส้นทางของดิกจะลากได้กี่แบบ เช่น สำหรับสี่เหลี่ยมจตุรัสขนาด 3 x 3 หน่วยจะลากได้ 5 แบบ ดังรูปในแผ่นคำถาม

450px-Catalan_number_4x4_grid_example.svg

สำหรับสี่เหลี่ยมจตุรัสขนาด 4 x 4 หน่วย จะลากได้ 14 แบบดังรูป แต่จะไล่ให้เป็นระบบได้อย่างไร ? ในที่นี้จะยกตัวอย่าง 2 วิธีด้วยกัน

วิธีที่หนึ่ง: วิธีต่อ

วิธีนี้เกิดจากการวิเคราะห์โจทย์ 4 x 4 ว่าประกอบไปด้วยโจทย์ย่อยขนาด 3 x 3, 2 x 2, 1 x 1 จนถึง 0 x 0 ต่อกัน โดยคำตอบของโจทย์ 4 x 4 จะเกิดจากการต่อกัน 4 ประเภท

1. “หาง” ขนาด 1 x 1 ต่อกับโจทย์ 3 x 3 ได้ 5 แบบ

เช่นเดียวกับ คำตอบของโจทย์ 3 x 3 ซึ่งแสดงไว้ข้างบน

tail-1

2. “หาง” ขนาด 2 x 2 ต่อกับโจทย์ 2 x 2 อีกอันหนึ่ง ได้ 2 แบบ

สังเกตว่า “หาง” นั้น ต้องไม่ “แตะ” เส้นทแยงมุมเลย เพราะถ้าแตะกรณีจะซ้ำกับหางขนาด 1 x 1

tail-2

3. “หาง” ขนาด 3 x 3 ต่อกับโจทย์ 1 x 1 ได้อีก 2 แบบ

เพราะ “หาง” ขนาด 3 x 3 มี 2 แบบ ทำไม “หาง” ขนาด 3 x 3 มีสองแบบ ลองวิเคราะห์ดี ๆ จะพบว่า “หาง” ขนาด 3 x 3 จะเท่ากับ คำตอบของโจทย์ขนาด 2 x 2 นั่่นเอง นั่นเป็นเพราะว่า ถ้าจะไม่ “แตะ” เส้นทแยงมุมขนาด 3 (เส้นประสีดำ) ก็คือ ปัญหาเดียวกันกับการที่อนุญาตให้ “แตะ” เส้นทแยงมุมขนาด 2 แต่ห้ามทะลุ (เส้นประสีแดง) ที่จริงแล้ว “หาง” ขนาด n x n จะมีจำนวนเท่ากับ โจทย์ขนาด n-1 x n-1

tail-3

4. “หาง” ขนาด 4 x 4 มีทั้งหมด 5 แบบ

ซึ่งสอดคล้องกับคำตอบของโจทย์ขนาด 3 x 3 นั่นเอง   

tail-4

สรุปวิธีแรก

first

ถ้าคิดว่าโจทย์ขนาด 0 x 0 ลากได้ 1 แบบ จะได้ข้อสรุปแบบทั่วไปว่า สำหรับโจทย์ขนาด 4 x 4 สามารถวิเคราะห์ออกเป็น 4 ส่วนคือ

  1. “หาง” ขนาด 1 x 1 (เท่ากับ โจทย์ 0 x 0) ต่อกับโจทย์ 3 x 3 ได้ 5 แบบ
  2. “หาง” ขนาด 2 x 2 (เท่ากับ โจทย์ 1 x 1) ต่อกับโจทย์ 2 x 2 ได้ 2 แบบ
  3. “หาง” ขนาด 3 x 3 (เท่ากับ โจทย์ 2 x 2) ต่อกับโจทย์ 1 x 1 ได้ 2 แบบ
  4. “หาง” ขนาด 4 x 4 (เท่ากับ โจทย์ 3 x 3) ต่อกับโจทย์ 0 x 0 ได้ 5 แบบ

รวม 14 แบบนั่นเอง

คำตอบของโจทย์นี้เรียกว่า จำนวนคาตาลัน (Catalan number)  เช่น คำตอบของโจทย์ 0 x 0 เรียกว่า C0= 1 คำตอบของโจทย์ 1 x 1 เรียกว่า C1 = 1  คำตอบของโจทย์ 2 x 2 เรียกว่า C2 = 2 คำตอบของโจทย์ 3 x 3 เรียกว่า C3 = 5 สังเกตว่า การสร้างเลขคาตาลันตัวต่อไป จะเท่ากับการนำเลขของคาตาลันตัวก่อน ๆ มาคูณโดยจับคู่กลับลำดับกัน เช่น C3 = C0C2 + C1C1+ C2C0 หรือนิยามเป็นสูตรแบบทางการดังด้านล่าง

formula

นิยามแบบนี้เรียกว่า นิยามแบบเวียนซ้ำ (recursive definition) คือต้องไล่เลขก่อน ๆ หน้า มาก่อน แล้วจึงได้เลขตัวที่ต้องการ (อาจนึกถึงลำดับฟีโบนักชี ที่นำเลขสองตัวก่อนหน้ามาบวกกันเริ่มจาก 1 , 1 เช่น 1 + 1 = 2; 1 + 2 = 3; 2 + 3 =5 เป็นลำดับ 1,1,2,3,5,8,… )

วิธีที่สอง: วิธีหมุน

วิธีที่สองที่อาจจะเข้าใจยากสักหน่อย แต่ดีกว่าวิธีแรกตรงที่ได้สูตรออกมาเป็นรูปปิด (Closed-form) คือ คำนวณทีเดียวเสร็จได้คำตอบเลย ไม่ต้องไล่เลขก่อน ๆ หน้า วิธีนี้เกิดจากข้อสังเกต 2 ประการ

ข้อสังเกตที่ 1: จำนวนวิธีเมื่อตัดเงื่อนไขเรื่องห้ามลากเหนือเส้นทแยงมุม

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

example

ดังนั้นหากตัดเงื่อนไขเรื่องเส้นทแยงมุม แล้วเขียน “ขวา” และ “ขึ้น” ให้ครบอย่างละ 3 ครั้ง จะว่าวิธีลากจากมุมซ้ายล่างไปมุมขวาบนมี 20 แบบ วิธีการคิดคือในการเขียน 6 ครั้ง ต้องเลือกเขียน “ขวา” 3 ครั้ง ส่วนที่เหลือเขียน “ขึ้น” ดังนั้นจึงใช้ {6 \choose 3} = 20 วิธี และสำหรับกรณีโจทย์ n x n จะใช้ {2n \choose n} วิธี

ข้อสังเกตที่ 2: วิธีหมุนเพื่อปรับให้อยู่ในเงื่อนไขห้ามลากเหนือเส้นทแยงมุม

dyck path class

ใน 20 แบบนี้ ย่อมมีบางแบบที่อยู่ “สามเหลี่ยมซ้ายบน” อย่างเดียว บางแบบอยู่ “สามเหลี่ยมขวาล่าง” อย่างเดียว (คือวิธีที่เราต้องการ) และบางแบบก็ทะลุเส้นทแยงมุม เราจะนับคะแนนที่เรียกว่าคะแนนบุกรุก (exceedance score) คือ นับว่ามีการลาก “ขึ้น” อยู่ใน “สามเหลี่ยมซ้ายบน” กี่ตัว เช่น วิธีลาก ขวา-ขึ้น-ขึ้น-ขวา-ขึ้น-ขวา มีคะแนนบุกรุกเท่ากับ 2 เพราะมีการลาก “ขึ้น” อยู่ใน “สามเหลี่ยมซ้ายบน” สองครั้ง สังเกตว่า หากคะแนนบุกรุกเท่ากับ 0 ก็จะตรงกับเงื่อนไขโจทย์ที่ว่าห้ามลากเหนือเส้นทแยงมุม

Catalan_number_swapping_example

เราสามารถหมุนเส้นทางเก่าที่มีคะแนนบุกรุกให้ต่ำลงได้ วิธีการคือ

  1. เล็งจุดหมุน “จุดหมุน” คือ ลูกศร “ขวา” ตัวแรกที่ชี้กลับมาเส้นทแยงมุม (ลูกศรสีดำในภาพ)
  2. สลับหัวกับหาง “หัว”คือเส้นทางก่อนจุดหมุน (เส้นทางสีแดงในภาพ) กับ “หาง” คือ เส้นทางหลังจุดหมุน (เส้นทางสีเขียวในภาพ)

วิธีหมุนนี้จะทำให้คะแนนบุกรุกลดลงเรื่อย ๆ เช่น โจทย์ 3 x 3 รูปที่มีคะแนนบุกรุก 3 หากหมุนแบบนี้หนึ่งครั้ง คะแนนบุกรุกก็จะลดเหลือ 2 หมุนอีกครั้ง คะแนนบุกรุกก็จะลดเหลือ 1  หมุนอีกครั้ง คะแนนบุกรุกก็จะลดเหลือ 0 ลักษณะเหมือนการเปลี่ยนร่างมอนสเตอร์

dyck path transition

คิดในทางกลับกัน ทุก ๆ “ร่างสุดท้าย” ที่มีคะแนนบุกรุก 0 ย่อมมีร่างอื่นที่มีคะแนนบุกรุก 1 หรือ 2 หรือ 3 ดังนั้น สำหรับภาพ 20 แบบ จะถูกจับกลุ่ม กลุ่มละ 4 ร่าง ได้จำนวนร่างสุดท้ายเท่ากับจำนวนกลุ่ม คือ 20/4 = 5 แบบ ซึ่งเป็นคำตอบของโจทย์ ขนาด 3 x 3

สำหรับโจทย์ขนาด n x n ถ้าตัดเงื่อนไขเส้นทแยงมุม จะลากได้ {2n \choose n} วิธี และถ้าเพิ่มเงื่อนไขเส้นทแยงมุม รูปแบบจะถูกจับกลุ่ม กลุ่มละ n+1 ร่าง ได้ทั้งหมด \frac{1}{n+1} {2n \choose n} วิธี และนี่เป็นสูตรแบบคำนวณทีเดียวเสร็จ (closed form) ของจำนวนคาตาลัน

closed-form

ยกตัวอย่างเช่น คำตอบของโจทย์ 4 x 4 = \frac{1}{4+1} {8 \choose 4} = \frac{1}{5} {8 \choose 4} = \frac{70}{5} =14  วิธี

แหล่งอ้างอิง

ภาพและเนื้อหาบางส่วนนำมาจากบทความวิกิพีเดียภาษาอังกฤษเรื่อง Catalan number ซึ่งมีรายละเอียดเรื่องโจทย์และวิธีการอื่น ๆ ที่ไล่คำตอบของโจทย์อย่างเป็นระบบ อ่านเพิ่มเติมได้สำหรับผู้ที่สนใจ

Advertisements
This entry was posted in บทความ and tagged , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s