组合数学

组合数求法,二项式定理,多重集的组合数与排列数,卢卡斯定理,正整数拆分,卡特兰数,容斥,群论基础及Polya定理

组合数求法:

  • 利用C(n,m)=C(n-1,m)+C(n-1,m-1)的性质可以递推求出0<=y<=x<=n的所有组合数C(x,y),复杂度为O(N^2);
  • 组合数结果一般较大,如果题目要求出C(n,m)对一个数p取模后的值,并且1~n都存在模p的乘法逆元,则可以先计算n! mod p,再计算分母m!(n-m)! mod p的逆元,乘起来得到C(n,m) mod p,复杂度为O(n);
  • 若在计算阶乘过程在把0<=k<=n的每个k! mod p及逆元分别保存在两个数组jc和jc_inv中,则可在O(nlgn)的预处理后,以O(1)的时间回到0<=y<=x<=n的所有组合数C(x,y) mod p=jc[x]·jc_inv[y]·jc_inv[x-y] mod p

二项式定理

  • (ax+by)^n=(k=0->n)∑C(n,k)·a^k·b^(n-k)·x^k·y^(n-k)

多重集的排列数

  • 多重集是的包含重复元素的广义集合。设S={n1·a1,n2·a2,…,nk·ak}是由n1个a1,n2个a2…nk个ak组成的多重集。S的全排列个数为:n!/(n1!·n2!·n3!·…·nk!)。

多重集的组合数

  • r<=min(ni)(i∈[1,k]),从S中取出r个元素组成一个多重集(不考虑元素的顺序),产生的不同多重集的数量为:C(k+r-1,k-1)

卢卡斯定理

  • 对任意正整数1<=m<=n,有C(n,m)≡C(n mod p,m mod p) · C(n/p,m/p) (mod p)。即将n和m表示为p进制数,对p进制下的每一位分别计算组合数,最后再乘起来。

正整数的拆分

  • 就是将一个正整数n拆分成若干个正整数的和,分为有序拆分和无序拆分。有序:(1,2) != (2,1),无序则(1,2) = (2,1)。
  • 用B(n,k)来表示将n个正数拆分成k个数的和,B(n)表示n的所有拆分的个数,显然B(n) = ∑B(n,k)(1<=k<=n)
  • 有序拆分:B(n,k) = C(n-1,k-1),即将n个1拆分成k组,考虑隔板法
  • 无序拆分:使用动态规划解决。用f(n,k)表示将正整数拆分成不大于k的正整数之和。
    则:
    • 当n == k时,一种情况是拆分成1个n,另一种情况是由不大于n-1的数组成n,所以f[n][k] = 1+f[n][n-1]
    • 当n < k时,因为用于拆分的数不能比n大,所以f[n][k]=f[n][n]
    • 当n > k时,一种情况是用小于m的数进行拆分;另一种情况是拆分的数中最大值为k,其他数之和为n-k,问题转换为用不大于k的数对n-k进行拆分。所以f[n][k] = f[n][k-1] + f[n-k][k]
    • 初态f[i][1] = f[1][i] = 1;
      1
      2
      3
      4
      5
      6
      7
      8
      9
      rep(i,1,n){
      rep(j,1,n){
      if(i==1 || j==1) f[i][j] = 1;
      else if(i==j) f[i][j] = f[i][j-1]+1;
      else if(i<j) f[i][j] = f[i][i];
      else f[i][j] = f[i][j-1]+f[i-j][j];
      }
      }
      ans = f[n][n];

卡特兰数

  • 给定n个0和n个1,它们按照某种顺序排成长度为2n的序列,满足任意前缀中0的个数都不少于1的个数的序列的数量为:Catn=C(2n,n)/(n+1)。以下问题都与Catalan数有关:
    • n个左括号和n个右括号组成的合法括号序列的数量为Catn
    • 1,2,..,n经过一个栈,形成的合法出栈序列的数量为Catn
    • n个节点构成的不同二叉树的数量为Catn
    • 在平面直角坐标系上,每一步只能向上或向右走,从(0,0)走到(n,n)并且出两个端点外不接触直线y=x的路线数量为2Cat(n-1)

容斥原理

  • 设S1,S2,S3…Sn为有限集合,|S|表示集合S的大小,则:|∪Si|=∑|Si|-∑|Si ∩ Sj|+∑|Si ∩ Sj ∩ Sk|-∑|Si ∩ Sj ∩ Sk ∩Sl|+…+(-1)^(n+1)|S1 ∩ S2 ∩…∩ Sn|。
  • 求1到m中能被A集合中元素(存在即可)整除的数有多少个。
    1
    2
    3
    4
    5
    6
    void dfs(int x,int k,int t){
    if(x>0) ans+=m/t*k;
    for(int i=x;i<n;i++)
    dfs(i+1,-k,lcm(a,t));
    }
    dfs(0,-1,1);

