Qual è la prova diretta della relazione di ricorrenza sull'enumerazione del percorso reticolare fornita da Bizley?

Jan 15 2021

Permettere $k$ essere un numero intero non negativo e let $m,n$essere interi positivi coprimi. Permettere$\phi_k$ essere il numero di percorsi reticolari da $(0,0)$ per $(km,kn)$ con gradini $(0,1)$ e $(1,0)$ che non superano mai la linea $my=nx$. Un percorso con questa proprietà verrà chiamato a$\phi$-sentiero. Poi,$\phi_k$ soddisfa la relazione di ricorrenza $$ k(m+n)\phi_k = \sum_{j=1}^{k}\binom{j(m+n)}{jm}\phi_{k-j} $$ per tutti $k \in \mathbb{Z}^+$, come mostrato da Bizley (1954) .

Bizley ha affermato che “queste relazioni possono essere dedotte direttamente dal ragionamento generale dalle proprietà geometriche dei cammini”. Tuttavia, non sono riuscito a ottenere una dimostrazione combinatoria di questo teorema.

Domanda: qual è la prova diretta della relazione di ricorrenza sopra menzionata?

Il mio primo pensiero su questa relazione è stato che il lato sinistro dell'equazione conta il numero delle permutazioni cicliche di tutti $\phi$-percorsi da $(0,0)$ per $(km,kn)$. Nel suo articolo, Bizley definisce il punto più alto di un percorso reticolare come “un punto reticolare$X$ sul percorso tale che la linea del gradiente $\frac{n}{m}$ attraverso $X$ taglia l'asse y con un valore di $y$non inferiore a quello corrispondente a qualsiasi altro punto reticolare del percorso ”. (È importante notare che il primo punto$(0,0)$ è considerato come non appartenente al sentiero.) Quindi, il numero delle permutazioni cicliche di tutti $\phi$-paths può essere espresso come la somma di $t$ volte il numero di tutti i percorsi reticolari con esattamente $t$ punti più alti per tutti $t=1,2,\ldots,k$. Tuttavia, apparentemente il lato destro dell'equazione non ha nulla a che fare con il numero dei percorsi reticolari con un numero specificato di punti più alti.

Temo che mi manchi qualcosa di ovvio sulle proprietà geometriche di $\phi$-paths e io saremmo così felici se qualcuno potesse fornire una prova o un trucco combinatorio che non sono riuscito a vedere. Grazie per l'attenzione in anticipo.

Risposte

3 MartinRubey Jan 31 2021 at 22:21

Il trucco sta nell'aggiungere $\phi_k$su entrambi i lati dell'equazione e interpretare il lato sinistro come un conteggio di percorsi con un passaggio orizzontale anteposto e uno dei suoi passaggi contrassegnato. Quindi, rendere il passaggio contrassegnato il primo passaggio di un percorso da$(-1, 0)$ per $(km, kn)$. Permettere$j$ essere minimo in modo tale che questo percorso colpisca $(jm, jn)$ e rimane sotto $my = nx$dopo di che. Quindi i passaggi prima del punto di incontro, escluso l'ultimo passaggio orizzontale, formano un percorso arbitrario contato dal coefficiente binomiale nella somma con indice$j$e i passaggi rimanenti formano un percorso contato da $\phi_{k-j}$.