Bizley tarafından verilen kafes yolu numaralandırmasıyla ilgili tekrarlama ilişkisinin doğrudan kanıtı nedir?
İzin Vermek $k$ negatif olmayan bir tam sayı olmak ve izin vermek $m,n$coprime pozitif tamsayılar olabilir. İzin Vermek$\phi_k$ örgü yollarının sayısı $(0,0)$ -e $(km,kn)$ adımlarla $(0,1)$ ve $(1,0)$ asla çizginin üzerine çıkmayanlar $my=nx$. Bu özelliğe sahip bir yola,$\phi$-yol. Sonra,$\phi_k$ tekrarlama ilişkisini karşılar $$ k(m+n)\phi_k = \sum_{j=1}^{k}\binom{j(m+n)}{jm}\phi_{k-j} $$ hepsi için $k \in \mathbb{Z}^+$Bizley (1954) tarafından gösterildiği gibi .
Bizley, “bu ilişkilerin doğrudan yolların geometrik özelliklerinden genel akıl yürütme ile çıkarılabileceğini” belirtmiştir. Ancak, bu teoremin kombinasyonel bir kanıtını elde etmeyi başaramadım.
Soru: Yukarıda bahsedilen tekrarlama ilişkisinin doğrudan kanıtı nedir?
Bu ilişki hakkındaki ilk düşüncem, denklemin sol tarafının tüm döngüsel permütasyonların sayısını saydığıydı. $\phi$-dan yollar $(0,0)$ -e $(km,kn)$. Bizley makalesinde, bir kafes yolunun en yüksek noktasını "kafes noktası$X$ yolda, gradyan çizgisi $\frac{n}{m}$ vasıtasıyla $X$ y eksenini bir değerde keser $y$yolun diğer herhangi bir kafes noktasına karşılık gelenden daha az değil ”. (İlk noktanın$(0,0)$ yola ait olmadığı kabul edilir.) Bu nedenle, tümünün döngüsel permütasyonlarının sayısı $\phi$-yollar toplamı olarak ifade edilebilir $t$ tam olarak tüm kafes yollarının sayısının çarpımı $t$ herkes için en yüksek puan $t=1,2,\ldots,k$. Bununla birlikte, görünüşe göre denklemin sağ tarafının, belirli bir sayıda en yüksek noktaya sahip kafes yollarının sayısıyla ilgisi yoktur.
Korkarım, nesnenin geometrik özellikleriyle ilgili bariz bir şeyi kaçırıyorum. $\phi$-yollar ve ben görmeyi başaramadığım bir kombinatoryal kanıt veya numara sunabilen biri olursa çok sevinirim. İlginiz için şimdiden teşekkürler.
Yanıtlar
İşin püf noktası eklemek $\phi_k$Denklemin her iki tarafına aktarın ve sol tarafı, başında yatay bir adım ve adımlarından biri işaretlenmiş olan sayma yolları olarak yorumlayın. Ardından, işaretli adımı bir yolun ilk adımı yapın$(-1, 0)$ -e $(km, kn)$. İzin Vermek$j$ bu yolun çarpması için asgari düzeyde olun $(jm, jn)$ ve aşağıda kalır $my = nx$Daha sonra. Ardından, son yatay adım hariç buluşma noktasından önceki adımlar, indeksli toplamda iki terimli katsayı ile sayılan keyfi bir yol oluşturur.$j$ve kalan adımlar, sayılan bir yol oluşturur $\phi_{k-j}$.