流水账流水账这篇什么都不是
目录
- 方法
- 10.2 Lattice paths without restrictions 无限制格子路径
- 10.3 Linear boundaries of slope 1
- 10.4 Simple paths with linear boundaries of rational slope,部分一
- 10.5 Simple paths with linear boundaries with rational slope,部分二
- 10.6 Simple paths with a piecewise linear boundary
- 10.7 Simple paths with general boundaries
- 10.8 Elementary results on Motzkin and Schröder paths
- 10.9 A continued fraction for the weighted counting of Motzkin paths
- 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
- 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
吐个槽，以为逛组合学就不要看到大段复杂的公式了，结果。。。后面的哪些公式(omegavarpi)都出来了，还一堆上下标。。。(sum)下面求和范围都密密麻麻写两行。。。
方法
如果某人尝试去列出格子路径计数问题中的一些重要方法，那么会包括下面这些：
- 生成函数；拉格朗日反演公式 ；residue calcus
- 一一映射
- reflection principle
- cycle lemma
- 转移函数方法
- 核方法
- the path switching involution for non-intersecting lattice paths
- manipulation of two-rowed arrays for turn enumeration
- 正交多项式；连分数
10.2 Lattice paths without restrictions 无限制格子路径
2维的例子，从(a,b)到(c,d)，允许(0,1)和(1,0)
[|L((a, b)
ightarrow(c, d))|=left(egin{array}{c}
c+d-a-b \
c-a
end{array}
ight)
]
n维的例子，从(mathbf{a})到(mathbf{e}),每次允许一个维度+1
[|L(mathbf{a}
ightarrow mathbf{e})|=left(egin{array}{c}
sum_{i=1}^{d}left(e_{i}-a_{i}
ight) \
e_{1}-a_{1}, e_{2}-a_{2}, ldots, e_{d}-a_{d}
end{array}
ight):=frac{left(sum_{i=1}^{d}left(e_{i}-a_{i}
ight)
ight) !}{left(e_{1}-a_{1}
ight) !left(e_{2}-a_{2}
ight) ! cdotsleft(e_{d}-a_{d}
ight) !}
]
2维的例子，从(a,b)到(c,d)，允许((0,pm1))和((pm1,0)),走n个steps
[left|L_{n}((a, b)
ightarrow(c, d) ;{(pm 1,0),(0,pm 1)})
ight|=left(egin{array}{c}
n \
frac{n+c+d-a-b}{2}
end{array}
ight)left(egin{array}{c}
n \
frac{n+c-d-a+b}{2}
end{array}
ight)
]
2维的例子，从(a,b)到(c,d)，允许(0,1)和(1,0)和(1,1)
[|L((a, b)
ightarrow(c, d) ;{(1,0),(0,1),(1,1)}|=sum_{k=0}^{c-a}left(egin{array}{c}
c+d-a-b-k \
k, c-a-k, d-b-k
end{array}
ight)
]
一个带权重计数，联系了格子路径计数和整数分拆
记号(a(P))表示path (P)的水平step和x轴夹的面积的代数和
一个q-模拟
[G Fleft(L((a, b)
ightarrow(c, d)) ; q^{a(.)}
ight)=q^{b(c-a)}left[egin{array}{c}
c+d-a-b \
c-a
end{array}
ight]_{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[egin{array}{c}
4 \
2
end{array}
ight]_{q}=frac{left(1-q^{4}
ight)left(1-q^{3}
ight)}{(1-q)left(1-q^{2}
ight)}=left(1+q^{2}
ight)left(1+q+q^{2}
ight)=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)
ightarrow(c, d) mid x geq y)|=left(egin{array}{c}
c+d-a-b \
c-a
end{array}
ight)-left(egin{array}{c}
c+d-a-b \
c-b+1
end{array}
ight)
]
其中(a geq b，cgeq d)
特例有：
ballot problem
[|L((0,0)
ightarrow(c, d) mid x geq y)|=frac{c+1-d}{c+d+1}left(egin{array}{c}
c+d+1 \
d
end{array}
ight) where cgeq d
]
卡特兰数
[|L((0,0)
ightarrow(n, n) mid x geq y)|=frac{1}{n+1}left(egin{array}{c}
2 n \
n
end{array}
ight)
]
Theorem 10.3.3 在两条斜率1的对角线之间
[egin{array}{l}
|L((a, b)
ightarrow(c, d) mid x+t geq y geq x+s)| \
quad=sum_{k in mathbb{Z}}left(left(egin{array}{c}
c+d-a-b \
c-a-k(t-s+2)
end{array}
ight)-left(egin{array}{c}
c+d-a-b \
c-b-k(t-s+2)+t+1
end{array}
ight)
ight)
end{array}
]
其中(a+tgeq bgeq a+s) and (c+tgeq dgeq c+s)
如果利用一些余数微积分的知识，我们可以改写成有sine和cosine的formula，这样容易分析渐进性质：
[egin{array}{c}
|L((a, b)
ightarrow(c, d) mid x+t geq y geq x+s)| \
=sumlimits_{k=1}^{lfloor(t-s+1) / 2
floor}frac{4}{t-s+2}left(2 cos frac{pi k}{t-s+2}
ight)^{c+d-a-b}
cdot sin left(frac{pi k(a-b+t+1)}{t-s+2}
ight) cdot sin left(frac{pi k(c-d+t+1)}{t-s+2}
ight)
end{array}
]
10.4 Simple paths with linear boundaries of rational slope,部分一
Theorem 10.4.1 rational Catalan number
[|L((0,0)
ightarrow(r, s) mid s x geq r y)|=frac{1}{r+s}left(egin{array}{c}
r+s \
r,s
end{array}
ight)
]
这里没错。。。我找了个pdf
这个数如今被称为有理卡特兰数，
如果让(r=n,s=n+1)，那么成为卡特兰数(frac{1}{n+1}left(egin{array}{c} 2n \ n end{array} ight))
Theorem 10.4.5
[|L((0,0)
ightarrow(c, d) mid x geq mu y)|=frac{c-mu d+1}{c+d+1}left(egin{array}{c}
c+d+1 \
d
end{array}
ight)
]
其中，(mu)是一个非负整数，(cgeq old{mu} d)
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
picewise 分段的，逐段的
像下面这样
Theorem 10.6.1
10.7 Simple paths with general boundaries
Theorem 10.7.1
[left|Lleft(left(0, b_{1}
ight)
ightarrowleft(n, a_{n}
ight) mid mathbf{a} geq mathbf{y} geq mathbf{b}
ight)
ight|=operatorname{det}_{1 leq i, j leq n}left(left(egin{array}{c}
a_{i}-b_{j}+1 \
j-i+1
end{array}
ight)
ight)
]
10.8 Elementary results on Motzkin and Schröder paths
一些著名paths
常见的就这么几种
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
[egin{array}{l}
L((a, b)
ightarrow(c, d) ; M mid y geq 0) mid \
quad=sum_{k=0}^{c-a}left(egin{array}{c}
c-a \
k
end{array}
ight)left(left(egin{array}{c}
c-a-k \
(c+d-k-a-b) / 2
end{array}
ight)-left(egin{array}{c}
c-a-k \
(c+d-k-a+b+2) / 2
end{array}
ight)
ight)
end{array}
]
Schröder paths enumeration
[egin{array}{c}
|L((a, b)
ightarrow(c, d) ; S mid y geq 0)|=sum_{k=0}^{(c-a) / 2}left(egin{array}{c}
c-a-k \
k
end{array}
ight) \
cdotleft(left(egin{array}{c}
c-a-2 k \
(c+d-2 k-a-b) / 2
end{array}
ight)-left(egin{array}{c}
c-a-2 k \
(c+d-2 k-a+b+2) / 2
end{array}
ight)
ight)
end{array}
]
Corollary 10.8.2
出发点和结束点都在x轴上的Motzkin paths计数
[|L((0,0)
ightarrow(n, 0) ; M mid y geq 0)|=sum_{k=0}^{lfloor n / 2
floor}left(egin{array}{c}
n \
2 k
end{array}
ight) frac{1}{k+1}left(egin{array}{c}
2 k \
k
end{array}
ight)
]
出发点和结束点都在x轴上的Schröder paths计数
[|L((0,0)
ightarrow(n, 0) ; S mid y geq 0)|=sum_{k=0}^{n / 2}left(egin{array}{c}
n / 2+k \
2 k
end{array}
ight) frac{1}{k+1}left(egin{array}{c}
2 k \
k
end{array}
ight)
]
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)
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
一些定义
有点像以前写过的routing，non-intersecting但是可以cross
Theorem 10.13.1
其实还是这个：以前写过的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
许多组合大牛写的组合计数综述合集，几乎覆盖组合计数学的各个方面