基础知识整理：

（1）加法原理

（2）乘法原理

（3）容斥原理（注意变式问题）

（4）排列组合公式的应用及变形：

       排列的公式：

       其变形为：

        与组合的关系如下（以下第一个公式很重要）：

       排列组合公式的重要推论：

         推论1：

           对于第一个物体如果不取的话，那么我们有C（n,k+1)种方法，对于第一个物体取的话，我有C（n,k)种方法。公式得证。

         推论2：

        这可以降低求解二项式系数的时间复杂度，通过利用递推关系自小到大依次计算得出，方便快捷。

（5）排列组合的基本问题：

  Q1：求有重复元素的排列。

         有k个元素。其中第i个元素有n_i个，求全排列个数。

          根据排列组合基本原理有：

 Q2：可重复选择的集合。有n个不同元素，每个元素可以选多次，一共选k个元素，有多少种方法？

         我们可设第i个元素有x_i个，问题转化为：

          问题的解变化为该公式中非负整数解的个数，令

         我们可以得到：

        此时问题的求解变为：方程中变量为正整数解的个数。因为为正整数，那么我们可以得出一个结论：我们只能在n+k-1中插（n-1）块木板（高中的插板法）进而得到所有变量的解个数。

         此时我们得到结果为：

Q3：单色三角形。给定空间的n个点，其中没有三点共线。每两个点之间都用红色或者黑色线段连接。求三条边都同色的三角形个数。

       根据题意，如果直接正向枚举，那么时间复杂度过高。我们可以采取补集思想，先枚举不是单色三角形的情况。对于每一个点而言，与之相连的点共有（n-1)条边。我们可以假设和点i相连的红色边有a_i条，黑边有（n-1-ai)条.那么同一点的两条不同颜色的边必定可以构成唯一的一个三角形，

那么根据乘法原理我们可以得到对于点i的非单色三角形个数为

 有于一共有n个点，并且每一条边会计数两次。所以需要把累加和除以2求得最终结果为：

最后我们可以求得单色三角形数目为：

OVER~寇小编还是很用心的，希望对各位偶然逛到我博客的博主有所帮助！！！

算法竞赛入门经典行训练指南【计数方法】------2015年1月23日