介绍常系数齐次线性递推关系式、常系数非齐次线性递推关系式以及卡特兰数的求法。



首先来看一个一般的$k$-阶常系数齐次线性递推关系式：

> $h_n=c_1h_{n-1}+c_2h_{n-2}+\dots+c_kh_{n-k}$



显然$h_n\equiv0$是递推关系的一个平凡解，但人们更想关注递推关系的非零解。

对于齐次递推关系，可以通过特征根法求解。这一方法主要是来源于常系数线性微分方程的解法，因为二者在结构上具有相似的地方。

特征方程:
> $x^k=c_1x^{k-1}+c_2x^{k-2}+\dots+c_k$

1. 若$x_1,x_2,\dots,x_k$是$k$个互异的实根，则$h_n=a_1x_1^n+a_2x_2^n+\dots+a_kx_k^n$是递推关系的通解。

2. 若存在$x_i$是重根，重数为$m$, 则通解中含有$h_n=(a_1+a_2n+\dots+a_m n^{m-1})x_i^n$.

而对于常系数非齐次线性递推关系式：

> $h_n=c_1h_{n-1}+c_2h_{n-2}+\dots+c_kh_{n-k}+f(n)$

至今只能针对部分特殊的$f(n)$给出解的形式。

$f(n)=b$:

若1也是特征方程的$m(m\leq k)$重特征根，则特解为$h_n^*=An^m$；
若1不是特征方程的特征根，则特解为$h_n^*=A$；将特解代回到原递推关系式中，求解得$A$.

$f(n)=b^n$:

若$b$也是特征方程的$m(m\leq k)$重特征根，则特解为$h_n^*=An^mb^n$；
若$b$不是特征方程的特征根，则特解为$h_n^*=Ab^n$；将特解代回到原递推关系式中，求解得$A$.

递推关系式的解法

介绍图同态的定义，并重点介绍图同态与染色、同构的关系。




### 图，有向图与同态
图的定义不做赘述。

**定义 1.1
    称映射$f:G\rightarrow H$为图$G$到图$H$的同态，若$f$满足：对于任意边$uv\in E(G)$, $f(u)f(v)\in E(H)$.**

图$G$到$H$的同态也被称作是图$G$的$H$-染色，在之后的内容中我们会揭示同态与染色的关系。若图$G$到$H$的同态存在，记作$G\rightarrow H$. 容易验证的是同态具有传递性。记$HOM(G,H)=\{f|f:G\rightarrow H\}$, $hom(G,H)=|HOM(G,H)|$.

根据同态映射的定义，可以发现，同态能够保持邻接性，因此有向图到有向图的同态映射也是其底图的同态映射，但反过来不一定成立。
在图中，如果$f(u)f(v)\in E(H)$意味着$f(u)\neq f(v)$, 因为图的每一条边都有两个不同的端点。

### 同态保持邻接性
首先考虑路和圈的同态。
图$G$中的\textbf{道}指点序列$v_0,v_1,\dots,v_k$, 其中任意两个序号差1的点相邻。若$v_0=v_k$, 则称路是\textbf{闭的}。称$k$为道的长度。若其中任意两点都不同，则称这样的道为\textbf{路}。

**性质 2.1
    映射$f:V(P_k)\rightarrow V(G)$是$P_k$到图$G$的同态，当且仅当$f(0),f(1),\dots,f(k)$是$G$的道。**

若用$d_G(u,v)$表示$u,v$两点的距离（即连接$u,v$的最短路的长度），则有以下结论成立：

**推论 2.2
    若映射$f:G\rightarrow H$为图$G$到图$H$的同态，则$d_H(f(u),f(v))\leq d_G(u,v)$, 对于任意两个不同的点$u,v\in V(G)$都成立。**

**证：**
    若$u=v_0,v_1,\dots,v_k=v$是$G$中的一条路，则$f(u)=f(v_0),f(v_1),\dots,f(v_k)=f(v)$同样为$k$长的$H$中的道，而任意从$f(u)$到$f(v)$的道必定包含从$f(u)$到$f(v)$的路，因此$d_H(f(u),f(v))\leq k$.


图$G$中的\textbf{圈}指首尾相接的道$v_1,\dots,v_k$, $v_1$与$v_k$相邻。同理分析可得：

**性质 2.3
    映射$f:V(C_k)\rightarrow V(G)$是$C_k$到$G$的同态，当且仅当$f(0),f(1),\dots,f(k)$是$G$的一条闭合的道。**

**推论 2.4
    $C_{2k1}\rightarrow C_{2l+1}$当且仅当$l\leq k $.**

**证：**
    同态将圈映射到闭的道上。而奇圈不含有任何比其短的闭的奇长道，而奇长道又只能包含长度小于等于其长的奇长道。


### 同态与染色的对应关系
图染色是大家很熟悉的概念了，因为图染色中的四色定理应该称得上是家喻户晓，那么能不能用这最熟悉的概念来解释图同态呢？

首先复习一下染色的定义：

