【数学】组合计数高级技巧 笔记分享

1.加法原理

完成一件事,有k类方法,各类分别有n1、n2……nk种方法

一共有n1+n2+……+nk种方法


2.乘法原理

完成一件事,要k步,各步骤分别有m1、m2……mk种方法

一共有m1•m2•……•mk种方法


3.排列

从m个不同对象中依次选取n个,排成一列,一共有A(n,m)种

A(n,m)=m(m-1)……(m-n+1)=m!/(m-n)!


4.组合

从m个不同对象中选取n个(无序),组成一个集合,一共有C(n,m)种

C(n,m)=m(m-1)…(m-n+1)/n!=m!/(m-n)!n!


例题1

用0、1、2、3、4能组成多少个不同的五位偶数?

A(4,4)+3•A(3,3)+3•A(3,3)=60

答案:60种


例题2

用2个1、3个2、1个3组成多少个6位数?

C(2,6)•C(3,4)•C(1,1)=60

答案:60种


常用方法

(1)枚举法

(2)利用排列数与组合数计算,包括分情况讨论、运用容斥原理,考虑重复情况等

(3)将问题转化为一般性情况,再利用递推的思路解决

(4)构造另一个组合模型,再利用对应的思路解决


5.递推法

例题3

10条直线能把平面分成多少各区域?(思路:将问题一般化处理)

n= 1    2    3    4

m=2    4    7    11

a(n)=a(n-1)+n

a(5)=16    a(6)=22

a(7)=29    a(8)=37

a(9)=46    a(10)=56

答案:56个


6.对应法(构造几何模型)

例如:插板法、标注法(最短路线)

例题4

不定方程x1+x2+x3+x4+x5+x6=10有几组正整数解?(运用插板法)

取10个球,分成6组

OO | OO | O | OOO | O | O

x1    x2  x3    x4    x5 x6

️️即问题转化为在9个空中插入5个隔板

C(5,9)=126


结论1

x1+x2+……+xn=m的正整数解有C(n-1,m-1)组

结论2

x1+x2+……+xn=m的非负整数解有多少组?

→(x1+1)+(x2+1)+……+(xn+1)=m+n

即问题转化为y1+y2+……+yn=m+n的正整数解

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


整理不易,谢谢点赞

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。
禁止转载,如需转载请通过简信或评论联系作者。

推荐阅读更多精彩内容

  • 内容来自百度百科知识以及东方耀老师笔记内容的整合 1、排列组合基本概述 排列组合是组合学最基本的概念。所谓排列,就...
    追梦小乐阅读 5,309评论 0 4
  • 计数工具二项式分解原理鸽巢原理证明具有某种性质的事物的存在 本章内容 1.基本原理2.排列组合3.产生排列组合的算...
    喜忧参半阅读 933评论 0 1
  • 这里称作进阶数学问题,其实着实是因为将线性方程组和期望的问题混合到一起总结,有些不太好起名字,所以采用了进阶数学问...
    kakokuryoku阅读 700评论 0 0
  • 组合数学是离散数学的一个分支。专门研究计数的问题。 数学的发展历史 组合数学的三大问题 存在性是否存在合理的解 计...
    谭英智阅读 1,862评论 0 0
  • 排列组合的定义 排列的定义:从n个不同元素中,任意取m个元素,m≤n且m和n都是自然数,按照一定顺序排成一列,叫做...
    伍帆阅读 5,069评论 6 10