Βασιλιάς στη σκακιέρα & Τριωνυμικό τρίγωνο

Τοποθετείται ένας βασιλιάς στην κορυφή μιας (άπειρης) σκακιέρας. Σε κάθε βήμα κατέρχεται κατά μία γραμμή, επιτρέπονται μόνο οι τρεις ελάχιστες κινήσεις: κάτω–αριστερά, κάτω, κάτω–δεξιά.

Αν $T(n,k)$ δηλώνει τον αριθμό ελάχιστων διαδρομών προς το τετράγωνο της $n$-ης γραμμής με οριζόντια μετατόπιση $k$ (αρνητική προς τα αριστερά, θετική προς τα δεξιά), τότε ισχύει

$$T(n,k)=T(n-1,k-1)+T(n-1,k)+T(n-1,k+1),T(0,0)=1,$$

δηλαδή ακριβώς η αναδρομή του τριωνυμικού τριγώνου. Κατά συνέπεια, η $n$-η «ζώνη» μετρήσεων συμπίπτει με την $n$-η γραμμή του τριωνυμικού τριγώνου.

Εναλλακτικά,

$$T(n,k)=[x^k](1+x+x^{-1}{)}^n=\sum _{\begin{array}{c}a+b+c=n\\ a-c=k\end{array}}\frac{n!}{a!b!c!},$$

όπου $a,b,c$ είναι, αντίστοιχα, οι αριθμοί κινήσεων κάτω–αριστερά, κάτω και κάτω–δεξιά.

Παράδειγμα (πρώτες γραμμές):
$n=0:\ \ 1$
$n=1:\ \ 1\ \ 1\ \ 1$
$n=2:\ \ 1\ \ 2\ \ 3\ \ 2\ \ 1$

Αιτιολόγηση: κάθε ελάχιστη διαδρομή προς $(n,k)$ προέρχεται υποχρεωτικά από ένα από τα τρία γειτονικά τετράγωνα της προηγούμενης γραμμής $(n-1,k-1)$, $(n-1,k)$, $(n-1,k+1)$. Η πρόσθεση των αντίστοιχων πλήθων δίνει την παραπάνω αναδρομή και «χτίζει» το τριωνυμικό τρίγωνο γραμμή προς γραμμή.