**定义 3.1
    $k$-coloring（$k$-染色）：通俗来说是指将$k$种颜色分配到图$G$中的每个顶点上，使得任意两个相邻的顶点染不同的颜色。实际上$k$-染色是一个映射$f:V(G)\rightarrow \{1,2,\dots,k\}$, 若$uv\in E(G)$, 则$f(u)\neq f(v)$.**

对比这两个定义，我们似乎能发现一些图染色与图同态的联系，此时若再增加一个媒介$K_n$, 便可发现：同态与染色有对应关系(homomorphisms generalize colourings).

记$V(K_n)=\{1,2,\dots,k\}$, 此时$k$-染色$f:V(G)\rightarrow V(K_n)$, 若$uv\in E(G)$, 则由染色的定义：$f(u)f(v)\in E(K_n)$.

根据以上分析可得：

**性质 3.2
    同态：$f:G\rightarrow K_k$恰为图$G$的$k$-染色。**

**推论 3.3
    记$\chi(G):=min\{k:$使得图$G$有$k$-染色$\}$, 则：若存在$G\rightarrow H$的同态，则$\chi(G)\leq \chi(H)$.**

**证：**
    令$h:G\rightarrow H$是一个同态映射。若$H$有一个$k$-染色$f:H\rightarrow K_k$, 则$h$复合$f$便是图$G$的一个$\chi(H)$-染色，从而$\chi(G)\leq\chi(H)$.

除了色数的关系外，同态的另一个必要条件便是：

**推论 3.4
    若存在$\phi:G\rightarrow H$: $odd\  girth(G)\ge odd\  girth(H)$.**

反过来，如果$\chi(G)>\chi(H)$, $odd\  girth(G)>odd\  girth(H)$, 就可说明不存在图$G$到$H$上的同态，但这一构造的前提是：存在这样的图，其有任意大的色数与奇围长。幸运的是，Erdős得到了这样的定理：

**定理 3.5
    对于任意$k,l$, 存在图$G$, 使其围长$g(G)\ge l$, $\chi(G)\ge k$.**

接下来给出概率方法的证明，在证明之前，有必要回顾一点概率知识。

1. 如果$Pr[A]<1$, 那么$Pr[\overline A]>0$. 即事件$\overline A$在概率空间上某个点上发生了。
2. 马尔可夫不等式：$Pr[X\ge \alpha]\leq \frac{E(X)}{\alpha}$.
3. 围长$g \ge l$, 控制小圈的个数
4. 染色数$\chi(G)$——独立数$\alpha(G)$:
    
    4.1 对于任意图$G$, $\chi(G)·\alpha(G)\ge n$.

**证：**
    随机图$G(n,p)$: 每条边以概率$p$出现且相互独立，固定$\lambda \in (0,\frac{1}{l})$.设置$p=n^{\lambda-1}$, 设置随机变量$X$为$G(n,p)$中长度至多为$l$的圈的数目。
    
**步骤一： $G(n,p)$中长度为$j$的圈有几个？**

首先$\tbinom{n}{j}\frac{(j-1)!}{2}=\frac{n!}{(n-j)!2j}\leq \frac{n^j}{2j}$

$E[X]=\sum_{j=3}^{l}\tbinom{n}{j}\frac{(j-1)!}{2}·p^j \leq\sum_{j=3}^{l}\frac{n^j}{2j}·p^j =\sum_{j=3}^{l}\frac{n^{\lambda j}}{2j}< n^{\lambda l}\sum_{j=3}^{l}\frac{1}{2j}<\frac{n}{4}$（当$n$充分大时）

此时由马尔可夫不等式可得：$Pr[X\ge \frac{n}{2}]\leq \frac{E(X)}{ \frac{n}{2}}<\frac{ \frac{n}{4}}{ \frac{n}{2}}=\frac{1}{2}$.

**步骤二：计算独立数$\alpha(G(n,p))$:**

设置$a=\lceil \frac{3}{p}\ln n \rceil$, 考虑事件：随机图$G(n,p)$有大小为$a$的独立集。令其对应的随机变量为$X_a$, 取值为$0, 1$.

$Pr[\alpha(G(n,p)\ge a ]=Pr[X_a=1]\leq \tbinom{n}{a}(1-p)^{\tbinom{a}{2}}\leq n^a·\exp{\{-p\frac{a(a-1)}{2}}\}$

当$n\rightarrow +\infty$时，$Pr[X_a=1] \rightarrow \frac{1}{2}$.

综上，$Pr[X_a=1$或$X\ge \frac{n}{2}]\leq Pr[X_a=1]+Pr[X\ge \frac{n}{2}]<\frac{1}{2}=1$. 等同于$Pr[X_a=0$且$X< \frac{n}{2}]>0$, 所以存在图$G$, 其长度小于$l$的圈的数目小于$\frac{n}{2}$, 且$\alpha(G)<a$. 

**步骤三：从图$G$中每个长度小于$l$的圈中任意删去一个点，得到新图$G'$**

首先$G'$至少有$\frac{n}{2}$个点，且围长至少为$l$, $\alpha(G')<a$, 此时$\chi(G')\ge \frac{|V(G)|}{\alpha(G')}\ge \frac{\frac{n}{2}}{a}=\frac{n^\lambda}{6\ln n}$

