Bằng chứng trực tiếp của quan hệ lặp lại về liệt kê đường dẫn mạng do Bizley đưa ra là gì?
Để cho $k$ là một số nguyên không âm và để $m,n$là số nguyên dương đúng chuẩn. Để cho$\phi_k$ là số đường dẫn mạng tinh thể từ $(0,0)$ đến $(km,kn)$ với các bước $(0,1)$ và $(1,0)$ cái đó không bao giờ vượt lên trên dòng $my=nx$. Đường dẫn có thuộc tính này sẽ được gọi là$\phi$-con đường. Sau đó,$\phi_k$ thỏa mãn mối quan hệ lặp lại $$ k(m+n)\phi_k = \sum_{j=1}^{k}\binom{j(m+n)}{jm}\phi_{k-j} $$ cho tất cả $k \in \mathbb{Z}^+$, như được thể hiện bởi Bizley (1954) .
Bizley đã tuyên bố rằng “những quan hệ này có thể được suy luận trực tiếp bằng suy luận chung từ các tính chất hình học của các đường đi”. Tuy nhiên, tôi không thể quản lý để có được một chứng minh tổ hợp của định lý này.
Câu hỏi: Bằng chứng trực tiếp của quan hệ lặp lại nêu trên là gì?
Suy nghĩ đầu tiên của tôi về mối quan hệ này là vế trái của phương trình đếm số hoán vị theo chu kỳ của tất cả $\phi$-các đường đi từ $(0,0)$ đến $(km,kn)$. Trong bài báo của mình, Bizley định nghĩa điểm cao nhất của đường dẫn mạng là “điểm mạng tinh thể$X$ trên con đường sao cho dòng gradient $\frac{n}{m}$ xuyên qua $X$ cắt trục y ở giá trị $y$không nhỏ hơn tương ứng với bất kỳ điểm mạng nào khác của đường dẫn ”. (Điều quan trọng cần lưu ý là điểm đầu tiên$(0,0)$ được coi là không thuộc đường dẫn.) Như vậy, số hoán vị tuần hoàn của tất cả $\phi$-paths có thể được biểu thị bằng tổng của $t$ nhân với số của tất cả các đường dẫn mạng với chính xác $t$ điểm cao nhất cho tất cả $t=1,2,\ldots,k$. Tuy nhiên, dường như vế phải của phương trình không liên quan gì đến số lượng đường dẫn mạng tinh thể với số điểm cao nhất được chỉ định.
Tôi sợ rằng tôi đang thiếu một cái gì đó rõ ràng về các đặc tính hình học của $\phi$-paths và tôi sẽ rất vui nếu ai đó có thể cung cấp bằng chứng tổ hợp hoặc thủ thuật mà tôi không thể quản lý để xem. Cảm ơn sự chú ý của bạn trước.
Trả lời
Bí quyết là thêm $\phi_k$cho cả hai phía của phương trình và giải thích phía bên trái là đếm các đường đi với một bước ngang được mở rộng trước và một trong các bước của nó được đánh dấu. Sau đó, hãy đặt bước được đánh dấu là bước đầu tiên của con đường từ$(-1, 0)$ đến $(km, kn)$. Để cho$j$ tối thiểu để con đường này chạm tới $(jm, jn)$ và ở bên dưới $my = nx$sau đó. Sau đó, các bước trước điểm gặp gỡ, không bao gồm bước ngang cuối cùng, tạo thành một đường đi tùy ý được tính bằng hệ số nhị thức trong tổng và với chỉ số$j$và các bước còn lại tạo thành một đường dẫn được tính bằng $\phi_{k-j}$.