格子パス

格子の点を横切る端から端までのベクトルの列

S = {(2,0),(1,1),(0,-1)}のℤ2^の長さ5の格子パス。

組合せ論において、集合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)\rbrace }$

北東格子パス

北東（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の順序は、 の順序を表します。さらに、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)}$

から始まる4つのNE格子パスは、ちょうど1つと3つの を持ちます。終点は必ず にあります。 ${\displaystyle (0,0)}$ ${\displaystyle N}$ ${\displaystyle E}$ ${\displaystyle (3,1)}$

格子パスの数え方

格子パスは、他の組合せ論的対象を数えるためによく用いられます。同様に、特定の種類の格子パスの数を数える組合せ論的対象も数多く存在します。これは、格子パスが対象の対象と一対一である場合に発生します。例えば、

• ディク路はカタラン数で数えられる。ディク路とは、からへの格子路で、 のステップが - 軸の下を通過することはない。^[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格子パス

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

からまでの格子パスの数はに等しくなります。 ${\displaystyle (0,0)}$ ${\displaystyle (2,3)}$ ${\displaystyle {\binom {2+3}{2}}={\binom {5}{2}}=10}$

からまでの格子パスの数は、二項係数に等しい。図は についてこれを示している。図を原点を中心に時計回りに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 格子パスは、正確に 1 つの色付きノードを通過します。

左側の二項係数の2乗 は、から までの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 格子パスのセットを正方形にし、2 番目のコピーを時計回りに 90 度回転させます。

下図のように、北東方向の格子経路を正方形にして同じ長方形の配列に重ね合わせます。からまでのすべての北東方向の格子経路が考慮されていることがわかります。特に、赤い格子点（例えば）を通過する格子経路は、格子経路の正方形の集合（これも赤で示されています）にカウントされます。 ${\displaystyle (0,0)}$ ${\displaystyle (n,n)}$ ${\displaystyle \Box }$

北東方向の格子経路を2乗した重ね合わせた集合。すべての北東方向の格子経路が考慮されている。

参照

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

参考文献

1. スタンレー、リチャード(2012).列挙的組合せ論 第1巻（第2版）. ケンブリッジ大学出版局. p. 21. ISBN 978-1-107-60262-5。
2. スタンレー、リチャード(2001).列挙的組合せ論 第2巻. ケンブリッジ大学出版局. pp. 173, 239. ISBN 978-0-521-78987-5。
3. "Wolfram MathWorld" . 2014年3月6日閲覧。

一般的な参考文献

• ナラヤナ、タデパリ・ヴェンカタ（1979年12月15日）『Lattice Path Combinatorics with Statistical Applications』（第1版）トロント：トロント大学出版局。ISBN 978-1487587284。
• 宋春偉(2024). 格子パス組合せ論と特殊計数列：列挙的観点から (第1版). ボカラトン: CRC Press. doi :10.1201/9781003509912. ISBN 978-1032671758。

「https://en.wikipedia.org/w/index.php?title=Lattice_path&oldid=1293168517」から取得