对于任意$k$, 当$n$充分大时，总存在$\frac{n^\lambda}{6\ln n}>k$.

综上，得证。


如果我们再换一个视角来看染色，图$G$的$k$-染色$f$实际上是将$V(G)$划分成$k$个独立集$f^{-1}(1),f^{-1}(2),\dots,f^{-1}(k)$, 记这样的划分为$\theta_f$. 将每个$f^{-1}(i)$中的点粘成一个点，然后删去重复的边，得到的图称为是图$G$的\textbf{商}。
若$f$是图$G$到$H$的同态，则由所有点$f(u),u\in V(G)$和所有边$f(u)f(w)，uw\in E(G)$构成的图称为是$G$在$f$下的同态像，记作$f(G)$. 显然$f(G)$是$H$的子图，若$f$是满射，则$H=f(G)$.
存在以下同态像与商的关系：
**推论 3.6
    图$G$的任意商是图$G$的一个同态像，反过来，任意图$G$的同态像同构于$G$的某个商。**

**证：**
    假设$\theta$是$V(G)$的一个划分，将$V(G)$划分成集合$S_i,i\in I$. 定义映射$f:V(G)\rightarrow I$, 则$f$是$G$到$G/\theta$的一个满射同态，所以$G/\theta$是$G$的一个同态像。
    反过来，一个满射同态$f:G\rightarrow H$对应于$G$的商$G/\theta_f$, 而$G/\theta_f$与$H$同构，也就是说对于任意点$x\in V(H)$, 都唯一对应于$\theta_f$中的点集$f^{-1}(x)$.
    
### 同态与同构的对应关系
若同态映射是一个双射，则称这一同态映射为同构映射(isomorphisms).
**性质 4.1
    任意同态映射$f:G\rightarrow H$都可以写成一个满射同态$s$与单射同态$i$的复合。$f=i\circ s$.**

**证：**
    注意到$f(G)$是图$H$的子图，则可以取$s$为使$s(G)=G/\theta_f$的满射，$i$为$f(G)$到$H$的嵌入同态(inclusion homomorphism)（这是一定存在的）。   

这样可以推出一个相当有力的同态计数工具，后面的结论的证明都离不开这一推论。

**推论 4.2
    对于任意图$G$和$H$, $hom(G,H)=\sum_{\theta\in \Theta}inj(G/\theta,H)$.**

有了同构的定义之后，学者们很自然地猜想，**在什么样的条件下，两个图是同构的？**在不断地研究探索中，边重构猜想诞生了。

**猜想 4.3
$|V(G)|=|V(H)|,|E(G)|=|E(H)|\ge 4$, 则图$G$与图$H$同构，当且仅当：存在双射$\beta:E(G)\rightarrow E(H)$, 使得对于任意边$e\in E(G)$, $G-e$同构于$H-\beta(e)$.**

这一猜想至今仍未被证实或证否。不过如果对边数进行一定的限制，我们可以验证这一猜想是正确的。

**定理 4.4
    当$G$和$H$均为$n$个顶点$m$条边的图时，且 $m>\frac{1}{2}C_n^2$, 猜想4.3成立。**

直接去找同态事实上是相当困难的，因此可以通过同态计数，再结合容斥原理去证明。用$inj(G,H)$表示所有从$V(G)$到$V(H)$的单射的数目。

**证：**
目标：$inj(G,H)\neq0$.

1. 容斥原理：对于任意有限集合族：$A_1,A_2,\dots,A_n$: $|\cup_{i=1}^{n}A_i|=\sum_{\emptyset \neq I \subset [n]}(-1)^{|I|+1}|\cap_{i\in I}A_{i}|$

计算：$inj(G,\overline{H})$.

2. 设存在性质$p_e$，若单射$f:V(G)\rightarrow V(H)$, 使得：存在边$e=uv,f(u)f(V)\in E(H),$ 存在性质$p_{e_1},\dots,p_{e_m},$ 则$G\rightarrow \overline{E}$意味着，对于任意边$e=xy\in E(G)$, 都不存在具有性质$p_e$的$f(x)f(y)\in E(H)$.

所以，$inj(G,\overline{H})=inj(\emptyset,\overline{H})-\sum_{|A|=1}inj(A,H)+\dots+(-1)^m inj(G,H)$. 令$G=H$, 得：$inj(H,\overline{H})=inj(\emptyset,\overline{H})-\sum_{|B|=1}inj(B,H)+\dots+(-1)^m inj(H,H)$.

虽然$AB$是不同的集合，但由于双射的存在可以保证计数的次数是相同的，因此两式相减可得：

$inj(G,\overline{H})-inj(H,\overline{H})=(-1)^m (inj(G,H)-inj(H,H))$.

