C/C++教程

【读书笔记】格子路径计数LatticePathEnumeration 学一半的笔记

本文主要是介绍【读书笔记】格子路径计数LatticePathEnumeration 学一半的笔记,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

流水账流水账这篇什么都不是

目录
  • 方法
  • 10.2 Lattice paths without restrictions 无限制格子路径
    • 2维的例子,从(a,b)到(c,d),允许(0,1)和(1,0)
    • n维的例子,从$\mathbf{a}$到$\mathbf{e}$,每次允许一个维度+1
    • 2维的例子,从(a,b)到(c,d),允许$(0,\pm1)$和$(\pm1,0)$,走n个steps
    • 2维的例子,从(a,b)到(c,d),允许(0,1)和(1,0)和(1,1)
    • 一个带权重计数,联系了格子路径计数和整数分拆
  • 10.3 Linear boundaries of slope 1
    • Theorem 10.3.1 在y=x对角线下
    • Theorem 10.3.3 在两条斜率1的对角线之间
  • 10.4 Simple paths with linear boundaries of rational slope,部分一
    • Theorem 10.4.1 rational Catalan number
    • Theorem 10.4.5
    • Lemma 10.4.6 Cycle Lemma
    • Theorem 10.4.7
  • 10.5 Simple paths with linear boundaries with rational slope,部分二
  • 10.6 Simple paths with a piecewise linear boundary
    • Theorem 10.6.1
  • 10.7 Simple paths with general boundaries
    • Theorem 10.7.1
  • 10.8 Elementary results on Motzkin and Schröder paths
    • 一些著名paths
    • Theorem 10.8.1
    • Corollary 10.8.2
  • 10.9 A continued fraction for the weighted counting of Motzkin paths
    • Theorem 10.9.1 Motzkin path带权重
    • Theorem 10.9.2 Motzkin和Schröder number的GF
    • Theorem 10.9.3 Dyck path带权重
  • 10.10 Lattice paths and orthogonal polynomials
  • 10.11 Motzkin paths in a strip
  • 10.12 Further results for lattice paths in the plane
  • 10.13 Non-intersecting lattice paths
    • 一些定义
    • Theorem 10.13.1
  • 10.14 Lattice paths and their turns
  • 10.15 Multidimensional lattice paths
  • 10.16 Multidimensional lattice paths bounded by a hyperplane
  • 10.17 Multidimensional paths with a general boundary
  • 10.18 The reflection principle in full generality
  • 10.19 q-Counting of lattice paths and Rogers–Ramanujan identities
  • 10.20 Self-avoiding walks

吐个槽,以为逛组合学就不要看到大段复杂的公式了,结果。。。后面的哪些公式\(\omega\varpi\)都出来了,还一堆上下标。。。\(\sum\)下面求和范围都密密麻麻写两行。。。

方法

如果某人尝试去列出格子路径计数问题中的一些重要方法,那么会包括下面这些:

  1. 生成函数;拉格朗日反演公式 ;residue calcus
  2. 一一映射
  3. reflection principle
  4. cycle lemma
  5. 转移函数方法
  6. 核方法
  7. the path switching involution for non-intersecting lattice paths
  8. manipulation of two-rowed arrays for turn enumeration
  9. 正交多项式;连分数
10.2 Lattice paths without restrictions 无限制格子路径

2维的例子,从(a,b)到(c,d),允许(0,1)和(1,0)

\[|L((a, b) \rightarrow(c, d))|=\left(\begin{array}{c} c+d-a-b \\ c-a \end{array}\right) \]

n维的例子,从\(\mathbf{a}\)到\(\mathbf{e}\),每次允许一个维度+1

\[|L(\mathbf{a} \rightarrow \mathbf{e})|=\left(\begin{array}{c} \sum_{i=1}^{d}\left(e_{i}-a_{i}\right) \\ e_{1}-a_{1}, e_{2}-a_{2}, \ldots, e_{d}-a_{d} \end{array}\right):=\frac{\left(\sum_{i=1}^{d}\left(e_{i}-a_{i}\right)\right) !}{\left(e_{1}-a_{1}\right) !\left(e_{2}-a_{2}\right) ! \cdots\left(e_{d}-a_{d}\right) !} \]

2维的例子,从(a,b)到(c,d),允许\((0,\pm1)\)和\((\pm1,0)\),走n个steps

\[\left|L_{n}((a, b) \rightarrow(c, d) ;\{(\pm 1,0),(0,\pm 1)\})\right|=\left(\begin{array}{c} n \\ \frac{n+c+d-a-b}{2} \end{array}\right)\left(\begin{array}{c} n \\ \frac{n+c-d-a+b}{2} \end{array}\right) \]

