矩阵连乘算法可行方案数与二叉树构造数量的关联问题

1. 二者的计数规则本质 #

• 矩阵连乘的可行方案数：n个矩阵相乘的可行计算顺序，等价于给M₁×M₂×…×Mₙ的表达式添加合法括号的总方案数，记为P(n)。因为矩阵乘法仅满足结合律，每次只能合并两个相邻的矩阵子块，不能交换矩阵顺序，仅能调整合并优先级。
• n个节点的不同二叉树数量：记为C(n)（即第n项卡特兰数），计数规则是根节点固定，左子树可以有0到n-1个节点，右子树对应有n-1到0个节点，总数量符合递推关系C(0)=1，C(n)=Σ_{i=0}^{n-1}C(i)*C(n-1-i)。

2. 递推关系的一致性 #

首先推导矩阵连乘方案数的递推式：

当只有1个矩阵时，不需要计算，P(1)=1
当有n个矩阵时，我们可以选择第k个矩阵作为分界，先计算前k个矩阵的乘积、再计算后n-k个矩阵的乘积，最后把两个结果相乘，因此总方案数为P(n)=Σ_{k=1}^{n-1}P(k)*P(n-k)（n≥2）
我们做变量替换令m = n-1，将递推式转化为：
P(m+1) = Σ_{i=0}^{m-1} P(i+1)*P(m-i)
令C'(m) = P(m+1)，可以看到C'(0)=P(1)=1，递推式和卡特兰数的标准递推完全一致，因此C'(m)就是第m项卡特兰数C(m)，代入得到P(n)=C(n-1)。

3. 一一对应关系的直观映射 #

我们可以直接构造两种场景的双射，证明数量完全相等：
把n个矩阵连乘的每一个合法括号方案，对应到一棵有n-1个节点的普通二叉树：

1. n个矩阵的连乘共有n-1个乘法运算符，每个运算符对应二叉树的一个节点
2. 整个表达式最后一步执行的乘法运算符作为二叉树的根节点：如果最后一步是合并前k个矩阵的乘积和后n-k个矩阵的乘积，那么根节点的左子树对应前k个矩阵的括号方案映射的子树，右子树对应后n-k个矩阵的括号方案映射的子树
   举个简单验证：n=3时有2种矩阵连乘方案，对应2个节点的二叉树总共有2种（根带左孩子、根带右孩子），二者一一对应完全匹配。

4. 为什么是n-1个节点的二叉树 #

我们也可以从满二叉树的性质辅助理解：矩阵连乘的括号方案对应的满二叉树（每个非叶子节点都有左右两个子节点）中，叶子节点对应单个矩阵（共n个），内部节点对应乘法操作。而满二叉树的固有性质是「叶子节点数 = 内部节点数 + 1」，因此内部节点数就是n-1，刚好和我们说的「n-1个节点的二叉树」的节点数对应，所以二者数量相等。

内容的提问来源于stack exchange，提问作者user9178840