動機
選取哪些位置放置上升步,所數的是具有給定終點高度的單詞,但這並不能保證其中間高度保持非負。前綴約束會記住符號的先後次序,因此不能僅靠要求總數相等來施加。
反射法用一個精確的雙射修復了這個不匹配。第一次跌到零以下的路徑,其初始段可以被翻轉,從而把「失敗」轉化為另一個終點的計數。把這些失敗的數目減去,便得到卡特蘭(Catalan)數。隨後,首次返回分解說明了為甚麼同一個數列還能計數有序二叉樹、括號化方式和三角剖分。重點在於找出可逆的構造,而不是羅列一些小數值恰好吻合卻互不相關的對象。
形式母函數只作為係數恆等式使用,不假設解析收斂性。
定義
定義 2.8.1
(前綴高度與投票條件)
上升步 使高度增加一,下降步 使高度減少一。含有 個上升步和 個下降步的單詞從零出發,終點高度為 。弱投票單詞是指每個前綴(包括空前綴)之後的高度都非負的單詞。嚴格投票單詞是非空單詞,並且每個非空前綴之後的高度都嚴格為正。
半長為 的 Dyck 單詞是含有 個上升步和 個下降步的弱投票單詞。空單詞是半長為零的唯一 Dyck 單詞。以 表示這類單詞的個數。等價地,把 詮釋為左括號, 詮釋為右括號:沒有任何前綴所關閉的括號多於所打開的括號,並且最終兩者總數相等。
定義 2.8.2
(平面滿二叉樹及其大小)
平面滿二叉樹是一棵有根樹,其中每個頂點要麼是葉子,要麼恰有兩個有序的子頂點,分別稱為左子頂點和右子頂點。這裏它的大小指內部頂點的個數,而不是頂點總數。一個內部頂點的兩棵子樹是各自獨立的有序選擇,交換它們可能改變這棵樹。
對於二項式係數的計數,當 或 時約定 ,其中 為非負整數。這使得沒有下降步的邊界情況得到明確處理。下面所有路徑都是有限的步驟單詞,而不是任意的幾何曲線。
定理/命題
定理 2.8.3
(反射給出弱與嚴格投票公式)
對於整數 ,弱投票單詞的個數為
特別地,對每個 有 。對於整數 ,嚴格投票單詞的個數為
嚴格情況的陳述針對非空單詞,它並沒有給空 Dyck 單詞賦予矛盾的地位。
定理 2.8.4
(首次返回給出卡特蘭遞推式與級數)
初值為 ,且對 ,
因此,普通形式級數 是滿足 且常數項為一的唯一級數,並且
其中形式平方根的常數項為一。具有 個內部頂點的平面滿二叉樹,以及對 個固定有序因子的完全括號化方式,其個數均為 。
閉式中的因子 來自反射計數,它並不是要求把所有對象分成無名的、每組該大小的若干組。之後的每一種詮釋,都需要各自的雙射,或一個初值相同且已被證明的遞推式。
證明思路或證明
證明
(在首次到達高度 處反射)
具有給定總數的無限制單詞共有 個。設 ,並設某個單詞不滿足非負性。找出它第一個終點高度為負一的前綴,並在該前綴內把 與 全部互換。該前綴的下降步比上升步多一個,所以變換後的完整單詞含有 個上升步和 個下降步。
反過來,任何具有變換後總數的單詞,終點高度為 。因此它有第一個終點高度為一的前綴。將該前綴內的各步互換。在所選的第一個正高度之前,所有高度都非正;反射之後,這些高度都非負,直到新前綴第一次到達負一為止。這兩個操作互為逆運算,且所用的首次到達時刻恰如上述所確定。於是,不良單詞與所有含 個下降步的單詞之間存在雙射,後者的個數為 。若 ,則沒有不良單詞,所述約定使該減項為零。
相減即得弱公式;經過初等的階乘約分,便得到其比值形式。取總數相等時,得到卡特蘭閉式,其中包括空單詞。對於 的嚴格投票單詞,第一步必須是上升步。刪去它,並把其餘的高度都下移一。原來非空前綴的嚴格正性,恰好就是這個後綴的弱非負性,該後綴含有 個上升步和 個下降步。應用弱公式,並利用 化簡,即得嚴格比值。
證明透視
首次到達時刻使反射可逆
有三個選擇使這個映射成為雙射。第一,切點是第一個高度為 的前綴;翻轉任意一個違規段,並不能說明如何還原原來的單詞。第二,被翻轉的前綴恰好比 多一個 ,所以像的總數為 與 ;這是步數唯一改變之處,也是減項為 的原因。
第三,逆映射要求每個具有新總數的單詞都有第一次到達高度 的時刻。它之所以存在,是因為這樣的單詞終止於 (這裏用到 ),而高度每步只變化一。在該時刻之前高度至多為 ,翻轉後至少為 ,而翻轉後的前綴終止於 :像第一次到達 正是在同一位置。兩個首次到達時刻因此互相對應,每個變換後的單詞恰好被計數一次,不會遺漏或重複任何失敗的單詞。 的情況從不進入反射,而由約定 處理。
證明
(首次返回分解及其編碼)
對於遞推式,非空 Dyck 單詞以 開頭。設它第一次返回高度零時的步為與之匹配的下降步。它具有唯一的形式 ,其中 和 是 Dyck 單詞:將最初那對匹配括號內部的高度減去一,並把返回之後的後綴視為從零開始。若 的半長為 ,則後綴的半長為 。反過來,任何這樣的一對單詞都給出一個具有該首次返回的 Dyck 單詞。把兩個獨立計數的乘積求和,便證明了遞推式。
現在,形式係數的乘法給出 。常數項之後的每個係數,都由遞推式根據前面的係數確定,這證明了唯一性。令 。代入得 且 。具有該常數項的平方根是唯一的:在每個正次數上,新的係數出現兩次,再加上已被確定的表達式,而二在有理數域上可逆。這就證明了平方根的表達式。它的分子常數項為零,所以除以 得到的是形式冪級數。二次方程的另一個符號,其分子常數項非零,會引入負次冪,因此它不是另一個形式冪級數解。
平面滿二叉樹要麼是單個葉子(大小為零),要麼是一個內部根加上一對有序的左右子樹。把葉子編碼為空 Dyck 單詞,把內部根編碼為 ,其中 分別編碼它的兩棵子樹。首次返回能唯一地重構根處的分裂,所以這是保持大小的雙射。對於括號化,把每次乘法變成一個內部頂點,把它的左右運算對象變成有序子樹;固定的因子次序從左到右標記各葉子。這個可逆的語法樹構造證明了第二種詮釋。
例題詳解
例題 2.8.5
(兩種獨立的計算都給出十四)
對於半長為四,反射公式給出 。由 ,首次返回給出 。每一項固定了第一對匹配括號內部的半長。無限制的平衡單詞共有七十個,所以大多數具有給定總數的單詞都不滿足前綴條件。
例題 2.8.6
(弱正性與嚴格正性所計數的是不同的事件)
含有七個上升步和四個下降步時,無限制單詞共有 個。弱計數為 。嚴格計數為 。弱單詞可以在繼續之前先返回零,嚴格單詞則不可以。它們的終點高度都是三,所以僅憑終點資訊無法區分這兩個條件。
下面的互動圖把壞單詞直到首次到達高度 的前綴翻轉,並把枚舉所得的弱投票、嚴格投票與壞單詞個數同公式比較,其中包括 、 的情況。
例題 2.8.7
(四個因子上的五種有序二叉結構)
有三個內部頂點時,根的子樹大小可以是 、 或 ,分別貢獻兩種、一種和兩種選擇。因此共有五棵平面滿二叉樹。在四個有序因子上,它們對應於 、、、 和 。
左右次序是每個構造的一部分。即使在結合運算下對它們求值會得到相同的值,這些書寫出來的括號化方式仍然互不相同。枚舉所計數的是語法或樹結構,而不是不同的數值結果。
例題 2.8.8
(一條指定的多邊形邊提供另一種根分裂)
在有 個按圓周排列的頂點的凸多邊形中,指定一條邊界邊。在三角剖分中,與該邊相鄰的三角形有唯一的第三個頂點。它把多邊形分成兩個較小的多邊形區域,這兩個區域的三角剖分可以獨立選取;凸性保證它們的對角線位於各自的區域之內。
對 ,以 表示這類三角剖分的個數,並對僅由一條邊界邊構成的空區域(而非真正的雙邊多邊形)規定 。選取第三個頂點,得到的區域大小以 和 為指標,因此 。反過來,把它們的三角剖分與指定的三角形拼合,可以唯一地重構原來的三角剖分。由於初值相同,這就是卡特蘭遞推式;因此五邊形有五種三角剖分。空區域的約定,正是用來處理第三個頂點與根邊的某個端點相鄰的情況。
計數並不能解決識別所需的記憶
Dyck 單詞有精確的公式和簡短的代數母函數恆等式,但它們所構成的整個語言並非正則語言。前綴 ( 為非負整數)兩兩可被後綴 區分:只有指數恰好匹配,才能得到平衡且非負的單詞。因此,自動機筆記中已證明的有限指標判據排除了有限狀態識別器。計數公式與有界記憶的識別算法是不同的數學對象。
概念視角組合
首次返回保留了由兩個較小對象構成的有序對
這個分解包含內部部分和隨後的部分,而不是由若干分量構成的無序集合。這就是普通級數相乘時無需階乘除數、而且左右樹結構至關重要的原因。每個對象都帶有可唯一還原的分裂,因此遞推式的相等記錄的是一個雙射,而不是數值上的巧合。
常見錯誤
反例模式
總數平衡且第一步向上仍然不夠
半長為二時,有六個單詞含兩個上升步和兩個下降步,但只有 和 是 Dyck 單詞。單詞 以上升步開始並終止於零,但它的第三個前綴的高度為負一。非負性必須在每個前綴上成立,而不只是在第一個和最後一個前綴上成立。反射所計數的,正是這些中間出現的失敗。
常見錯誤
(把平面樹個數除以二來忘記左右)
不要把平面樹的個數除以二來抹去左右次序:不同的形狀具有不同的對稱性。交換根的兩棵子樹時, 的形狀不變, 的形狀卻改變了,所以平面樹個數並不是無序形狀個數的固定倍數。
常見錯誤
(在總數相等時使用嚴格公式)
不要在上升步與下降步總數相等且為正時使用嚴格公式,因為在最後的零高度處,嚴格正性必然失效。當 時沒有嚴格投票單詞,而公式要求 。
常見錯誤
(以解析方式選取平方根符號)
形式平方根的選取由常數項和允許的冪次決定,而不是假設一個尚未引入的解析極限。若取 ,分子常數項為 ,除以 便會產生負次冪 。
總結
首次到達的反射把含禁止前綴的單詞轉化為無限制的終點計數,從而證明了弱與嚴格投票公式及卡特蘭閉式。首次返回給出有序分解、二次形式級數,以及樹與括號化的可逆編碼。多邊形三角剖分遵循同樣的有根分裂,並配有精確的空區域約定。
練習
快速檢查
(求含五個上升步和三個下降步的弱投票單詞與嚴格投票單詞的個數。)
給出兩個整數計數,並指出共同的無限制總數。
解答 · 答案
無限制的總數為 。弱正性給出 ,嚴格正性給出 。兩種計算所數的都是固定步數總數的單詞。差值記錄的是開始之後曾觸及零的單詞,弱正性容許這類單詞,嚴格正性則排除它們。
快速檢查
(在半長為五的 Dyck 單詞中,求首次返回發生在四步之後的單詞個數,以及僅在末尾才首次返回的單詞個數。)
把返回時刻轉換為 中內部部分的半長。
解答 · 答案
在第 步首次返回,意味著內部 Dyck 單詞的半長為 。四步給出 ,所以個數為 。僅在末尾(第十步)首次返回,給出 ,所以個數為 。這些是總數 中互不相交的子族;其他返回時刻提供遞推式中其餘的項。
快速檢查
(具有三個內部頂點的無序有根滿二叉樹形狀有多少種?解釋為甚麼把平面樹的個數除以二是錯誤的。)
對根的分裂進行分類,並考慮交換相同子樹的情況。
解答
根要麼在兩棵子樹中各有一個內部頂點,得到一種平衡形狀;要麼有一個葉子和一棵含兩個內部頂點的子樹。後一棵子樹只有一種無序形狀,所以它再給出一種形狀。無序形狀共有兩種。
平衡形狀只給出一種平面形狀,因為交換其相同的子形狀不會改變任何東西。不平衡形狀給出四種平面形狀:選擇根的哪一側是葉子,以及其內部子頂點的哪一側繼續延伸。因此五種平面形狀在兩種無序形狀上的重數是一和四,而不是公共因子二。統一除以二無論在算術上還是作為計數論證都是行不通的。