อะไรคือข้อพิสูจน์โดยตรงของความสัมพันธ์การเกิดซ้ำเกี่ยวกับการแจกแจงเส้นทางตาข่ายที่ Bizley มอบให้?
ปล่อย $k$ เป็นจำนวนเต็มไม่ติดลบและปล่อยให้ $m,n$เป็นจำนวนเต็มบวก coprime ปล่อย$\phi_k$ เป็นจำนวนของเส้นทางตาข่ายจาก $(0,0)$ ถึง $(km,kn)$ ด้วยขั้นตอน $(0,1)$ และ $(1,0)$ ที่ไม่เคยอยู่เหนือเส้น $my=nx$. เส้นทางที่มีคุณสมบัตินี้จะเรียกว่า a$\phi$-เส้นทาง. จากนั้น$\phi_k$ ตอบสนองความสัมพันธ์การเกิดซ้ำ $$ k(m+n)\phi_k = \sum_{j=1}^{k}\binom{j(m+n)}{jm}\phi_{k-j} $$ สำหรับทุกอย่าง $k \in \mathbb{Z}^+$ที่แสดงโดยBizley (1954)
Bizley ระบุว่า“ ความสัมพันธ์เหล่านี้สามารถอนุมานได้โดยตรงโดยการให้เหตุผลทั่วไปจากคุณสมบัติทางเรขาคณิตของเส้นทาง” อย่างไรก็ตามฉันไม่สามารถจัดการเพื่อให้ได้รับการพิสูจน์แบบผสมผสานของทฤษฎีบทนี้
คำถาม:อะไรคือข้อพิสูจน์โดยตรงของความสัมพันธ์การเกิดซ้ำดังกล่าวข้างต้น?
ความคิดแรกของฉันเกี่ยวกับความสัมพันธ์นี้คือด้านซ้ายมือของสมการจะนับจำนวนการเรียงสับเปลี่ยนของวัฏจักรของทั้งหมด $\phi$- เส้นทางจาก $(0,0)$ ถึง $(km,kn)$. ในกระดาษของเขา Bizley กำหนดจุดสูงสุดของเส้นทางขัดแตะว่า“ จุดขัดแตะ$X$ บนเส้นทางที่เป็นเส้นไล่ระดับ $\frac{n}{m}$ ผ่าน $X$ ตัดแกน y ที่ค่า $y$ไม่น้อยกว่าที่ตรงกับจุดขัดแตะอื่น ๆ ของเส้นทาง” (สิ่งสำคัญคือต้องสังเกตว่าจุดแรก$(0,0)$ ถือว่าไม่ได้เป็นของเส้นทาง) ดังนั้นจำนวนการเรียงสับเปลี่ยนของวัฏจักรของทั้งหมด $\phi$- เส้นทางอาจแสดงเป็นผลรวมของ $t$ คูณจำนวนของเส้นทางตาข่ายทั้งหมดด้วย $t$ คะแนนสูงสุดสำหรับทุกคน $t=1,2,\ldots,k$. อย่างไรก็ตามเห็นได้ชัดว่าด้านขวามือของสมการไม่เกี่ยวข้องกับจำนวนของเส้นทางตาข่ายที่มีจำนวนจุดสูงสุดที่ระบุ
ฉันกลัวว่าฉันพลาดอะไรบางอย่างที่ชัดเจนเกี่ยวกับคุณสมบัติทางเรขาคณิตของไฟล์ $\phi$- เส้นทางและฉันจะดีใจมากถ้าใครสามารถให้หลักฐานหรือกลอุบายแบบผสมผสานที่ฉันไม่สามารถจัดการให้เห็นได้ ขอขอบคุณสำหรับความสนใจของคุณล่วงหน้า
คำตอบ
เคล็ดลับคือการเพิ่ม $\phi_k$ไปยังทั้งสองด้านของสมการและตีความทางด้านซ้ายมือว่าเป็นเส้นทางการนับโดยมีขั้นตอนแนวนอนที่อยู่ข้างหน้า จากนั้นให้ทำขั้นตอนที่ทำเครื่องหมายไว้เป็นขั้นตอนแรกของเส้นทางจาก$(-1, 0)$ ถึง $(km, kn)$. ปล่อย$j$ น้อยที่สุดเพื่อให้เส้นทางนี้ไปถึง $(jm, jn)$ และอยู่ด้านล่าง $my = nx$หลังจากนั้น. จากนั้นขั้นตอนก่อนถึงจุดนัดพบโดยไม่รวมขั้นตอนสุดท้ายในแนวนอนสร้างเส้นทางโดยพลการซึ่งนับโดยสัมประสิทธิ์ทวินามใน summand พร้อมดัชนี$j$และขั้นตอนที่เหลือจะสร้างเส้นทางที่นับโดย $\phi_{k-j}$.