arrays - 数组的不同排列的总数，其中两个不相交的子数组中元素的相对顺序保持不变

Question

给出一个整数数组。

例如 a = {1,2,20,19} 让两个不相交的子数组为 {1,2} 和 {20,19}。有 5 种这样的排列，其中“1”总是在“2”之前，“20”总是在“19”之前，例如：

1. {1、2、20、19}
2. {1、20、2、19}
3. {1、20、19、2}
4. {20、1、19、2}
5. {20、19、1、2}

我的问题是：

给定一个数组，大小为 n+m 的 a[1...n+m]。求两个子数组 a[1..n] 和 a[n+1..n+m] 中元素的相对顺序保持不变的排列数。

Answer 1

1. 在您的示例中，它将是 6 个排列。您错过了 {20,1,2,19}。

2. 这是一个纯数学（组合）问题。这个问题等价于 -
   找出方程所有可能解的数量：

   x0+x1+....+xn = m

答案由公式定义——(n+m)!/(m!n!)

例如，在您的情况下，n=m=2答案是4!/2!2! = 6