ラティスパス

組合せ論において、集合Sにステップを持つ長さkのd次元整数格子⁠ ⁠内の格子パス Lは、連続する各差がSに含まれるようなベクトル⁠ ⁠のシーケンスです。^{[1]格子パスは}⁠ ⁠内の任意の格子 に存在する可能性がありますが、^[1]整数格子⁠ ⁠ が最も一般的に使用されます。 ${\displaystyle \mathbb {Z} ^{d}}$ ${\displaystyle v_{0},v_{1},\ldots ,v_{k}\in \mathbb {Z} ^{d}}$${\displaystyle v_{i}-v_{i-1}}$${\displaystyle \mathbb {R} ^{d}}$${\displaystyle \mathbb {Z} ^{d}}$

⁠ ⁠${\displaystyle \mathbb {Z} ^{2}}$における長さ 5、ステップ数 の格子パスの例 は です。 ${\displaystyle S=\lbrace (2,0),(1,1),(0,-1)\rbrace }$${\displaystyle L=\lbrace (-1,-2),(0,-1),(2,-1),(2,-2),(2,-3),(4,-3)\ブラケット }$

北東(NE) 格子パスは、のステップを持つ の格子パスです。ステップは北ステップと呼ばれ、s で表されます。ステップは東ステップと呼ばれ、s で表されます。 ${\displaystyle \mathbb {Z} ^{2}}$${\displaystyle S=\lbrace (0,1),(1,0)\rbrace }$${\displaystyle (0,1)}$${\displaystyle N}$${\displaystyle (1,0)}$${\displaystyle E}$

NE 格子パスは、通常、原点から始まります。この規則により、NE 格子パスに関するすべての情報を単一の順列ワードにエンコードできます。ワードの長さは、格子パスのステップ数 を​​示します。sとsの順序は、 のシーケンスを伝えます。さらに、ワード内の の数と の数によって、の終点が決まります。 ${\displaystyle L}$${\displaystyle k}$${\displaystyle N}$${\displaystyle E}$${\displaystyle L}$${\displaystyle N}$${\displaystyle E}$${\displaystyle L}$

NE 格子パスの順列ワードに- ステップと- ステップが含まれ、パスが原点から始まる場合、パスは必然的に で終わります。これは、パスがから正確に北に 歩、東に 歩「歩く」ためです。 ${\displaystyle n}$ ${\displaystyle N}$${\displaystyle e}$ ${\displaystyle E}$${\displaystyle (e,n)}$${\displaystyle n}$${\displaystyle e}$${\displaystyle (0,0)}$

格子パスは、他の組み合わせオブジェクトを数えるためによく使用されます。同様に、特定の種類の格子パスの数を数える組み合わせオブジェクトも多数あります。これは、格子パスが問題のオブジェクトと一対一である場合に発生します。たとえば、

• ディクパスはカタラン数で数えられる。ディクパスとは、から への格子パスのうち、 のステップが- 軸の下を通過することのないものである。^[2]同様に、ディクパスとは、から への北東方向の格子パスのうち、対角線 の真下に位置する（ただし接することもある）ものである。^{[2] [3]}${\displaystyle n^{\text{th}}}$ ${\displaystyle C_{n}}$${\displaystyle \mathbb {Z} ^{2}}$${\displaystyle (0,0)}$${\displaystyle (2n,0)}$${\displaystyle S=\lbrace (1,1),(1,-1)\rbrace }$${\displaystyle x}$${\displaystyle (0,0)}$${\displaystyle (n,n)}$${\displaystyle y=x}$
• シュレーダー数は、からへの格子経路のうち、およびにステップがあり、対角線を超えることのない経路の数を数えます。^[2]${\displaystyle (0,0)}$${\displaystyle (n,n)}$${\displaystyle (1,0),(0,1)}$${\displaystyle (1,1)}$${\displaystyle y=x}$
• からまでの NE 格子パスの数は、オブジェクトセットからのオブジェクトの組み合わせの数をカウントします。${\displaystyle (0,0)}$${\displaystyle (a,b)}$${\displaystyle a}$${\displaystyle a+b}$

NE 格子パスは、二項係数によってカウントされ、パスカルの三角形に配置される組み合わせの数と密接な関係があります。次の図は、これらの関係のいくつかを示しています。

からまでの格子パスの数は、二項係数に等しくなります。図は についてこれを示しています。図を原点を中心に時計回りに 135° 回転し、すべての を含むように拡張すると、パスカルの三角形が得られます。この結果は、パスカルの三角形の行の要素が二項係数 であるためです。 ${\displaystyle (0,0)}$${\displaystyle (n,k)}$ ${\displaystyle {\binom {n+k}{n}}}$${\displaystyle 0\leq k\leq n=4}$${\displaystyle n,k\in \mathbb {N} \cup \lbrace 0\rbrace }$${\displaystyle k^{\text{th}}}$${\displaystyle n^{\text{th}}}$${\displaystyle {\binom {n}{k}}}$

NE 格子パスのグラフィカルな表現は、組み合わせを含む多くの全単射証明に役立ちます。ここにいくつかの例を示します。

• ${\displaystyle \sum _{k=0}^{n}{\binom {n}{k}}^{2}={\binom {2n}{n}}.}$

証明: 右辺は から までの NE 格子パスの数に等しくなります。これらの各 NE 格子パスは、の座標を持つ長方形配列内の格子点の 1 つと交差します。これは、 について下の図に示されています。からまでのすべての NE 格子パスは、色付きのノードの 1 つと交差します。 ${\displaystyle (0,0)}$${\displaystyle (n,n)}$${\displaystyle (x,n-x)}$${\displaystyle x\in \lbrace 0,1,\ldots ,n\rbrace }$${\displaystyle n=4}$${\displaystyle (0,0)}$${\displaystyle (4,4)}$

左側の二項係数の二乗 は、から までの NE 格子パスのセットの 2 つのコピーを端点から始点に接続したものを表します。2 番目のコピーを時計回りに 90° 回転しても、オブジェクトの組み合わせは変わりません。したがって、格子パスの合計数は変わりません。 ${\displaystyle {\binom {n}{k}}^{2}}$${\displaystyle (0,0)}$${\displaystyle (k,n-k)}$${\displaystyle {\binom {n}{k}}={\binom {n}{n-k}}}$

下の図に示すように、同じ長方形の配列に NE 格子パスの二乗を重ねます。からまでのすべての NE 格子パスが考慮されていることがわかります。特に、赤い格子点 (たとえば) を通過する格子パスは、格子パスの二乗セット (これも赤で表示) によってカウントされます。${\displaystyle (0,0)}$${\displaystyle (n,n)}$${\displaystyle \Box }$

• タデパリ・ベンカタ・ナラヤナ

^[1]

^[2]