wxw 小站
    笔记奶爸

    组合与计数—题目整理

    可打印版本 · 清爽排版 · A4 适配

    基础原理

    加法原理(Rule of Sum)

    若有 A 种方式完成某件事情,又有 B 种方式完成另一件事情,且这两种方式互斥(不能同时发生),则完成这两件事情的总方案数为 A + B 种。

    乘法原理(Rule of Product)

    若完成一项任务分为若干步:第一步有 A 种选择,并且对每一种选择,第二步有 B 种选择(以此类推),且各步相互独立,则总方案数等于各步方案数的乘积,例如 A × B(× …)。

    容斥原理

    一种用于计算多个集合并集中元素个数的方法。基本思想:先不考虑重叠把包含于某内容中的所有对象的数目计算出来,再把计数时重复计算的数量排除,使结果既无遗漏又无重复。

    $\lvert A \cup B \rvert = \lvert A \rvert + \lvert B \rvert - \lvert A \cap B \rvert$

    $\lvert A \cup B \cup C \rvert = \lvert A \rvert + \lvert B \rvert + \lvert C \rvert - \lvert A \cap B \rvert - \lvert A \cap C \rvert - \lvert B \cap C \rvert + \lvert A \cap B \cap C \rvert$


    常见方法

    1. 捆绑法

      题目:7 名学生站成一排,甲、乙必须站在一起,有多少不同排法?
    2. 插空法

      • 题目 2.1:7 名学生站成一排,甲、乙互不相邻,有多少不同排法?
      • 题目 2.2(NOIP2008):书架上有 21 本书,编号从 1 到 21,从中选 4 本,其中每两本的编号都不相邻。共有( )种选法。
        提示:序号示意:1 2 3 4 5 6 7 8 9 10 11 12 …
    3. 排除法

      题目:共有六个科目:语文、数学、英语、物理、化学、体育。一天 6 节课,每天每个科目都上一节。第一节不能排体育,最后一节不能排数学。这一天共有多少种排课方法?
    4. 先选后排法

      题目:从 萝卜、白菜、黄瓜、西红柿 四种蔬菜中选出 3 种,分别种在 不同土质 的三块土地上,且 萝卜必须种植。不同的种植方法共有( )种。
    5. 隔板法

      • 八个名额分配给三个班级,每个班至少有一个名额。
      • 八个名额分配给三个班级,允许某些班没有名额。

    历年与专项选择题

    【2019 年第 7 题】
    把 8 个同样的球放在 5 个同样的袋子里,允许有的袋子空着不放,问共有多少种不同的方法?( )
    提示:如果 8 个球都放在 1 个袋子里,无论是哪一个袋子,都只算同一种方法。
    • 22
    • 24
    • 18
    • 20
    【2019 年第 13 题】

    有些数字可以倒过来看。例如:

    • 0、1、8 倒过来仍是 0、1、8;
    • 6 倒过来是 9;9 倒过来是 6;
    • 其他数字倒过来都不构成数字。

    类似地,一些多位数也可以倒过来看,例如 106 倒过来是 901。

    假设某城市的车牌号码由 5 位数字组成,每一位都可取 0–9。问:这个城市最多有多少个车牌号码倒过来仍然是原来的车牌号?( )

    • 60
    • 125
    • 75
    • 100
    【2020 年第 10 题】
    5 个小朋友并排站成一列,其中有两个小朋友是双胞胎。如果要求这两个小朋友必须相邻,则有( )种不同的排列方法。
    • 48
    • 36
    • 24
    • 72
    【2020 年第 14 题】
    把 10 个三好学生名额分配到 7 个班级,每个班级至少有 1 个名额,共有( )种不同的分配方案。
    • 84
    • 72
    • 56
    • 504
    【2020 年第 15 题】
    有 5 副不同颜色的手套(共 10 只,每副左右各 1 只),一次性从中取 6 只。问:恰好能配成两副手套的不同取法有( )种。
    • 120
    • 180
    • 150
    • 30
    【2021 年第 10 题】
    有 6 个人,两个人组成 1 队,一共组成 3 队,不区分队伍编号。不同的组队情况有( )种。
    • 10
    • 15
    • 30
    • 20
    【2021 年第 12 题】(新增)
    用数字 1、1、2、2、3 组成不同的三位数共有( )种。
    • 18
    • 15
    • 12
    • 24
    【2023 年第 14 题】(新增)
    一个班级有 10 个男生和 12 个女生。要选出一个 3 人小组,并且小组中至少包含 1 个女生。问:共有多少种可能的组合?( )
    • 1420
    • 1770
    • 1540
    • 2200

    参考答案与解法

    1. 【2019 年第 7 题】答案:C(18)

      同球、同袋,相当于把 8 拆成至多 5 个正整数之和(不计顺序)。 8 的划分数 p(8)=22。剔除“分成 ≥6 份”的 4 种:

      6 份:$1+1+1+1+1+3$, $1+1+1+1+2+2$

      7 份:$1+1+1+1+1+1+2$

      8 份:$1+1+1+1+1+1+1+1$

      故 $22-4=18$。

    2. 【2019 年第 13 题】答案:C(75)

      五位“倒看不变”号(0/1/8 自身,6↔9)。车牌号可以以 0 开头,因此首位允许 0。

      $5$ 种首末对(00、11、88、69、96)

      $5$ 种次末对(00、11、88、69、96)

      中间位 $3$ 种(0、1、8)

      合计 $5\times5\times3=75$。

    3. 【2020 年第 10 题】答案:A(48)

      把双胞胎视为一个“捆绑体”,与另外 3 人共 4 个单元,排法 4!;捆绑体内部可交换 2!。

      $4!\times 2=48$。

    4. 【2020 年第 14 题】答案:A(84)

      隔板法(正整数解):x₁+…+x₇=10,xᵢ≥1。

      $\binom96=\binom96=84$。

    5. 【2020 年第 15 题】答案:A(120)

      先选成对的两色,再选两只“散单手套”。

      成对:$\binom52=10$

      散单:从剩余 3 色中选 2 色且各取一只:$\binom32\times 2^2=3\times4=12$

      总数 $10\times12=120$(恰好两副,且其余两只不同色不会再成对)。

    6. 【2021 年第 10 题】答案:B(15)

      6 人两两配对(队伍不区分),为完美匹配数:(2n−1)!!,n=3。

      $5\times3\times1=15$。

    7. 【2021 年第 12 题】答案:A(18)

      从 3 取 3 位组成不同三位数:

      全异:$\{1,2,3\} \Rightarrow 3! = 6$

      两同一异:$\{1,1,2\}, \{1,1,3\}, \{2,2,1\}, \{2,2,3\}$ 各 $\tfrac{3!}{2!}=3$,共 $12$

      合计 6+12 = 18。

    8. 【2023 年第 14 题】答案:A(1420)

      至少 1 个女生:总选法减去“全是男生”。

      $\binom223 - \binom103 = 1540 - 120 = 1420$。