說明當 n 個矩陣相乘時，可能的情況P(n)數等于C(n-1)。（C是加泰羅尼亞數）此時，C(n)據說是用n個節點可以創建的不同二叉樹的數量。我沒有認知理解。如果您能解釋一下，我將不勝感激。
請解釋為什么n個矩陣乘法中n-1個節點可以組成的二叉樹的數量與n個矩陣乘法中的案例數相同。
uj5u.com熱心網友回復：
理解這需要兩個步驟：
步驟 1：N 個矩陣相乘的不同方法的數量是具有 N 個葉子的完整二叉樹的數量。
請注意，“完整”二叉樹是其中每個節點都有 0 或 2 個子節點的二叉樹。
矩陣乘法不交換，因此矩陣必須按其原始順序相乘。每個案例可以形成如下：
- 按順序寫下所有矩陣
- 重復相乘兩個相鄰的矩陣或中間產品，直到只剩下一個。
并非所有這樣做的方法實際上都是不同的。例如：
ABCDE -> (AB)CDE -> (AB)C(DE) -> (ABC)(DE) -> (ABCDE)
包括與以下完全相同的乘法：
ABCDE -> ABC(DE) -> (AB)C(DE) -> (ABC)(DE) -> (ABCDE)
在這兩種情況下，我們都生產產品 AB 和 DE。我們先做哪個并不重要，因為我們以相同的方式組合它們。
您可以將任何不同的情況映射為二叉樹，其中每個內部節點都是一個產品，葉子是原始矩陣。上述情況的樹是：
*
/ \
* \
/ \ \
* C *
/ \ / \
A B D E
樹顯示了哪些矩陣對形成的每個乘積有貢獻，與我們實際執行它們的順序無關，因此每個不同的樹實際上都是矩陣相乘的不同方式。
Step 2：N個葉子的完全二叉樹的個數就是N-1個節點的二叉樹的個數
對于任何具有 N 個葉子的完整二??叉樹，有 N-1 個內部節點——每對相鄰葉子之間有一個。這些節點本身形成一個（不一定是完整的）二叉樹。上面樹中的 * 節點就是一個例子。
對于任何具有 N-1 個節點的二叉樹，只有一種方法可以附加 N 個葉子以形成完整的樹。原來的樹有 N 個孩子的空閑位置，所以你必須把它們都填滿。
因此，具有 N 個葉子的完整二??叉樹的數量等于具有 N-1 個節點的二叉樹的數量，因為這些事物之間存在一一對應關系。
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/344360.html
上一篇：加權回圈有向圖中的最長路徑
下一篇：PineScript不繪制框