2维的例子,从(a,b)到(c,d),允许(0,1)和(1,0)和(1,1)

\[|L((a, b) \rightarrow(c, d) ;{(1,0),(0,1),(1,1)}|=\sum_{k=0}^{c-a}\left(\begin{array}{c} c+d-a-b-k \\ k, c-a-k, d-b-k \end{array}\right) \]

一个带权重计数,联系了格子路径计数和整数分拆

记号\(a(P)\)表示path \(P\)的水平step和x轴夹的面积的代数和

一个q-模拟

\[G F\left(L((a, b) \rightarrow(c, d)) ; q^{a(.)}\right)=q^{b(c-a)}\left[\begin{array}{c} c+d-a-b \\ c-a \end{array}\right]_{q} \]

举例:从(0,0)到(2,2)有6种

是UURR,URUR,RURU,RRUU,URRU,RUUR

\[q^4+q^3+q^1+q^0+q^2+q^2=\left[\begin{array}{c} 4 \\ 2 \end{array}\right]_{q}=\frac{\left(1-q^{4}\right)\left(1-q^{3}\right)}{(1-q)\left(1-q^{2}\right)}=\left(1+q^{2}\right)\left(1+q+q^{2}\right)=1+q+2 q^{2}+q^{3}+q^{4} \]

10.3 Linear boundaries of slope 1

Theorem 10.3.1 在y=x对角线下

\[|L((a, b) \rightarrow(c, d) \mid x \geq y)|=\left(\begin{array}{c} c+d-a-b \\ c-a \end{array}\right)-\left(\begin{array}{c} c+d-a-b \\ c-b+1 \end{array}\right) \]

其中\(a \geq b,c\geq d\)

特例有:

ballot problem

\[|L((0,0) \rightarrow(c, d) \mid x \geq y)|=\frac{c+1-d}{c+d+1}\left(\begin{array}{c} c+d+1 \\ d \end{array}\right) \ where \ c\geq d \]

卡特兰数

\[|L((0,0) \rightarrow(n, n) \mid x \geq y)|=\frac{1}{n+1}\left(\begin{array}{c} 2 n \\ n \end{array}\right) \]

Theorem 10.3.3 在两条斜率1的对角线之间

\[\begin{array}{l} |L((a, b) \rightarrow(c, d) \mid x+t \geq y \geq x+s)| \\ \quad=\sum_{k \in \mathbb{Z}}\left(\left(\begin{array}{c} c+d-a-b \\ c-a-k(t-s+2) \end{array}\right)-\left(\begin{array}{c} c+d-a-b \\ c-b-k(t-s+2)+t+1 \end{array}\right)\right) \end{array} \]

其中\(a+t\geq b\geq a+s\) and \(c+t\geq d\geq c+s\)

如果利用一些余数微积分的知识,我们可以改写成有sine和cosine的formula,这样容易分析渐进性质:

\[\begin{array}{c} |L((a, b) \rightarrow(c, d) \mid x+t \geq y \geq x+s)| \\ =\sum\limits_{k=1}^{\lfloor(t-s+1) / 2\rfloor}\frac{4}{t-s+2}\left(2 \cos \frac{\pi k}{t-s+2}\right)^{c+d-a-b} \cdot \sin \left(\frac{\pi k(a-b+t+1)}{t-s+2}\right) \cdot \sin \left(\frac{\pi k(c-d+t+1)}{t-s+2}\right) \end{array} \]

10.4 Simple paths with linear boundaries of rational slope,部分一

Theorem 10.4.1 rational Catalan number

\[|L((0,0) \rightarrow(r, s) \mid s x \geq r y)|=\frac{1}{r+s}\left(\begin{array}{c} r+s \\ r,s \end{array}\right) \]

这里没错。。。我找了个pdf

这个数如今被称为有理卡特兰数,

如果让\(r=n,s=n+1\),那么成为卡特兰数\(\frac{1}{n+1}\left(\begin{array}{c} 2n \\ n \end{array}\right)\)

Theorem 10.4.5

\[|L((0,0) \rightarrow(c, d) \mid x \geq \mu y)|=\frac{c-\mu d+1}{c+d+1}\left(\begin{array}{c} c+d+1 \\ d \end{array}\right) \]

其中,\(\mu\)是一个非负整数,\(c\geq \bold{\mu} d\)

Lemma 10.4.6 Cycle Lemma

image-20200904153032817

Theorem 10.4.7

image-20200904153334628

10.5 Simple paths with linear boundaries with rational slope,部分二 10.6 Simple paths with a piecewise linear boundary

picewise 分段的,逐段的

像下面这样

image-20200905083413387

Theorem 10.6.1

image-20200905083922192

10.7 Simple paths with general boundaries

image-20200905084436444

Theorem 10.7.1

\[\left|L\left(\left(0, b_{1}\right) \rightarrow\left(n, a_{n}\right) \mid \mathbf{a} \geq \mathbf{y} \geq \mathbf{b}\right)\right|=\operatorname{det}_{1 \leq i, j \leq n}\left(\left(\begin{array}{c} a_{i}-b_{j}+1 \\ j-i+1 \end{array}\right)\right) \]

10.8 Elementary results on Motzkin and Schröder paths

一些著名paths

image-20200905084756862

常见的就这么几种

Motzkin paths 允许(1,1),(1,-1),(1,0) 不会到x轴下方

Schröder paths 允许(1,1),(1,-1),(2,0) 不会到x轴下方

Catalan paths 允许(1,1),(1,-1) 不会到x轴下方

Dyck paths 上面的3种只要出发点和终点都在x轴上,就叫做Dyck paths

Theorem 10.8.1

Motzkin paths enumeration

\[\begin{array}{l} L((a, b) \rightarrow(c, d) ; M \mid y \geq 0) \mid \\ \quad=\sum_{k=0}^{c-a}\left(\begin{array}{c} c-a \\ k \end{array}\right)\left(\left(\begin{array}{c} c-a-k \\ (c+d-k-a-b) / 2 \end{array}\right)-\left(\begin{array}{c} c-a-k \\ (c+d-k-a+b+2) / 2 \end{array}\right)\right) \end{array} \]

Schröder paths enumeration

\[\begin{array}{c} |L((a, b) \rightarrow(c, d) ; S \mid y \geq 0)|=\sum_{k=0}^{(c-a) / 2}\left(\begin{array}{c} c-a-k \\ k \end{array}\right) \\ \cdot\left(\left(\begin{array}{c} c-a-2 k \\ (c+d-2 k-a-b) / 2 \end{array}\right)-\left(\begin{array}{c} c-a-2 k \\ (c+d-2 k-a+b+2) / 2 \end{array}\right)\right) \end{array} \]

Corollary 10.8.2

出发点和结束点都在x轴上的Motzkin paths计数

\[|L((0,0) \rightarrow(n, 0) ; M \mid y \geq 0)|=\sum_{k=0}^{\lfloor n / 2\rfloor}\left(\begin{array}{c} n \\ 2 k \end{array}\right) \frac{1}{k+1}\left(\begin{array}{c} 2 k \\ k \end{array}\right) \]

出发点和结束点都在x轴上的Schröder paths计数

\[|L((0,0) \rightarrow(n, 0) ; S \mid y \geq 0)|=\sum_{k=0}^{n / 2}\left(\begin{array}{c} n / 2+k \\ 2 k \end{array}\right) \frac{1}{k+1}\left(\begin{array}{c} 2 k \\ k \end{array}\right) \]

10.9 A continued fraction for the weighted counting of Motzkin paths

给每个Motzkin path定义一个weight,定义为:

是所有step权重的乘积,

up-step的权重是\(1\),level step at height \(h\)的权重是\(b_h\),down step from height \(h\) to height \(h-1\)的权重是\(\lambda_h\)

image-20200905123656900

Theorem 10.9.1 Motzkin path带权重

image-20200905123840899

Theorem 10.9.2 Motzkin和Schröder number的GF

image-20200905124031540

Theorem 10.9.3 Dyck path带权重

image-20200905124348653

10.10 Lattice paths and orthogonal polynomials 10.11 Motzkin paths in a strip 10.12 Further results for lattice paths in the plane 10.13 Non-intersecting lattice paths

一些定义

image-20200905201935999

有点像以前写过的routing,non-intersecting但是可以cross

Theorem 10.13.1

image-20200905202217905

其实还是这个:以前写过的routing

剩下的看不懂看不懂看不懂

10.14 Lattice paths and their turns 10.15 Multidimensional lattice paths 10.16 Multidimensional lattice paths bounded by a hyperplane 10.17 Multidimensional paths with a general boundary 10.18 The reflection principle in full generality 10.19 q-Counting of lattice paths and Rogers–Ramanujan identities 10.20 Self-avoiding walks

说这个求精确解是复杂的,求渐进的情况是很多的。给你列出了参考文献

其中推荐的standard book(标准教科书)N.MadrasandG.Slade. The self-avoiding walk. Probability and its Applications, Birkh¨auser Boston, Inc., Boston, MA, 1993.



资料来自网络

书用的是Handbook of Enumerative Combinatorics by Miklos Bona

许多组合大牛写的组合计数综述合集,几乎覆盖组合计数学的各个方面

这篇关于【读书笔记】格子路径计数LatticePathEnumeration 学一半的笔记的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!