关于组合数学

M1__ · 2024-08-24 21:29:52 · 算法·理论

• 排列组合的一些公式及推导(非常详细易懂)

• 错排公式

  D_1=0,D_2=1,D_n=(n-1)(D_{n-2}+D_{n-1})

• 特殊性质：

  C^0_n=1 C^m_n=C^{n-m}_n C^m_n=C^{m-1}_{n-1}+C^{m}_{n-1}

• 其中第三个还和杨辉三角有关。

• 另外，还有一些公式：

• 从 n 个不同的元素取 m 个元素（可以重复取）的排列个数为 n^m 。

• 把 n 个相同的元素分成 m 个不同的组，每组至少有一个元素的方案数位 C^{m-1}_{n-1} 。

• 把 n 个相同的元素分成 m 个不同的组，每组可以一个元素也没有的方案数为 C^{m-1}_{n+m-1} 。（隔板法）

• 从 n 个不同的元素中取 m 个元素（元素可以重复取）的组合个数为 C^{n-1}_{n+m-1}