Simple (divide and conquer) Python solution with explanation
Consider example 2 in the problem:Observations
The first number cannot be rearranged because moving it will change the root of the tree.
Swapping any numbers be
Consider example 2 in the problem:

![image](https://assets.leetcode.com/users/images/6653ee40-694e-42dd-b7c9-698513924b94_1623134884.6523626.png)

```
Input: nums = [3,4,5,1,2]
Output: 5
Explanation: The following 5 arrays will yield the same BST: 
[3,1,2,4,5]
[3,1,4,2,5]
[3,1,4,5,2]
[3,4,1,2,5]
[3,4,1,5,2]
```

### Observations
1. The first number cannot be rearranged because moving it will change the root of the tree.
2. Swapping any numbers between left and right subarrays will yield the same tree.

### Key
Focus on observation #2:
 - The left subarray is `[1,2]` (all numbers after the root (`3`) that are smaller than the root)
 - The right subarray is `[4,5]` (all numbers after the root (`3`) that are larger than the root)

How many ways can we merge these 2 subarrays while keeping the order within each subarray?
```
L:          1          2
R:                                4          5                    => [1,2,4,5]
-----------------------------------------------
L:          1                     2
R:                     4                     5                    => [1,4,2,5]
-----------------------------------------------
L:                     1          2
R:          4                                5                    => [4,1,2,5]
-----------------------------------------------
...
```
The number of ways to "interleave" the 2 arrays is `{len(L) + len(R)}    choose    {len(L)}` (or, `{len(L) + len(R)}    choose    {len(R)}`), i.e. `(2+2) choose (2) = 6` ways. (You can think of it as number of ways to put 2 identical items in 4 slots)

We know that (from observation #2) these rearrangements of the numbers after the root (`3`) will yield the same tree.
What this means is, if we know the numbers of permutations (`numOfWays`) of the left and right subarrays, then we can calculate the overall permutations for the current tree:
```
choose(len(left_subarray)+len(right_subarray), len(left_subarray))           # (call this K)
X
numOfWays(left_subarray)
X
numOfWays(right_subarray)
```
because for each arrangement pair of the left and right subarrays, there are `K` ways to merge them.

So, we can recursively compute the permutations in each subtree/subarray, and then calculate the overall permutations based on the above formula.

### Divide and conquer

```python
import operator as op
from functools import reduce


def choose(n, r):
    """https://stackoverflow.com/a/4941932
    """
    r = min(r, n-r)
    numer = reduce(op.mul, range(n, n-r, -1), 1)
    denom = reduce(op.mul, range(1, r+1), 1)
    return numer // denom


class Solution:
    def numOfWays(self, nums: List[int]) -> int:
        def divideAndConquer(sublist):
            if len(sublist) <= 1:  # base case
                return 1
            
            root = sublist[0]
            left = [n for n in sublist if n < root]   # left subarray
            right = [n for n in sublist if n > root]  # right subarray
            
            leftWays = divideAndConquer(left)
            rightWays = divideAndConquer(right)
            
            return choose(len(left)+len(right), len(left)) * leftWays * rightWays
        
        # minus 1 because the answer needs to exclude the input
        return (divideAndConquer(nums) - 1) % 1000000007
```
['Divide and Conquer', 'Python']