当边数足够大时，$|E(G)|<\frac{1}{2}C_n^2$, $inj(G,\overline{H})=0, inj(H,\overline{H})=0$, 所以$inj(G,H)=inj(H,H)\neq 0$. (理解起来也比较直观，过于稠密图是不存在同态到过于稀疏图上的。）


1985年Muller对边数的下界进行了改进：

**定理 4.5
    当$G$和$H$均为$n$个顶点$m$条边的图时，且 $m>n(log_{2} n-1)$, 猜想4.3成立。**

**证：**
    1. 性质$p_e$: 如果一个映射$f:V(G)\rightarrow V(H)$, 使得恰好对于边$e=uv\in E(G),f(u)f(v)\in E(H)$.
2. 有误差$D$的同态：$D\subset E(G), \ f^D:G\rightarrow H$, 但是对于任意边$uv\in D, f(u)f(v)\notin E(H)$.

**记号：** 有误差$D$的单射同态计数：$inj_D(G,\overline{H})$； 事件$A_i$: 图$G$中的边$e_i$映射到了图$H$的某条边上，则$\overline{A_i}$: 表示图$G$中的边$e_i$映射到了图$\overline{H}$的某条边上。

若令$A\subset E(G)\backslash D$, 则由容斥原理得：

$inj_D(G,\overline{H})=inj(D,H)-\sum_{|A|=1} inj(D\cup A,H)+\sum_{|A|=2} inj(D\cup A,H)-\dots+(-1)^{m-|D|}inj(G,H)$

若$|D|=d$, 遍历所有的$d$元子集可得：$inj_d(G,\overline{H})=\sum_{|D|=d}inj_D(G,\overline{H})$

再令$B=D\cup A\subset E(G)$, 则

$inj_d(G,\overline{H})=\sum_{|B|=d}inj(B,H)-\sum_{|B|=d+1}\tbinom{d+1}{d}inj(B,H)+\dots+(-1)^{m-d}\sum_{|B|=m}inj(G,H)$.

其中，$\sum_{|B|=m}inj(G,H)=\sum_{|D|=d,|A|=m-d}inj(G,H)=inj(G,H)\tbinom{m}{d}$.

同理，对于$C\subset E(H)$, 可得：

$inj_d(H,\overline{H})=\sum_{|C|=d}inj(C,H)-\sum_{|C|=d+1}\tbinom{d+1}{d}inj(C,H)+\dots+(-1)^{m-d}\sum_{|C|=m}inj(H,H)$.

因为$E(G)$与$E(H)$存在双射$\beta$, 所以$\sum_{|C|=d}inj(C,H)=\sum_{|B|=d}inj(B,H)$. 两式相减得：

$inj_d(G,\overline{H})-inj_d(H,\overline{H})=(-1)^{m-d}\tbinom{m}{d}(inj(G,H)-inj(H,H))$
从而：
$|inj_d(G,\overline{H})-inj_d(H,\overline{H})|=\tbinom{m}{d}(inj(G,H)-inj(H,H))$

对$|D|$从$0-m$求和：$\sum_{d=0}^{m}|inj_d(G,\overline{H})-inj_d(H,\overline{H})|$=$\sum_{d=0}^{m}\tbinom{m}{d}inj(H,H)=2^m·inj(H,H)\ge2^m$,

此外：$\sum_{d=0}^{m}|inj_d(G,\overline{H})-inj_d(H,\overline{H})|$=$\sum_{d=0}^{m}(inj_d(G,\overline{H})-inj_d(H,\overline{H}))=2(n!)<2(\frac{n}{2})^n$.


### 同态等价

**定义 5.1
    同态等价：存在图$G$到图$H$的同态，同时也存在图$H$到图$G$上的同态。**

**定义 5.2
    若图$H$是图$G$的子图，且存在$G\rightarrow H$的同态$\phi$, 使得对于任意点$x\in V(H), \phi(x)=x$，则称$H$为$G$的缩回(retraction)；称这一对应的同态映射为收缩同态。**

**定义 5.3
    核core：图$G$的核指的是$G$中最小的子图$G'$使得$G\rightarrow G'$的同态存在。**

如果一个图是核，也意味着它不是任意一个图（不是其本身）的缩回。容易验证核是良定义的，任何一个图的核在同构的意义下都是唯一的。

图同态，染色与同构

首先介绍列表染色的定义：

**列表染色(List coloring):**  对于图$G$, 给其每个点一个颜色列表$L$, 则称正常染色$\phi$为列表染色$L$-染色，如果$v\in V(G),\ \phi(v)\in L(v)$.

**$k$-可选图:** 对于图$G$, 任给其每个点一个$k$列表$L_k$, 都存在$L_k$-列表染色，则称图$G$是$k$-可选图。记$\chi_l(G)=min\{k\}$为**列表染色数**。

显然，正常染色数$\chi(G)\leq\chi_l(G)$, 因为若给每个点均取一样的染色列表，此时列表染色就退化成正常染色。但$chi_l(G)-\chi(G)$可能会取到非常大的值。

**命题 1.1** 令$k$是一个正整数，$n=\tbinom{2k-1}{k}$, 考虑完全二部图$K_{n,n}$, 断言其$\chi_l(K_{n,n})>k$.

**证：** 反证，假设$\chi_l(K_{n,n})\leq k$, 将$K_{n,n}$的点集划分为$A,B$两部，则给$A$中的每个点都赋予各不相同的$k$元列表$L$, 假设$G$有一个$L$-染色$\phi$，则断言$\phi$在$A$中至少使用了$k$种颜色。否则，
当选了第$j$种颜色时，剩余的种类数为$tbinom{2k-2}{k-1}$

k=3，10个点，颜色种类一共是1，2，3，4，5：
{1，2，3}{4,5,1}{1,3,4}{1,3,5}{1,2,4}{1,2,5}{2,3,4}{2,3,5}{2,4,5}{3,4,5}
1        1      1       1      1     1       2     2      2      3
**$k$-退化：遍历图$G$的所有子图$H$, 若$k=max_{H\subset G}\{\delta(H)\}$, 则称图$G$是$k$-退化的。**

第一章 概念介绍与权转移方法

RNA（核糖核苷酸组成的长链状分子）是基因表达中不可或缺的一环。RNA的一级结构表现为核糖核苷酸的排列，其中包含4种碱基：A（腺嘌呤）G（鸟嘌呤）C（胞嘧啶）U（尿嘧啶）。RNA的二级结构则是在一级结构的基础上，通过碱基配对产生折叠，形成多种多样的二级结构，使得RNA实现多种多样的功能。本文重点关注RNA的二级结构，并以此为背景，引入几个组合计数的问题。




### 一、RNA二级结构的表示：
1. 格路径表示（lattice path）：

<img src="https://jdd.southyang.cn/static/img/163afd310eebda767e6d52d7c5050aef.image.png" alt="image" style="zoom:65%;" />


2. 山形表示：（对应格路径表示）

<img src="https://jdd.southyang.cn/static/img/84b1cbc79a50871c48a4b82e4dcc1769.image.png" alt="image" style="zoom:55%;" />

3. 简图表示（diagram）：

<img src="https://jdd.southyang.cn/static/img/6b856aee40f6cc52dfcc7d78a1fa71da.image.png" alt="image" style="zoom:65%;" />


4. 圆圈表示：在简图表示的基础上，将首尾碱基对相连，形成一个圆圈。

<img src="https://jdd.southyang.cn/static/img/339f6acf3103a1e318ff277b9ca81bf9.image.png" alt="image" style="zoom:70%;" />


5. 文法表示（grammar）：括弧表示碱基有配对。

<img src="https://jdd.southyang.cn/static/img/2d28850c0f7d13e2953003b27cd7d466.image.png" alt="image" style="zoom:70%;" />


6. 树表示：多添加一条弧（0,32）作为根点，然后以弧作为内点，以未配对碱基作为叶子点。

<img src="https://jdd.southyang.cn/static/img/b27d6d8def476b03eca71fd19a629adc.image.png" alt="image" style="zoom:60%;" />

### 二、RNA二级结构的数学定义：

（一）$n$长的RNA二级结构可表示为一个点的标号为$[n]$的简单图，并且边集满足：

1. 若$(i,j)\in E$, 则$|i-j| \ge 2$;

2. 若$(i,j)\in E$, 且$(k,l)\in E$, 其中$i<j$, $k<l$, $[i,j]$与$[k,l]$的交集非空， 则要么$[i-j] \subset [k,l]$, 要么$[k,l] \subset [i-j]$. 

（二）By Waterman: [Secondary Structure of Single-Stranded Nucleic Acids] RNA的二级结构可表示为一个含$n$“带标签”点的图，其邻接矩阵满足：

1. $a_{i,i+1}=1, 1\leq i \leq n-1.$
2. 对任意$i,\ $至多存在一个整数$k \neq i-1,i+1$, 使得$a_{ik}=1$;
3. 若$a_{ij}=a_{kl}=1,i<k<l$, 则$i<l<j$.

称边$(i,k)$, $|i-k|\neq 1$为一个基对。点 $i$ 只与 $i-1$ 和 $i+1$ 相连的称为是“未配对的”。点 $i$ 被“内含于”基对$(k,l)$, 若$k<i<l$. 特别地，若不存在基对$(p,q)$, 使得$k<p<i<q$, 则称$i$是唯一内含于基对$(k,l)$的。

（三）By Tinoco et.al: [RNA Secondary Structure: A Complete Mathematical Analysis] RNA的二级结构可以表示为一个配对矩阵$P=（p_{ij}）$, 对于给定的核苷酸序列$s=s_1s_2\dots s_n$, $p_{ij}=1$当且仅当$s_i$与$s_j$配对，否则$p_{ij}=0$. 除此之外，需要满足的性质有：1. 配对矩阵的每一行每一列都至多有一个元素为1；2. 若$s_i$与$s_j$配对，则$s_k(i<k<l)$只能与$i$、$j$之间的点配对。

### 三、n长的RNA的二级结构的种类:

**命题1.** 令$R(n)$表示长为 $n$ 的RNA的二级结构的数目，则: 

$R(n+1)=R(n)+\sum\limits_{j=1}^{n-1}R(j-1)R(n-j)=R(n)+\sum\limits_{j=0}^{n-2}R(j)R(n-j-1)$, 其中$n\ge2,\ R(0)=R(1)=R(2)$.

**证明：** 当$n=1,2$时，结果显然成立。假设对于$R(k),1\leq k\leq n$, 这一命题都成立，则对于新增的第$n+1$个碱基：

1. 它不与前$n$个碱基中的任何一个配对：此时的方案数为$R(n)$;

2. 它与前面第$j$个碱基配对：首先按照定义，第$j$个碱基不能与其余的碱基再进行配对，由于不能交叉配对，第$j+1$个碱基只能与第$j+3$个到第$n$个碱基配对。这样一来，整个RNA链被分成了两个独立的部分：$1$到$(j-1)$和$(j+1)$到$n$. 根据乘法原理，此时的方案数为：$\sum\limits_{j=1}^{n-1}R(j-1)R(n-j)·1$.  
      
再由加法原理，相加即证毕。

易得：$R(n+1)\ge R(n)$, 所以

$R(n+1)\ge R(n)+\sum\limits_{j=0}^{n-2}R(j)R(n-1-j)=R(n)+R(n-1)+\sum\limits_{j=1}^{n-2}R(j)R(n-1-j)=R(n)+R(n-1)+\sum\limits_{j=0}^{n-3}R(j+1)R(n-j-2)\ge R(n)+R(n-1)+\sum\limits_{j=0}^{n-3}R(j)R(n-j-2)=2R(n)$

$R(n)\ge 2^{n-2}$.

更进一步地，定义生成函数: 

$\phi(x)=\sum_{n=0}^{+\infty}R(n)x^{n}=1+x+\sum_{n=2}^{+\infty}R(n)x^{n}$, 

则由上面所求的递推关系：

$x^2\phi^2(x)+(x-1-x^2)\phi(x)+1=0$.

**命题 2.** $n$长的，最小弧长为$m$的RNA二级结构的种类：

$R^m(n)=\sum_{i=1}^{m+1}R^m(n-i)+\sum_{i=0}^{n-2}R^m(i)R^m(n-2-i),n> m$

其中$R^m(0)=R^m(1)=\dots=R^m(m-1)=0,R^m(m)=1$.

**证明：** 当$n=1,2,\dots,m-1$时，易得$R^m(n)=1$; 假设对于$R^m(k),1\leq k\leq n-1$, 这一命题都成立，则对于新增的第$n$个碱基：

1. 它不与前$n-1$个碱基中的任何一个配对：方案数为$R^m(n-1)$; 

2. 它与前面第$j$个碱基配对：首先按照定义，第$j$个碱基不能与其余的碱基再进行配对，由于不能交叉配对，第$j+1$个碱基只能与第$j+m+1$个到第$n-1$个碱基配对。这样一来，整个RNA链被分成了两个独立的部分：$1$到$(j-1)$和$(j+1)$到$n-1$. 

    3. $1\leq j\leq m$: 只在$[j+1,n-1]$上形成了满足条件的二级结构，则此类二级结构数为$R^m(n-j-1)$;
    
    4. $m+1 \leq j\leq n-m$: 在$[j+1,n-1]$和$[1,j-1]$上都能形成满足条件的二级结构，则此类二级结构数为$R^m(n-j-1)R^m(j-1)$;
    5. $n-m+1\leq j \leq n-1$: 只在$[1,j-1]$上形成了满足条件的二级结构，则此类二级结构数为$R^m(j-1)$;
    
根据加法原理，总方案数为：
$R^m(n)=\sum_{i=1}^{m+1}R^m(n-i)+\sum_{i=0}^{n-2}R^m(i)R^m(n-2-i),n> m$





### 四、RNA二级结构的各类子结构的数学定义：

1. Helix（螺旋）: RNA二级结构中的螺旋是相互嵌套的最大弧集，其左端和右端分别是连续的。这个弧集的大小称为螺旋的长度。例如$(5,13)(6,12)$就构成了一个螺旋。注意：螺旋可以只包含一条弧。

2. stack：包含基对$(p-k,q+k),(p-k+1,q+k-1),\dots,(p,q)$, 使得$(p-k-1,q+k+1), (p+1,q-1)$中至少有一个未配对。称$k+1$为stack的长度，$(p-k,q+k)$是最终的基对。

3. external vertex：不属于任何loop的未配对的点。相邻的external vertex的集合称为是external element. 若其包含点$1$或$n$, 则其为自由端（free end），否则称为joint. 

4. loop（在邻接矩阵的定义下）: 若$i+1,i+2,\dots,j-1$都没被配对，而$a_{ij}=1$, 则称结构$s_{i+1}s_{i+2}\dots s_{j-1}$为loop.

5. bulge（在邻接矩阵的定义下）：若$i+1,i+2,\dots,j-1$都没被配对，而$i,j$均配对，但$a_{ij}\neq 1$, 则称结构$s_{i+1}s_{i+2}\dots s_{j-1}$为bulge.

6. interior loop：由两个bulge组成的结构$s_{i+1}s_{i+2}\dots s_{j-1}$和$s_{k+1}s_{k+2}\dots s_{l-1}, i<j<k<l$, 且$a_{il}=1,a_{jk}=1$.

7. join：特殊的bulge$s_{i}s_{i+1}\dots s_{j}$, 使得若$a_{kl}=1,k<i$, 则$l\leq i$；若$a_{kl}=1,k>j$, 则$l\ge j$.

8. tail：结构$s_1s_2\dots s_j$, 其中$1,2,\dots,j$未配对，而$j+1$配对。

9. ladder：两个序列组成的结构：$s_{i+1}s_{i+2}\dots s_{i+j}$和$s_{k+1}s_{k+2}\dots s_{k+j}, i+j+1<k,a_{i+l,k+j-l+1}=1$, 对于任何一个$1\leq l\leq j$都成立，且$a_{i,k+j+1}=a_{i+j+1,k}=0$; 若$i+j+3=k+1$, 则最后一个约束可以忽略。

10. hairpin：最长的序列$s_{i+1}s_{i+2}\dots s_{j-1}$恰好只含一个loop使得$a_{i+1,j-1}=1$, 且$a_{i,j}=0$

问题引入：RNA的二级结构

### 论文概览 
本文第一部分介绍研究背景与部分前置知识，第二部分介绍本文主要用的方法：收缩方法；第三部分证明结论：任意简单5-连通的线图的流指数都小于3；第四部分和第五部分扩展Hakimi定理并用以刻画流指数小于3，且为6-边连通的图。



### 第一部分 介绍
本文研究的对象皆为有限图，且不允许有自环，但允许有重边。

给定整数$k\ge 2d\ge 0$, 图$G$的圆环$\frac{k}{d}$-流$(D,f)$满足：$f:E(G)\rightarrow \{\pm{d},\pm{(d+1)},\dots,\pm{(k-d)}\}$, 使得对于任意点$v\in V(G)$, 都有$\partial f(v)=\sum_{e\ leaving\ v}f(e)-\sum_{e\ entering\ v}f(e)=0$成立。特别地，当$d=1$时，退化成为处处非零$k$-流。

已有学者研究得出，圆环流具有单调性，即任意图若存在$t$-圆环流，则其同时存在$s$-圆环流，其中$s\ge t \ge2$. 

定义流指数$\phi(G)=inf\{r|r$是有理数，且图$G$存在$r$-圆环流$\}$. 已有的结论是：对于任意有限无桥图，这样的流指数总是存在的。

Tutte最先发现了边连通性与流存在的关系，提出了著名的5-流猜想、3-流猜想。在此流指数的定义下，Tutte的5-流猜想可以被重述为：任意无桥图$G$都满足：$\phi(G)\leq5$; Seymour证明了：任意无桥图$G$都满足：$\phi(G)\leq6$; Tutte的3-流猜想：任意4-边连通图$G$都满足：$\phi(G)\leq3$; 而Jaeger证明了：任意4-边连通图$G$都满足：$\phi(G)\leq4$; Lovász, Thomassen, Wu 和 Zhang4人证明了：对于任意6-边连通图$G$, 都有$\phi(G)\leq3$成立。

Jaeger拓展了Tutte的流猜想，提出：任意$4p$-边连通图$\phi(G)\leq \frac{1}{p}+2$. 这一猜想的弱版本：任意$6p$-边连通图$\phi(G)\leq \frac{1}{p}+2$, 由Thomassen提出，且被Lovász等人证明。然而最近对于$p\ge3$的情况，Jaeger的圆环流猜想有无穷多个反例被构造出来。而$p=1,2$时的情况与Tutte的流猜想联系更为紧密，因此也更加重要，但遗憾的是，这两种情况仍未被解决。

**Conj 1.1 对于任意6-边连通图$G$, $\phi(G)<3$.**

众所周知，完全图$\phi(K_6)=3$, 并且5-边连通的平面图族的流指数也恰好为3. 因此在这一猜想中，边连通性的条件不能再被放宽。目前已经证明：对于任意8-边连通图，其流指数小于3.

**Thm 1.2 对于任意8-边连通图，其流指数小于3.**

这篇文章运用收缩方法，研究了流指数小于3的问题，并对于特定图类给出猜想1.1的证明。这一方法也与图的哈密尔顿性密切相关，具体内容将在第二部分展开。

**Thm 1.3 令$G$是一个6-边连通图：**

（1）若$G$至多有12个奇度点，则其流指数小于3.

（2）若$G$的独立数最多为2，则其流指数小于3.

需要注意的是：独立数至多为2的图与不含三角形（triangle-free）的图一样多，原因是独立数至多为2的图实际上是triangle-free图的补图。

称简单图为**弦图**，若该图每一个长度至少为4的圈都含有**弦**，换句话说就是弦图的每一个导出圈（induced cycle）的长度至多为3. 弦图在图的算法领域是一类很重要的图，因为大量NP难的问题在弦图上都能够找到有效的算法。

**Thm 1.4 若$G$是一个简单5-连通弦图，且其不同构于$K_6$, 则其流指数小于3.**

### 第二部分 收缩方法与定向

独立数: $\alpha(G)$; 最小度: $\delta(G)$; 邻点集: $N(v)$.

给定两个非空点集$A,B \subset V(G)$, 令$[A,B]_G=\{ab \in E(G)|a\in A, b\in B\}$. 当$AB$互补时，简记为 $\partial_G A$.

给定图$G$, 映射$\beta:\ V(G)\rightarrow \mathbb{Z}_3$,  若$\sum_{x\in V(G)}\beta(x)=0\pmod{3}$, 则称$\beta$为边界函数。记边界函数的集合为$Z(G,\mathbb{Z}_3)$. 

称定向$D$为$\beta$-定向，若对于任意点$v\in V(G)$, 都有$d^+(v)-d^-(v) \equiv \beta(v)\pmod{3}$. 当$\beta\equiv 0$时，退化为图$G$的模3-定向。

**Prop 2.1 若一个图的流指数小于等于3等价于该图存在模3-定向。**

事实上，流指数严格小于3与强连通定向也存在类似的关系。

**Thm 2.2 若一个图的流指数严格小于3等价于该图存在强连通模3-定向。**

Jaeger等人于1992年提出了一个在研究处处非零3-流与模3-定向中很有力的一个工具——群连通性。称图$G$是$\mathbb{Z}_3$-连通的，若对于任意边界函数$\beta$, 都存在相应的$\beta$-定向。

**Def 2.3 称图$G$为强连通$\mathbb{Z}_3$-可收缩的，若对于任意边界函数$\beta$, 都存在强连通$\beta$-定向。**
记这类图为$S_3$.

为了记号方便，记强连通$\beta$-定向为$\beta-SCO$. 强连通$\mathbb{Z}_3$-可收缩图为$S_3$-图。

给定边子集$B\subset E(G)$, 图的**收缩**指：将$B$中的每条边的两个端点“粘”成一个点，然后再去掉由此形成的环，这样得到的新图记作$G/B$. 从定义可以验证，在图的收缩下，群连通性可以保持。

**Prop 2.4 下列几条成立：**

（1）$K_1\in S_3$;

（2）$G\in S_3$, 且$e\in E(G)$, 则$G/e \in S_3$;

（3）若子图$H$与$G/H$都是$S_3$的，则$G$也是$S_3$的。

**Def 2.5 称图$G$是弱可收缩的，若对于任意真子图$H$, 以及任意$H$上的边界$\beta$, 任意$G/H$上的定向$\beta'-SCO$可被扩展成$G$上的$\beta-SCO$定向。类似地，记这类图为$W_3$.**

**Prop 2.6 令$H$是$G$的一个真$W_3$子图，则有以下成立：**

（1）$\phi(G) <3$当且仅当$\phi(G/H)<3$;

（2）$G\in S_3$当且仅当$G/H \in S_3$.
**Prop 2.7 图$H\in W_3$, 当且仅方$H+xy \in S_3$, $x,y$是不同的点。**

**证明：** 若$H\in W_3$, 令$G=H+xy$, 则此时$G/H=K_1$, 由**Def 2.5**, $k_1$上的任意$\beta'-SCO$都可扩展为$G$上的$\beta-SCO$. 根据定义图$G\in S_3$. 

反过来，假设对于任意两个不同的点$x,y$, 都有$G/H\in S_3$, 令$G$是$H$的真子图。给定$\beta\in Z(G,\mathbb{Z}_3)$, 根据$G/H$上的$\beta'$-定向$D'$复制得到$G-E(H)$上的定向$D_1$（对于$E(G[V(H)]-E(H)$的边则随意定向）, 可断言：对于任意不同点$x,y$, 在$D_1$中存在$x$到$y$的有向路。

因为图$H$是图$G$的真子图，所以存在$G-E(H)$的路（注意：非有向！）$P$连接$V(H)$中的两个点$u,v$. 如果$P$中的每一条边都含于$D_1$中的某个有向圈内，则存在$u,v$之间的有向路，从而命题成立。否则，存在边$e_0\in P$, 使得这条边不被$D_1$中的任何一个有向圈所包含。

注意到$D'=D'(G/H)$是强连通定向，所以存在$D'$中的有向圈$C$包含$e_0$. 但$E(C)$不是$D_1$中的有向圈，所以一定存在连接$u,v$的有向路。（实际上这句话的意思是说，$e_0$在$D_1$下未被包含在有向圈中，而在$D'$下我们找到了一个有向圈$C$, 而$D'$中的所有有向边在$D_1$中都有，那么可以推断，在$D_1$中，$e_0$与有向路$E(C)-e_0$有同样的终点和起点，它们所下未被包含在有向圈中，）

证毕。