分类加法、分步乘法

分完问题

把谁分完谁做指数，结果为$m^n$

染色问题

立体图压成平面图，只要相邻关系一样

全错排问题

• 错排数直接记，D(1)=0，D(2)=1，D(3)=2，D(4)=9，D(5)=44
• 定义：所有人都不对号入座的方法数
  例：用三种颜色染3列2行六个区域，要求同行同列不同色
  先染第一行，然后第二行和第一行错排，$(3{\times}2{\times}1){\times}2$
  变式：若用四种颜色呢？
  分两类：
  第一类：只用三种颜色，$(4{\times}3{\times}2){\times}2$
  第二类：用了四种颜色，假设此区域为4列2行（即在右边补一列），$(4{\times}3{\times}2){\times}9$

排列组合

主要内容

• 排列、排列数、组合、组合数定义
• 组合数两个性质
• 排队问题、排数问题
• 特殊位置、特殊元素：谁少先考虑谁
• 相邻问题：捆绑法
• 不相邻问题：插空法、先排余（注意路灯问题：不亮的路灯不相邻、部分相邻的处理）
• 分排问题：直排处理
• 定序问题：除序。直接说明定序：甲在乙左边（可不相邻）；相同元素：adapt写错；实际问题：摘灯笼
• 环排问题
• 隔板法：相同元素分配给不同的人。正整数解；自然数解；球数不少于编号数；各个位数之和为8的四位数
• 分组分配：先分组后分配。只分组的；平均分组及部分平均分组的；甲单独去A地及甲去A地；有的组已经分好的；最短路径
• 多面手问题：只考虑一边
• 鞋子问题：十双不同的鞋子混在一个口袋中：先选双，再选只

• 几何问题：求对棱数，先求三棱锥数，一个三棱锥有三组对棱

  分组分配问题区分

• 4个不同的球放进3个不同的盒子、盒子不空：先分组后分配
• 4个不同的球放进3个相同的盒子、盒子不空：只分组不分配
• 4个不同的球放进3个不同的盒子、盒子可空：分完问题
• 4个相同的球放进3个不同的盒子、盒子不空：隔板法