弦理论

这里要说的弦，既不是音乐里的弦，也不是物理中的弦, 而是组合数学中的字符串，计算机科学也会加以研究。给定一个字符集S，如 {0, 1} ，英文字母表，标点符号等，一个字符串或 “字” （string， or word）就是有限个字符的序列。位串（bit string）就是由0和1组成的序列；英文单词就是英文字母组成的序列。一些字符串的集合F，叫做S上的一篇文章；当然要有一些语法规则，以便成文。本文要通过生成函数，来进形模式匹配（Pattern matching），给文章（句子和段落）捏出几个意思来。
一个串的长度就是它所包含的字符个数；长度为零的串即是空串ε。F中的串用逗号分隔；句号或问号、惊叹号、问号分隔句子；回车号分隔段落。在串集F上，可以定以一个权重函数或者向量，w: F → N^k，w(s) = (w1(s), w2(s), …, wk(s)) ；每个wj(s)是串s的一个统计量，比如某个字符或子串的个数，甚至是字母的编码；需得由w(s)的数值获取s的信息。在权重w下，F的生成函数定义为G(F, w; x) = Sigma{x^w(s) = x1^w1(s)* x2^w2(s) * …* xk^wk(s): s ∈ F}, x1, x2, …, xk为形式变量。一般地，我们有公式：G(AUB, w, x) = G(A, w, x) + G(B, w, x) – G(A∩B, w, x)，其中, U和∩分别是集合的并集与交集运算。
串的运算有并联（concatenation）与分拆(substrings)。给定两个串s1和s2，它门的并联就是s1s2；比如s1 = 101, s2 = 111, 则s1s2 = 101111。还有前缀与后缀，反转与左右旋环等，就是对字符串施行某种变换。一般要求权重函数在变换下保持不变，而在并联运算之下具有可加性：w(s1s2) = w(s1) + w(s2) ，w(ε) = 0; ε 为空串。这样，生成函数可以具有某种运算规律。
两个字集A和B的并联，就如同两个集合的Descartes乘积：AB = {st: s ∈ A, t ∈ B}。为了保持基数的不变性，即 |AB| = |A| |B|，要求AB是唯一生成的，即AB中的每一个串，都有唯一的一种分拆，使得其前缀在A中，后缀在B中。如果有一串s1t1 = s2t2, 其中, s1, s2 在A中，t1, t2在B中，必有s1为s2的前缀，t2 为t1的后缀（或者s2 为s1的前缀, t1 为t2的后缀）；因此，若A中任何的串都不是其它串的前缀，或者B中任何串都不是其它串的后缀，则并联运算是唯一生成的。
对于一个字集A，假设任何串都不是其它串的前缀，或者任何串都不是其它串的后缀；我们就可以定义A^2 = AA, A^3 = (A^2) A， …, A^(n +1) = (A^n) A。再定义A^0 = {ε},即空串之集，A* = U{A^n: n = 0, 1, 2, …}，A*的生成函数G(A*, w, x) = [1 – G(A, w, x)]^(-1)。这可以从生成函数的并联运算公式推出：G(AB, w, x) = G(A, w, x)G(B, w, x)，假设AB是唯一生成的。
在模式匹配中，我们经常需要考虑含有某个特定子串s0 = c1c2…ck的字集A，或者不包含s0的字集B；在S*中，A与B互为补集。设C是S*中以s0为后缀、而且前面的字符串都不包含子串s0的所有字符串的集合；也就是说s0只在最后出现一次，或者说，C = B{s0} ；此外还有集合等式：{ε} ? BS = B?C。不含s0的串，后面添家一个字符后所得到的串，可能含有s0也可能不含s0；另一方面，如果 s ∈ B, 则 s 要么是空串，要么可以去掉它的最后那个字符，所得结果依然不含s0。如果 s ∈ C, 那么去掉s的最后一个字符ck后，就毁掉了s中唯一的串s0，结果在B中。用生成函数表示出来，可得：G(C, w, x）= G(B, w, x) [x^w(s0)], 1 + G(B, w, x)G(S, w, x) = G(B, w, x) + G(C, xw x); 由此可以解出G(B, w, x)。
我们需要知道长度为n的所有字符串中，含有子串s0的字符串的个数。例如，Euclid竞赛2016年的一道题，只用两个字母A和B构造字符串，在长度为10的所有字符串中（2^10个），要求含有子串ABBA的字符串的个数。直接计数的办法是，分成7种情况，把子串放在第j到第j + 3的位置，j = 1, 2, …, 7；需要用容斥原理去计算交集中字符串的个数。如果用间接计数法，可以用上述生成函数。
也可以递归地构造集合； 比如，S* = {ε}U S S*。例1，如果S含有n个字符，如S = {1, 2, …, n}, 要构造没有重复字符的串集T，即不含xx这样的子串；设Ti是以i开头、且不含重复字符的串集，则有 Ti = {i}U {i}(TTi)，T = U{Ti}。例2，设R是不含三个连续1（即不含子串111）的所有二进制串的集合。R中的每一个字符串可以表示为sr的形式，s以0结尾：s = 0, 10, 或110，r在R中；基本的初始串有ε, 1, 及 11;因此，R= {ε, 1, 11}U {0, 10, 110}R。
一般地，设B是S*中不含子串s0 = c1c2…ck的字符串的集合。基本初始串集R0 = {ε, c1, c1c2, …, c1c2…c(k-1)} ；R0中的串至少要跟一个不是ck的字符，也就是作并联R0 S{ck}；因此，R = R0 U R0S{ck}R。
还可以直接用重复运算符*构造集合。例如，对于S = {0, 1} ，不含两个连续11的二进制串的集合可以写为 {ε, 1} {{0}{1, ε}}*, 即以空串或1开始，后跟至少一个0。不含三个连续1的串集，R = {ε, 1, 11}{{0}{11, 1, ε}}*。
可以多种方式进形拆分。例如，不含子串00100的二进制串，考虑以一个1结尾的所有串，分为A = {1, 01},与以至少两个0开始的串集C = 000*1。所有的二进制串的集合可以表示为 {A, C}*0*。要想不出现子串s = 00100, C之后得跟至少一个A（中的串），而且，如果以C结尾的话，后面不能跟两个或以上的0。因此，集合可以表示为 A*(CAA*)*{C, C0, 0*}。
二元树的构造用递归方式较为简捷。二元树具有若干个结点，每一条边都是桥（一旦去掉，就成为不连通的图了）。一棵二元树本质上就是递归的：从根部开始，分裂为左右两棵子树；所谓根部，就是仅有一个结点的树，记为R。所有树的集合T，可以用递归方程表示为：T = {ε}? TRT。定义一棵树的权重w为其结点数，根R的生成函数为 G(R, x) = x，因此，G(T, x) = 1 + xG^2(T, x)；解之可得G(T, x) = [1 – sqrt(1 – 4x)]/2x，由此可算出结点个数为n的树的数目为，C(2n, n)/(n+1)。
文章意义的理解、归纳，我已在《教电脑读书识数解风情》一文中有阐述。《信息的收集与处理》一文尚在写作中。