两个数组保持顺序合并能产生多少种排列组合

做这道题用到的:https://leetcode.com/problems/number-of-ways-to-reorder-array-to-get-same-bst/description/

求两个数组归并后可能产生多少种组合,要求归并后两个数组元素仍有保持原数组中的顺序

其实是个很简单的问题,是我开始想复杂了

假设两个数组长度分别为m和n,则归并后长度为m+n,则问题可以转换为从m+n个索引里面挑选出m个(或n个)索引有多少种方式

其实就是 \( C_{m+n}^m = C_{m+n}^n = \frac {(m+n)!}{m!×n!} \)

组合(Combination)公式为

\[ C_n^k = \frac {n!}{k!×(n-k)!} \]

在python中可以用 math.comb(n, k) 进行计算

排列(Arrangement,从n个元素中选出k个元素并排序)公式为

\[ A_n^k = \frac {k!}{(n-k)!} \]

python中使用 math.perm(n, k) 进行计算

Leave a Comment