组合数学

枚举法

原则： 按一定顺序，不重复不遗漏地列举所有可能。

例题 1

用1、2、3能组成多少个不同的两位数？

例题 2

小明有3件上衣、2条裤子，共有多少种搭配方法？

每件上衣都可以配2条裤子
3 × 2 = 6（种）

抽屉原理

基本原理

原理1： n+1个物品放进n个抽屉，至少有一个抽屉里有2个或更多物品。

原理2： m×n+1个物品放进n个抽屉，至少有一个抽屉里有m+1个或更多物品。

例题 1

袋中有红、黄、蓝三种颜色的球，至少取几个球才能保证有2个同色？

把三种颜色看作3个抽屉
最坏情况：每种颜色各取1个，共3个
再取1个，必然与某颜色重复

至少取 3 + 1 = 4 个

例题 2

班上有40名同学，至少有几名同学在同一个月过生日？

12个月看作12个抽屉
40 ÷ 12 = 3......4

至少有 3 + 1 = 4 名同学在同一个月过生日

计数原理

加法原理

做一件事，有n类方法，第i类有mᵢ种方法，则共有 m₁ + m₂ + ... + mₙ 种方法。

乘法原理

做一件事，需要n个步骤，第i步有mᵢ种方法，则共有 m₁ × m₂ × ... × mₙ 种方法。

练习题

1. 用0、1、2、3能组成多少个没有重复数字的三位数？
2. 盒子中有红、黄、蓝、白四种颜色的球各5个，至少取几个才能保证有3个同色？
3. 从A地到B地有3条路，从B地到C地有4条路，从A经B到C有多少种走法？