arrays - 互いに素な 2 つのサブ配列内の要素の相対的な順序が一定のままである、配列の異なる順列の総数

Question

整数の配列を与えます。

たとえば、a = {1,2,20,19} 2 つの互いに素な部分配列を {1,2} と {20,19} とします。'1' が常に '2' の前に来て、'20' が常に '19' の前に来る 5 つの順列があります。

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]。2 つの部分配列 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