418531 ภาคต้น 2552/โจทย์ปัญหาการวิเคราะห์เชิงการจัด/เฉลยข้อ 5

ข้อ 1

เนื่องจากวิธีการเดินจาก (0,0) ไปยัง (m,n) คือลำดับของการเดินที่มีการเดินไปทางขวา m ครั้งและมีการเดินไปข้างบน n ครั้ง เราจึงสามารถแทนการเดินไปทางซ้ายด้วยเลข 0 จำนวน m ตัวและการเดินไปทางขวาด้วยเลข 1 จำนวน n ตัว วิธีการเดินจึงสามารถแทนด้วยบิตสตริงความยาว m+n ที่มีเลข 0 จำนวน m ตัวและมีเลข 1 จำนวน n ตัว

ข้อ 2

จำนวนบิตสตริงความยาว m+n ที่มีเลข 0 จำนวน m ตัวมีอยู่ทั้งหมด ${m+n \choose m}\,$ ตัว ดังนั้นจึงมีวิธีเดินจาก (0,0) ไปยัง (m,n) เป็นจำนวนเท่่ากัน