组合计数课件.pdf

组合计数 基础  加法原理：一件事有两类做法，第一类有m种做法，第二类有n 种做法，则这件事共有mn种做法。  加法原理：一件事分两步做，第一步有m种做法，第二步有n种 做法，则这件事共有mn种做法。  排列：m件不同的物品中选取n件排成一排，排列方式的数目是 ! !  组合：m件不同的物品中选取n件，选取方法的数目是 ! ! !  组合与排列不同的是，组合不计次序。 可重复的排列  m种不同的物品中选取n个，可重复选取，排成一排，排法的数目 n 是m . 证明：n个位置，每个位置有m个选择方式。  m种不同的物品总共n个，第i种物品有n个，n个物品排成一排，i 排列方式的数目是 ! , ,…, ! !… ! 证明：n个位置中选取n 个放置第1种，在剩下nn 位置中选取n 个 1 1 2 放置第2种，…. ，总选取方式有 ! ! ! … … ! ! ! ! ! ! ! !… ! 可重复的组合  m种不同的物品中选取n个，可重复选取 设第i种物品选取xi个，选法的数目等于以下方程的正整数解 的个数。  x x … x n ，x 0. 1 2 m i 也等于放法的数目  n个相同的球放入m个不同的盒子 1  解是 证明：问题相当于n个