弦理論

這裏要說的弦，既不是音樂裏的弦，也不是物理中的弦, 而是組合數學中的字符串，計算機科學也會加以研究。給定一個字符集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)。
文章意義的理解、歸納，我已在《教電腦讀書識數解風情》一文中有闡述。《信息的收集與處理》一文尚在寫作中。