Apa bukti langsung dari relasi pengulangan tentang pencacahan jalur kisi yang diberikan oleh Bizley?
Membiarkan $k$ menjadi integer nonnegatif dan biarkan $m,n$menjadi bilangan bulat positif coprime. Membiarkan$\phi_k$ menjadi jumlah jalur kisi dari $(0,0)$ untuk $(km,kn)$ dengan langkah-langkah $(0,1)$ dan $(1,0)$ yang tidak pernah melampaui batas $my=nx$. Sebuah jalan yang memiliki properti ini akan disebut a$\phi$-path. Kemudian,$\phi_k$ memenuhi hubungan perulangan $$ k(m+n)\phi_k = \sum_{j=1}^{k}\binom{j(m+n)}{jm}\phi_{k-j} $$ untuk semua $k \in \mathbb{Z}^+$, seperti yang ditunjukkan oleh Bizley (1954) .
Bizley telah menyatakan bahwa "hubungan ini dapat disimpulkan secara langsung dengan penalaran umum dari sifat geometris jalur". Namun, saya tidak dapat memperoleh bukti kombinatorial dari teorema ini.
Pertanyaan: Apa bukti langsung dari relasi perulangan yang disebutkan di atas?
Pikiran pertama saya tentang hubungan ini adalah bahwa sisi kiri persamaan menghitung jumlah permutasi siklus semua. $\phi$-path dari $(0,0)$ untuk $(km,kn)$. Dalam makalahnya, Bizley mendefinisikan titik tertinggi dari jalur kisi sebagai “titik kisi$X$ di jalan sedemikian rupa sehingga garis gradien $\frac{n}{m}$ melalui $X$ memotong sumbu y pada nilai $y$tidak kurang dari itu sesuai dengan titik kisi lain dari jalur tersebut ”. (Penting untuk dicatat bahwa poin pertama$(0,0)$ dianggap tidak termasuk dalam sang jalan.) Jadi, jumlah permutasi siklus dari semua $\phi$-path dapat diekspresikan sebagai jumlah dari $t$ dikalikan jumlah semua jalur kisi dengan tepat $t$ poin tertinggi untuk semua $t=1,2,\ldots,k$. Namun, ternyata persamaan ruas kanan tidak ada hubungannya dengan jumlah lattice path dengan jumlah titik tertinggi tertentu.
Saya khawatir saya kehilangan sesuatu yang jelas tentang sifat geometris dari $\phi$-paths dan saya akan sangat senang jika ada yang bisa memberikan bukti atau trik kombinatorial yang tidak bisa saya lihat. Terima kasih atas perhatian Anda sebelumnya.
Jawaban
Triknya adalah menambahkan $\phi_k$ke kedua ruas persamaan, dan tafsirkan ruas kiri sebagai jalur penghitungan dengan anak tangga horizontal di awal, dan salah satu anak tangganya ditandai. Kemudian, buat langkah yang ditandai sebagai langkah pertama dari sebuah jalur$(-1, 0)$ untuk $(km, kn)$. Membiarkan$j$ seminimal mungkin sehingga jalur ini berhasil $(jm, jn)$ dan tetap di bawah $my = nx$setelah itu. Kemudian langkah-langkah sebelum titik pertemuan, tidak termasuk langkah horizontal terakhir, membentuk jalur arbitrer yang dihitung oleh koefisien binomial di penjumlahan dengan indeks$j$, dan langkah yang tersisa membentuk jalur yang dihitung $\phi_{k-j}$.