归一法在计数原理中的运用

    徐涛

    

    计数原理这一章的某些问题，诸如：分组问题和环排问题和恒等证明问题，不少同学感到甚是棘手，其实教材已给出了解决之道：归一法.

    研究组合数Cm?n的公式，教材的处理如下：

    考查模型（Ⅰ）：从n个不同的元素中任取m个元素可组成多少个排列？

    法一：由排列知识可知：从n个不同的元素中任取m个元素可组成Am?n个排列;

    法二：第一步：从n个不同的元素中取出m个元素，共有Cm?n种取法，第二步：将取出的m个元素做全排列，共有Am?m种排法，由分步乘法计数原理得：从n个不同的元素中任取m个元素可组成Cm?n·Am?m个排列.

    因法一、法二都解决了模型（Ⅰ），故有：Am?n=Cm?n·Am?m，解得：Cm?n=Am?nAm?m.

    一、分组问题

    例1有9本不同的书，将其分成如下3组，各有多少种分法？

    （1）每组3本;

    （2）一组5本，另两组各2本;

    （3）一组2本，一组3本，一组4本.

    解：（1）考查模型（Ⅱ）：将9本书平分给甲、乙、丙三人，共有多少种分法？

    法一：第一步：甲分3本书，有C3?9种分法，第二步：乙分3本书，有C3?6种分法，第三步：丙分3本书，有C3?3种分法.由分步乘法计数原理得：甲、乙、丙各得3本，共有C3?9·C3?6·C3?3种分法.

    法二：第一步：将9本书分成3组，每组3本，设有x?1种分法;第二步：将这3组分给甲、乙、丙3人共有A3?3种分法.由分步乘法计数原理得：甲、乙、丙各得3本，共有x?1·A3?3种分法.因法一、法二都解决了模型（Ⅱ），故有：C3?9·C3?6·C3?3=x?1·A3?3，解得：x?1=C3?9C3?6C3?3A3?3.

    （2）考查模型（Ⅲ）：将9本书分给甲、乙、丙三人，甲得5本，乙、丙各得2本，共有多少种分法？

    法一：第一步：甲分5本书，有C5?9种分法;第二步：乙分2本书，有C2?4种分法;第三步：丙分2本书，有C2?2种分法.由分步乘法计数原理得：甲得5本，乙、丙各得2本，共有C5?9·C2?4·C2?2种分法.

    法二：第一步：将9本书分成3组，一组5本，另两组各2本，设有x?2种分法;第二步：将这3组分给甲、乙、丙3人共有A2?2种分法.由分步乘法计数原理得：甲得5本，乙、丙各得2本，共有x?2·A2?2种分法.因法一、法二都解决了模型（Ⅲ），故有：C5?9·C2?4·C2?2=x?2·A2?2，解得：x?2=C5?9·C2?4·C2?2A2?2.

    （3）考查模型（Ⅳ）：将9本书分给甲、乙、丙三人，甲得2本，乙得3本、丙得4本，共有多少种分法？

    法一：第一步：甲分2本书，有C2?9种分法;第二步：乙分3本书，有C3?7种分法;第三步：丙分4本书，有C4?4种分法.由分步乘法计数原理得：甲得2本，乙得3本、丙得4本，共有C2?9·C3?7·C4?4种分法.

    法二：第一步：将9本书分成3组，一组2本，一组3本，一组4本，设有x?3种分法，第二步：将这三组分给甲、乙、丙三人共有1种分法，由分步乘法计数原理得：甲得2本，乙得3本、丙得4本，共有x?3·1种分法.

    因法一、法二都解决了模型（Ⅳ），故有：C2?9·C3?7·C4?4=x?3·1，解得：x?3=C2?9·C3?7·C4?4.

    评析：解决分组问题，可构建一个组合模型，用归一法解決.

    二、恒等证明

    例2证明：（C0?n）2+（C1?n）2+（C2?n）2+…+（Cn?n）2=Cn?2n.

    证明：考查模型（Ⅵ）：某校高一年级1班和2班各有n个同学，从这两个班选出n个同学去养老院为老人打扫卫生，共有多少种选法？

    法一：第一类：1班选0个同学，2班选n个同学，有C0?n·Cn?n=（C0?n）2种选法，第二类：1班选1个同学，2班选n-1个同学，有C1?n·Cn-1?n=（C1?n）2种选法，第三类：1班选2个同学，2班选n-2个同学，有C2?n·Cn-2?n=（C2?n）2种选法，…，第n+1类：1班选n个同学，2班选0个同学，有Cn?n·C0?n=（Cn?n）2种选法，由分类加法计数原理得：共有（C0?n）2+（C1?n）2+（C2?n）2+…+（Cn?n）2种选法.

    法二：两班共计2n个同学，从这2n个同学选出n个，共有Cn?2n种选法.

    因法一、法二都解决了模型（Ⅵ），故有：（C0?n）2+（C1?n）2+（C2?n）2+…+（Cn?n）2=Cn?2n.

    评析：解决恒等证明问题，可构建一个排列或组合模型，用归一法解决.