logo

您所在位置网站首页 > 海量文档  > 计算机 > 软件编程

组合数学容斥原理.ppt 148页

本文档一共被下载: ,您可全文免费在线阅读后下载本文档。

  • 支付并下载
  • 收藏该文档
  • 百度一下本文档
  • 修改文档简介
全屏预览

下载提示

1.本站不保证该用户上传的文档完整性,不预览、不比对内容而直接下载产生的反悔问题本站不予受理。
2.该文档所得收入(下载+内容+预览三)归上传者、原创者。
3.登录后可充值,立即自动返金币,充值渠道很便利
特别说明: 下载前务必先预览,自己验证一下是不是你要下载的文档。
  • 上传作者 爱是你我(上传创作收益人)
  • 发布时间:2019-05-15
  • 需要金币100(10金币=人民币1元)
  • 浏览人气
  • 下载次数
  • 收藏次数
  • 文件大小:677 KB
下载过该文档的会员
你可能关注的文档:
第三章 容斥原理和鸽巢原理 §1 容斥原理引论 例 [1,20]中2或3的倍数的个数 [解] 2的倍数是:2,4,6,8,10, 12,14,16,18,20。 10个 3的倍数是:3,6,9,12,15, 18。 6个 但答案不是10+6=16 个,因为6, 12,18在两类中重复计数,应减 去。故答案是:16-3=13 容斥原理研究有限集合的交或并 的计数。 [DeMorgan定理] 论域U,补集  定理 设¢(n,k)是[1,n]的所有k- 子集的集合, 则 |∪Ai | = ∑ (-1)k-1 ∑ | ∩ Ai | 证 对n用归纳法。n=2时,等式成立。 假设对n - 1,等式成立。对于n有 §3.6 一般公式 间的位置为第 n 号位置。设第 i 号女人的丈 夫的编号也为第 i 号,1≤ i ≤ n。让 n 个男 人坐到上述编号的 n 个位置上。设 ai是坐在 第 i 号位置上的男人,则 ai ≠ i ,i + 1,1≤ i ≤n-1;an≠n,1。 这样的限制也即要求在下面3行n列的排列中 1 2 3  ···  ··· n-1 n 2 3 4  ···  ··· n   1 a1  a2 a3 ··· ··· an-1 an §3.6 一般公式 每列中都无相同元素。满足这样的限制的排 列 a1a2 ···an称为二重错排。 设二重错排的个数为Un,原问题所求的方案 数就是Un ( n-1)!。 设Ai为 ai = I 或 I + 1 (1≤ I ≤n-1 ),an = n 或1的排列 a1 a2 ··· an的集合。则 |Ai|= 2 (n-1)! ,关键是计算∑  |∩Ai|  I ∈¢( n , k) i∈I §3.6 一般公式 也就是从( 1 , 2 ) ( 2 , 3 ) ··· ( n-1, n ) ( n , 1) 这n对数的k 对中各取一数,且互不相同的 取法的计数。这相当于从1 , 2 , 2 , 3 ,3 ,4, ···, n-1, n-1, n , n , 1中取 k 个互不相邻数的组 合的计数,但首尾的1不能同时取。回想无 重复不相邻组合的计数: C’( n , r ) = C ( n-r + 1 , r ) ,这里所求的是 ( )-( )= ( ) 2n-k+1 k 2n-4-( k-2)+1 k-2 2n-k k 2n 2n-k §3.6 一般公式 ∴ Un =∑(-1)k ( )(n-k)! = |∩ Ai| 2n 2n-k 2n-k k i ∈[ 1 , n ] §3.11 反演 基本想法:{an} 易算,{bn}难算,{an}可用 {bn}表示,利用反演,将{bn}用{an}表示. 1.二项式反演 引理 §3.11 反演 证  §3.11 反演 定理 证 §3.11 反演 推论 证 在定理中bk处用(-1)k bk代入,即可. 例 n! = ∑ ( ) Dn-k,Dn=bn, 令n-k = l ,则 n! = ∑ ( ) Dl Dn = ∑ (-1)n-k ( )k! = n! ∑ (-1)n-k = n ∑ n k n k n k 1 (n-k)! k=0 k=0 k=0 n n n (-1)k k! §3.11 反演 2. Mǒbíus反演 定义 设 n ∈Z+ 1,若 n = 1; μ( n ) = 0,若n = p1α1 p2α2 ··· pkαk 存在αi>1 (-1)k ,若n = p1p2···pk 如 μ( 30) = μ( 2·3·5 ) = (-1)3 μ( 12) = 0; §3.11 反演 定理 设n ∈Z+ 则 ∑ μ( d ) = 1,若n = 1; 0,若n > 1; d | n 证 若n =1, ∑ μ( d ) = μ( 1 ) = 1,成立. 若 n>1,设n = p1α1 p2α2 ···

发表评论

请自觉遵守互联网相关的政策法规,严禁发布色情、暴力、反动的言论。
用户名: 验证码: 点击我更换图片

2010-2013 max.book118.com在线文档投稿赚钱网. All Rights Reserved 蜀ICP备08101938号