Qual é a prova direta da relação de recorrência sobre a enumeração do caminho da rede dada por Bizley?

Jan 15 2021

Deixar $k$ seja um número inteiro não negativo e deixe $m,n$ser inteiros positivos de coprime. Deixar$\phi_k$ seja o número de caminhos de rede de $(0,0)$ para $(km,kn)$ com passos $(0,1)$ e $(1,0)$ que nunca estão subindo acima da linha $my=nx$. Um caminho com essa propriedade será chamado de$\phi$-caminho. Então,$\phi_k$ satisfaz a relação de recorrência $$ k(m+n)\phi_k = \sum_{j=1}^{k}\binom{j(m+n)}{jm}\phi_{k-j} $$ para todos $k \in \mathbb{Z}^+$, como mostrado por Bizley (1954) .

Bizley afirmou que “essas relações podem ser deduzidas diretamente pelo raciocínio geral a partir das propriedades geométricas dos caminhos”. No entanto, não consegui obter uma prova combinatória deste teorema.

Pergunta: Qual é a prova direta da relação de recorrência mencionada acima?

Meu primeiro pensamento sobre esta relação foi que o lado esquerdo da equação conta o número de permutações cíclicas de todos $\phi$-caminhos de $(0,0)$ para $(km,kn)$. Em seu artigo, Bizley define o ponto mais alto de um caminho de rede como "um ponto de rede$X$ no caminho de modo que a linha de gradiente $\frac{n}{m}$ Através dos $X$ corta o eixo y em um valor de $y$não menos do que o correspondente a qualquer outro ponto da rede do caminho ”. (É importante notar que o primeiro ponto$(0,0)$ é considerado como não pertencente ao caminho.) Assim, o número de permutações cíclicas de todos $\phi$-caminhos podem ser expressos como a soma de $t$ vezes o número de todos os caminhos de rede com exatamente $t$ pontos mais altos para todos $t=1,2,\ldots,k$. No entanto, aparentemente, o lado direito da equação não tem nada a ver com o número de caminhos da rede com um número especificado de pontos mais altos.

Receio estar perdendo algo óbvio sobre as propriedades geométricas do $\phi$-paths e eu ficaria muito feliz se alguém pudesse fornecer uma prova combinatória ou truque que eu não consegui ver. Obrigado pela sua atenção antecipadamente.

Respostas

3 MartinRubey Jan 31 2021 at 22:21

O truque é adicionar $\phi_k$para ambos os lados da equação e interpretar o lado esquerdo como caminhos de contagem com uma etapa horizontal prefixada e uma de suas etapas marcada. Em seguida, faça da etapa marcada a primeira etapa de um caminho de$(-1, 0)$ para $(km, kn)$. Deixar$j$ ser mínimo, de modo que este caminho atinja $(jm, jn)$ e fica abaixo $my = nx$depois disso. Em seguida, as etapas antes do ponto de encontro, excluindo a etapa horizontal final, formam um caminho arbitrário contado pelo coeficiente binomial na soma e com índice$j$, e as etapas restantes formam um caminho contado por $\phi_{k-j}$.