What is the relationship between the concatenated matrix algorithm and the number of possible binary-CodePudding

It is stated that when multiplying n matrices, the number of possible cases P(n) is equal to C(n-1). (C is a catalan number) At this time, C(n) is said to be the number of different binary trees that can be created with n nodes. I do not have a cognitive understanding. I'd appreciate it if you could explain.

Please explain why the number of binary trees that can be made with n-1 nodes in n matrix multiplication is the same as the number of cases in n matrix multiplication.

CodePudding user response：

Understanding that takes 2 steps:

Step 1: The number of distinct ways to multiply N matrices is the number of complete binary trees with N leaves.

Note that a "complete" binary tree is one in which every node has either 0 or 2 children.

Matrix multiplication does not commute, so matrices have to be multiplied together in their original order. Each case can be formed like:

write down all the matrices in order
repeatedly multiply two adjacent matrices or intermediate products until only one remains.

Not all the ways of doing this are actually distinct. For instance:

ABCDE -> (AB)CDE -> (AB)C(DE) -> (ABC)(DE) -> (ABCDE)

includes exactly the same multiplications as:

ABCDE -> ABC(DE) -> (AB)C(DE) -> (ABC)(DE) -> (ABCDE)

In both cases we make products AB and DE. It doesn't matter which one we do first, because we combine them in the same ways.

You can map out any distinct case as a binary tree where each internal node is a product and the leaves are the original matrices. The tree for the above cases is:

      *
     / \
    *   \
   / \   \
  *   C   *
 / \     / \
A   B   D   E

The tree shows which matrices contribute to each product formed, independent of the order in which we might actually perform them, so each different tree is actually a distinct way to multiply the matrices.

Step 2: The number of complete binary trees with N leaves is the number of binary trees with N-1 nodes

For any complete binary tree with N leaves, there are N-1 internal nodes -- one between each pair of adjacent leaves. These nodes themselves form a (not necessarily complete) binary tree. The * nodes in the tree above are an example.

For any binary tree with N-1 nodes, there is exactly one way to attach N leaves in order to form a complete tree. The original tree has N free positions for children, so you have to fill them all.

The number of complete binary trees with N leaves is therefore equal to the number of binary trees with N-1 nodes, because there is a one-to-one correspondence between these things.