Jaki jest bezpośredni dowód na relację powtarzania w wyliczaniu ścieżek kratowych podany przez Bizleya?

Jan 15 2021

Pozwolić $k$ być nieujemną liczbą całkowitą i niech $m,n$być liczbami całkowitymi względnie liczbami całkowitymi dodatnimi. Pozwolić$\phi_k$ być liczbą ścieżek kratowych z $(0,0)$ do $(km,kn)$ ze stopniami $(0,1)$ i $(1,0)$ które nigdy nie wznoszą się ponad linię $my=nx$. Ścieżka posiadająca tę właściwość będzie nazywana a$\phi$-ścieżka. Następnie,$\phi_k$ spełnia relację powtarzania $$ k(m+n)\phi_k = \sum_{j=1}^{k}\binom{j(m+n)}{jm}\phi_{k-j} $$ dla wszystkich $k \in \mathbb{Z}^+$, jak pokazuje Bizley (1954) .

Bizley stwierdził, że „relacje te można wydedukować bezpośrednio poprzez ogólne rozumowanie z geometrycznych właściwości ścieżek”. Nie udało mi się jednak uzyskać kombinatorycznego dowodu tego twierdzenia.

Pytanie: Jaki jest bezpośredni dowód na wspomnianą powyżej relację nawrotów?

Moją pierwszą myślą o tej relacji było to, że lewa strona równania liczy liczbę cyklicznych permutacji wszystkich $\phi$-ścieżki z $(0,0)$ do $(km,kn)$. W swoim artykule Bizley definiuje najwyższy punkt ścieżki sieciowej jako „punkt kraty$X$ na ścieżce tak, że linia gradientu $\frac{n}{m}$ przez $X$ przecina oś Y przy wartości $y$nie mniej niż odpowiadający jakiemukolwiek innemu punktowi kratownicy ścieżki ”. (Ważne jest, aby pamiętać, że pierwszy punkt$(0,0)$ uważa się, że nie należy do ścieżki). Zatem liczba cyklicznych permutacji wszystkich $\phi$-ścieżki można wyrazić jako sumę $t$ razy liczba wszystkich ścieżek sieci z dokładnie $t$ najwyższe punkty dla wszystkich $t=1,2,\ldots,k$. Jednak najwyraźniej prawa strona równania nie ma nic wspólnego z liczbą ścieżek sieci o określonej liczbie najwyższych punktów.

Obawiam się, że brakuje mi czegoś oczywistego w geometrycznych właściwościach pliku $\phi$-paths i byłbym bardzo zadowolony, gdyby ktoś mógł dostarczyć kombinatoryczny dowód lub sztuczkę, której nie udało mi się zobaczyć. Z góry dziękuję za uwagę.

Odpowiedzi

3 MartinRubey Jan 31 2021 at 22:21

Sztuczka polega na dodaniu $\phi_k$po obu stronach równania i zinterpretować lewą stronę jako liczące się ścieżki z dołączonym poziomym krokiem i zaznaczonym jednym z jego kroków. Następnie zrób zaznaczony krok jako pierwszy stopień ścieżki od$(-1, 0)$ do $(km, kn)$. Pozwolić$j$ być minimalne, tak aby ta ścieżka trafiła $(jm, jn)$ i pozostaje poniżej $my = nx$po tym. Następnie kroki przed punktem spotkania, z wyłączeniem ostatniego kroku poziomego, tworzą dowolną ścieżkę liczoną przez współczynnik dwumianowy w szczycie o indeksie$j$, a pozostałe kroki tworzą ścieżkę liczoną według $\phi_{k-j}$.