流水账流水账这篇什么都不是
目录
吐个槽,以为逛组合学就不要看到大段复杂的公式了,结果。。。后面的哪些公式\(\omega\varpi\)都出来了,还一堆上下标。。。\(\sum\)下面求和范围都密密麻麻写两行。。。
如果某人尝试去列出格子路径计数问题中的一些重要方法,那么会包括下面这些:
\[|L((a, b) \rightarrow(c, d))|=\left(\begin{array}{c}
c+d-a-b \\
c-a
\end{array}\right)
\]
\[|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) !}
\]
\[\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)
\]
\[|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}
\]
\[|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)
\]
\[\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}
\]
\[|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)\)
\[|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\)
picewise 分段的,逐段的
像下面这样
\[\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)
\]
常见的就这么几种
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
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}
\]
出发点和结束点都在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)
\]
给每个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\)
有点像以前写过的routing,non-intersecting但是可以cross
其实还是这个:以前写过的routing
剩下的看不懂看不懂看不懂
说这个求精确解是复杂的,求渐进的情况是很多的。给你列出了参考文献
其中推荐的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
许多组合大牛写的组合计数综述合集,几乎覆盖组合计数学的各个方面
手机扫一扫
移动阅读更方便
你可能感兴趣的文章