Bizley가 제공 한 격자 경로 열거에 대한 재발 관계의 직접적인 증거는 무엇입니까?

Jan 15 2021

허락하다 $k$ 음이 아닌 정수이고 $m,n$코 프라임 양의 정수입니다. 허락하다$\phi_k$ 격자 경로의 수 $(0,0)$ ...에 $(km,kn)$ 단계로 $(0,1)$$(1,0)$ 선 위로 절대 올라가지 않는 $my=nx$. 이 속성을 가진 경로는$\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$-paths와 내가 볼 수없는 조합 증명이나 트릭을 누군가 제공 할 수 있다면 너무 기쁠 것입니다. 미리 관심을 가져 주셔서 감사합니다.

답변

3 MartinRubey Jan 31 2021 at 22:21

트릭은 추가하는 것입니다 $\phi_k$방정식의 양쪽에 추가하고 왼쪽을 수평 단계가 앞에 추가되고 단계 중 하나가 표시된 계산 경로로 해석합니다. 그런 다음 표시된 단계를 경로의 첫 번째 단계로 만듭니다.$(-1, 0)$ ...에 $(km, kn)$. 허락하다$j$ 이 경로는 $(jm, jn)$ 아래 유지 $my = nx$그 후. 그런 다음 최종 수평 단계를 제외하고 만나는 지점 이전 단계는 인덱스가있는 합계의 이항 계수로 계산되는 임의 경로를 형성합니다.$j$, 나머지 단계는 $\phi_{k-j}$.