计数技术基础

乘法原理与笛卡尔积的基数

$|A1 \times A2 \times \dots \times Am |= |A1||A2| \dots |Am|$

容斥原理

有根树图

鸽巢原理

• 推论：一个从m个元素到n个元素（m>n)的函数不可能是单射。
• 广义鸽巢原理
  • 如果N 个物体放置到k个盒子中，那么至少 有一个盒子装有不少于⌈N/k⌉个物体。
  • 关键词：至少，分配（/填色/分类）
  • 要用上鸽巢原理就要灵活转换问题
• 可用结论：
  • 任何一个正整数都给可以分解为一个2的次幂×一个奇数

排列组合

乘法原理，加法原理，组合，排列

二项式系数与组合分析法

组合分析法证明

允许重复的n元素的r排列

$n^r$

允许重复的n元素的r组合

$C_{n+r-1}^r$

思想：隔板选位，不定方程求解

可分辨与不可分辨的分配问题