组合数学

liyao2025 · 2025-11-25 13:42:52 · 算法·理论

1.鸽巢原理

定理

如果把 N+1 个物品放入 N 个盒子中，那么至少有一个盒子中有两个或更多的物品，

推论

公式证明：

组合意义1：是否包含某个（最后一个）元素。

递推关系---杨辉三角

计算组合数

方格路径数

3.组合的定义和模型

组合定义 combination

从n个元素中任取 r 个元素一组，若不考虑他们的顺序时，则称为从 n 中取 r 的组合它的方案数以 C(n,r) 或 表示

例如从 (A,B,C,D) 中取三个为一组，可有 (A,B,C), (A,B,D), (A,C,D), (B,C,D) 四个组，故C(4,3)=4.

模型1：

组合的典型问题是把 n 个有标志的球, 取 r 个放到 r 个无区别的盒子里, 每盒 一个.

模型2：

也可以看作是取 r 个无标志的球, 放到 n 个有区别的盒子, 每盒一球的方案数

组合公式

排列与组合的模型的区别在于盒子，排列的盒子有区别，组合的盒子无区别.放进 r 个盒子的球的全排列为 r!, 这就是组合的重复度，故

组合练习

• 从 1~300 之间任取 3 个不同的数：有几种方案?

:::info[答案]

:::

• 如果要使得这3个数的和正好被3除尽,问共有几种方案?

:::info[答案]

:::

• 平面上有三条平行直线，每条直线上分别有7, 5, 6个点，目不同直线上三个点都不在同一条直线上。问用这些点为顶点，能组成多少个不同三角形?

:::info[答案]

:::

• 平面上有三条平行直线，每条直线上分别有7, 5, 6个点，目不同直线上三个点都不在同一条直线上。问用这些点为顶点，能组成多少个不同的四边形? :::info[答案] 2250

  :::

3.排列的定理

例如：P(5,3) = 5*4*3 = 5!/2!

全排列: n! =1*2*3…*n

特别： 0!=1

例题：字母排列

将 a, b, c, d, e, f 进行排列.问:

• 排列有多少种?

:::info[答案]

:::

• 使得字母b正好在字母e的左邻的排列有多少种?

:::info[答案]

:::

• 使得字母b在字母e的左边的排列有多少种? :::info[答案] 6 * 5 * 4 * 3 * 2 * 1 / 2

  :::

  4.组合数学之加\减\乘\除原理

  加法原理

若具有性质 A 的事件有 m 个，具有性质 B 的事件有 n 个，则具有性质 A 或性质 B 的事件有 m+n 个。

设集合 S 被划分成两两不相交的部分S_1，S_2....S_m。则 S 的对象数目可以通过确定它的每一个部分的对象数目并如此相加而得到:

乘法原理

若具有性质 A 的事件有 m 个，具有性质 B 的事件有 n 个，则具有性质 A 及性质 B 的事件有 m*n 个。

减法原理

除法原理

例题

• 在所有六位二进制数中，至少有连续 4 位是 1 的有(___)个 :::info[答案]

  8

  :::

• 计算机密码是由取自于数字 0，1，2 的数字和取自于小写字母 a，b，c 的字母组成的长度为 6 的字符串。有多少个可以有重复字符的计算机密码？

:::info[答案]

:::

• 在 1000 到 9999 之间有多少个各位数字不同的奇数?

:::info[答案]

:::

• 由数字 1，1，1，3，8 可以构造出多少个不同的 5 位数?

:::info[答案]

:::

• 求小于 10000 的正整数中含有数字 1 的数的个数。 答案： :::info[答案]

  9999-9 * 9 * 9 * 9+1

  :::

• 有日文书 5 册，英文书 7 册中文书 10 册，

1. 若从中取两册不同文字的书有几种可能? :::info[答案]

   155

   :::

2. 若取两册是相同文字的又有多少种方案?

:::info[答案]

:::

3. 若取两本不论是什么文字的又有几种方案? :::info[答案] 231

   :::

   • 有 a,b,c,d,e 这 5 个字，从中取 6 个构成一组字符串,要求
4. 第 1 个和第 6 个必须是子音 b,c,d ；
5. 每一字符串都必有 a,e 两个母音，且 a,e不相邻；
6. 相邻两子音不允许相同。求字符串的数目。 :::info[答案] 324

   :::

   • 比 5400 大的四位整数中，数字 2，7 不出现，且各位数字不同的整数有多少个? :::info[答案] 1 * 4 * 6 * 5 + 3 * 7 * 6 * 5

     :::