组合数公式(组合数怎么计算?)

时间:2023-09-25 09:41:43 阅读:10

组合数怎样盘算?

组合数是指从 n 个不同元素中,任取 m (m≤n) 个元素并成一组,叫作从 n 个不同元素中取出 m 个元素的一个组合;从 n 个不同元素中取出 m (m≤n) 个元素的一切组合的个数,叫作 n 个不同元素中取出 m 个元素的组合数1。用标记 C (n,m) 表现。

比如,从 {a,b,c,d} 中任取两个元素,可以取得六种组合:{a,b}、{a,c}、{a,d}、{b,c}、{b,d}、{c,d}。以是 C (4,2) = 6。

那么怎样盘算 C (n,m) 呢?有以下几种办法:

  • 使用公式法

依据分列数和组合数之间的干系,可以取得以下公式1:

C (n,m) = A (n,m) / m! = n! / [(n-m)! * m!]

此中 A (n,m) 表现从 n 个不同元素中取出 m 个元素的分列数,n! 表现 n 的阶乘(即 n * (n-1) * … * 1),m! 表现 m 的阶乘。

比如,C (4,2) = A (4,2) / 2! = [4 * (4-1)] / [(4-2)! * 2!] = 12 / [2 * 2] = 6

这种办法比力简便直接,但是当 n 和 m 很大时,阶乘运算会很繁复。

  • 使用递推法

依据杨辉三角形(帕斯卡三角形)的实质4,可以取得以下递推公式:

C (n,m) = C (n-1,m-1) + C (n-1,m)

此中 C(n,0)=C(n,n)=1

比如,

C(0,0)=1 C(1,0)=C(1,1)=1 C(2,0)=C(2,2)=1 C(2,1)=C(1,0)+C(1,1)=2 … 以此类推

这种办法可以制止阶乘运算,但是必要存储前方盘算过的后果。

  • 使用编程言语

假如使用编程言语来完成盘算组合数,可以使用以上两种办法大概其他优化算法。比如,在 Python 中:

# 办法一:使用 math 模块提供的阶乘函数 import math def comb_1(n,m):     return math.factorial(n)//(math.factorial(m)*math.factorial(n-m)) # 办法二:使用递归函数和缓存装饰器 from functools import lru_cache @lru_cache(maxsize=None) def comb_2(n,m):         if m == 0 or m == n:             return 1     else:             return comb_2(n-1,m-1)+comb_2(n-1,m)

版权声明:本文来自互联网整理发布,如有侵权,联系删除

原文链接:https://www.yigezhs.comhttps://www.yigezhs.com/shenghuojineng/36643.html


Copyright © 2021-2022 All Rights Reserved 备案编号:闽ICP备2023009674号 网站地图 联系:dhh0407@outlook.com