【排列组合基本公式及算法】在数学中，排列组合是研究从一组元素中选择或安排某些元素的方法。它们广泛应用于概率论、统计学、计算机科学等领域。排列和组合虽然都涉及“选”与“排”，但两者的区别在于是否考虑顺序。本文将对排列组合的基本公式和算法进行总结，并通过表格形式清晰展示。
一、基本概念
1. 排列（Permutation）
指从n个不同元素中取出k个元素，按一定顺序排列的方式数。
关键点：顺序有关
2. 组合（Combination）
指从n个不同元素中取出k个元素，不考虑顺序的选法种数。
关键点：顺序无关
二、排列组合公式
| 类型 | 公式 | 说明 |
| 排列（P(n, k)） | $ P(n, k) = \frac{n!}{(n - k)!} $ | 从n个元素中取k个进行排列 |
| 组合（C(n, k)） | $ C(n, k) = \frac{n!}{k!(n - k)!} $ | 从n个元素中取k个不考虑顺序 |
| 全排列（P(n, n)） | $ P(n, n) = n! $ | 所有n个元素的全排列方式 |
| 重复排列（P(n, k) with repetition） | $ n^k $ | 允许重复选取元素的排列数 |
| 重复组合（C(n, k) with repetition） | $ C(n + k - 1, k) $ | 允许重复选取元素的组合数 |
三、常见算法实现
1. 阶乘计算（Factorial）
阶乘是排列组合计算的基础，其定义为：
$$
n! = n \times (n-1) \times (n-2) \times \cdots \times 1
$$
算法实现（Python示例）：
```python
def factorial(n):
if n == 0:
return 1
result = 1
for i in range(1, n+1):
result = i
return result
```
2. 排列计算（Permutation）
根据公式 $ P(n, k) = \frac{n!}{(n - k)!} $
算法实现（Python示例）：
```python
def permutation(n, k):
return factorial(n) // factorial(n - k)
```
3. 组合计算（Combination）
根据公式 $ C(n, k) = \frac{n!}{k!(n - k)!} $
算法实现（Python示例）：
```python
def combination(n, k):
return factorial(n) // (factorial(k) factorial(n - k))
```
四、应用实例
| 问题 | 计算方式 | 结果 |
| 从5个球中选3个并排成一行 | 排列 | $ P(5, 3) = 60 $ |
| 从5个球中选3个不考虑顺序 | 组合 | $ C(5, 3) = 10 $ |
| 用数字0-9组成三位密码（允许重复） | 重复排列 | $ 10^3 = 1000 $ |
| 从5个不同颜色的球中选3个放在一起 | 组合 | $ C(5, 3) = 10 $ |
五、注意事项
- 当 $ k > n $ 时，组合数为0。
- 当 $ k = 0 $ 或 $ k = n $ 时，组合数为1。
- 在实际编程中，建议使用动态规划或递归优化阶乘计算，避免大数运算时的性能问题。
总结
排列组合是处理选择与排序问题的重要工具，理解其基本公式和算法对于解决实际问题具有重要意义。通过合理使用排列和组合，可以高效地计算出不同的选择方式，为后续的概率分析、数据结构设计等提供理论支持。