多重集的组合数

  • 设S={n1·a1,n2·a2,…,nk·ak}。设n=∑ni,对于任意整数r<=n,从S中取出r个元素组成一个多重集(不考虑顺序),产生的不同多重集的数量为:C(k+r+1,k-1)-∑C(k+r-ni-2,k-1)+∑C(k+r-ni-nj-3,k-1)-...+(-1)^k·C(k+r-∑ni-(k+1),k-1)
  • Devu与鲜花:Devu有N个盒子,第i个盒子中有Ai枝花。同一个盒子内的花颜色相同,不同盒子内的花颜色不同。Devu要从这些盒子中选出M枝花组成一束,求共有多少种方案。若两束花每种颜色的花的数量都相同,则认为这两束花是相同的方案。结果需对109+7取模之后方可输出。此题等价于多重集S中选出M个原色能产生的不同多重集的数量。

置换群和Polya定理

  • 给定一个集合G={a,b,c…}和集合G上的二元关系,并满足:
    • 封闭性:对于G中的任意a,b,存在c属于G,满足axb = c
    • 结合律:对于G中任意a,b,c,(axb)xc = ax(bxc)
    • 单位元:对于G中任意a,存在e属于G,使得axe = exa = a
    • 逆元:对于G中任意a,都存在b属于G,使得axb = e。
      则称集合G在x运算下是一个群,axb简写为ab

置换

使一个元素被替换成另一个元素的规则

其中的数字i表示上面的ci

置换群

即所有置换的集合,如{转0°,转90°,转180°,转270°},运算是置换的连接,例如:

Zk——k不动置换类

  • 设G是1…n的置换群.若k是1…n中的某个元素,G中使得k不变的置换集合记为Zk,叫做使k保持不动的置换类,简称k不动置换类。
  • 对于元素C1,四个置换都保持其不变,Z1={a1,a2,a3,a4};
    对于元素C3,只有置换a1使其不变,Z3={a1};
    对于元素C11,a1和a3使其不变,Z11={a1,a3}。

Ek——等价类

  • 设G是1…n的置换群,则Ek表示k在G作用下的轨迹,即k在G的作用下能化成的元素的集合。
  • E1={c1}, E3={c3,c6,c5,c4}, E11={c11,c12}

Burnside定理

  • L表示互异的组合装态的个数,即本质不同的组合方案数
  • G(aj)表示在置换aj下不变的元素个数
  • 若元素i在置换j下保持不变,则f[i][j]=1,否则为0,整个矩阵的和除以置换数即为所求。

循环

  • 将a[i]与i连一条边,最终会形成数个环,一个环即为一个循环,环数即为循环节数。上诉表示的循环节数为3

Polya定理

  • 设G是p个对象的置换群,用m种颜色染p个对象,则本质不同的染色方案数为:

    其中G={g1,g2,g3…gn},c(gi)表示gi的循环节个数。

Polya定理的应用

  • Arif in Dhaka:用t种颜色组成n颗珠子的项链和手镯,项链可旋转,手镯可旋转和翻转,求本质不同的项链(旋转后不一样)和手镯数量
  • 项链:共有n个置换方式,分别为旋转1,2,3…n个单位,对于旋转i个单位,循环节的个数为gcd(n,i),证明如下:
    • 假设置换gk表示旋转k位,则i,i+k,i+2k……i+tk (%n) 组成一个循环,求解k*t%n==0的最小t,t=lcm(n,k)/k=n/gcd(n,k),即一个循环里面有n/gcd(n,k)个元素,又因为每个循环的元素个数相同,所以gk有n/(n/gcd(n,k))=gcd(n,k)个循环节。
      然后带入公式L = ∑(p^gcd(i,n)) / n
  • 手镯:
    • 旋转:令a= ∑(p^gcd(i,n)) ;
    • 翻转:分奇偶讨论。
    • 若为奇数,则有n个翻转置换,对称轴是一个珠子到圆心的连线,对称轴上的珠子自成一个循环,其他的n-1个珠子以对称轴构成(n-1)/2个循环,每个置换循环节个数为1+(n-1)/2=(n+1)/2。b = np^((n+1)/2)
    • 若为偶数,则一类置换方式为以两个珠子的连线为对称轴,共n/2个置换,每个置换循环节个数为2+(n-2)/2;另一类置换方式为以两个珠子的中点与圆心的连线,共n/2个置换,每个置换循环节个数为n/2。b = [p^((n+2)/2)+p^(n/2)]*(n/2)
    • L = (a+b)/(2*n)
Donate comment here