计数

计数的本质

计数的本质是集和的生成(枚举)

扩展到两个集和
加法原理： 当 时成立
乘法原理：

写出具体的一个集和，找规律
将大集合划分为小集和

计数例题

例1：n位二进制数的个数

例2：n位二进制数0比1多的数的个数

例3：把0看作(，1看作)，配对的括号序列有多少个？

例4：求1,2,3…n所有排列的数量

引申：将n个元素分成两个集和k和n-k，每个集合的元素排列数量为k!和(n - k)!，总排列数量为n!
由此可得组合数

例5：错位排列
求所有1,2,3…n的排列中，每个数字都不在原位的排列数量。