组合数(卢卡斯定理)

时间:2020-03-10 来源:www.ldwork.com.cn

“组合数”是来自n个不同元素的m(m≤n)个元素的组合。从n个不同的元素中取出m(m≤n)个元素的所有组合数,称为从n个不同的元素中取出m个元素的组合数。

公式:C(n,m)=n!/((n-m)!*m!(m≤n)

property 1: c (n,m)=c (n,n-m)

property 2: c (n,m)=c (n-1,m-1) c (n-1,m)

definition

composition是数学中的一个重要概念。不管顺序如何,一次从n个不同的元素中取出m个不同的元素,叫做从n个元素中选择m个元素的组合而不重复。这种组合的数量称为组合的数量。

属性

1。互补性质

即从M个不同元素中提取的N个元素的组合数=从M个不同元素中提取的(m-n)个元素的组合数;

例如,C(9,2)=C(9,7),即从9个元素中选择2个元素的方法与从9个元素中选择7个元素的方法相同。

规则:C(n,0)=1

2。如果组合标识

表示m个项目选自n个项目,则存在以下公式:c (n,m)=c (n,n-m)=c (n-1,m-1) c (n-1,m)。

来自N个人的K个人的组合数=来自n-1个人的K个人的组合数=来自n-1个人的K个人的组合数

规则:C(n,0)=1

来自N个人的K个人的组合数=来自n-1个人的K个人的组合数=来自n-1个人的K个人的组合数

来自n-1个人的k-1个人的组合数增加到N个人,最后一个人可能被选中,也可能不被选中,有两种情况:

1。未选择,即需要从n-1人中选择K个人。

2。选择时,k-1人需要从n-1人中选择。

这两种情况的总和是从N个个体中选择K个个体的组合数。

卢卡斯定理(Lacus)寻找大组合

°1

现在出现了一个新问题。如果n和m都很大怎么办?

例如,找到C(n,m)% p?N=1e18,m=1e18,p=1e5

看,n和m很大,但是p很小,我们必须用这个p

Lucas来表示

C(n,m)% p?=?C(n/p,m/p) * C(n%p,m%p)%

找到一个大人物的理解过程:

发布一个模板:

规则:C(n,0)=1