离散数学排列与组合_离散数学合成运算

离散数学排列与组合_离散数学合成运算

(7.17)熬个夜的博客哦 (部分题目参考离散数学及其应用 原书第7版 [(美)KENNETH H.ROSEN著;徐六通,杨娟,吴斌])
前言: 对于这些问题,其实自从高中开始,我自己学的就不是很好,眼看着要到大二了,要学的可多了,有什么概率论与随机过程,运筹学,离散还没学完啊。不废话了,这篇让我亲自再做一遍,再写一遍理解吧,加深印象和理解。

先来浅谈一下排列吧。

  1. 从五个学生里面选出三个学生站成一行拍照,有几种选择的方法?再让五个学生站成一行照相,又有几种呢?
    回答:解答这个问题还好吧,毕竟拍照站的时候是有顺序的,比如从左边开始,选第一个学生站有5种方法,选第二个位置的学生有4种方法,当然选第三个位置的有3种方法,一共呢,根据乘法原理就是5 x 4 x 3 = 60种;
    而第二问,五个学生都排的话,就是5 x 4 x 3 x 2 x 1 = 120种方法,很好理解。
    看了这一个,我们想想这一类的问题,涉及次序在里面,从m个中选n个,则有p(m,n)=m (m-1) …(m-n+1)种可能性
    需要注意的是啥呢?就是n=0时,p(m,n)=1.

  2. 在进入刘木中学比赛的时候,要从100个人中选出一个一等奖,一个二等奖,和一个三等奖得主,问有几种方案?
    回答: 这个问题和第一个有点类似,一二三等奖在某种程度上也可以认为就是从左到右的一二三个位置,选第一个位置100种,选第二个位置99种,第三个位置就是98种,那么一共就是100 x 99 x 88=970 200;或者直接用p(100,3)=970 200;

  3. 在陪女朋友买衣服的时候呢,进入一家购物商场,女友坚持要买7件衣服且在不同的店购买,买这7件衣服有多少种顺序?
    回答: 与上文类似,直接7x6x5x4x3x2x1 = 7! = 5040种方法;

在这想象还是挺简单啊?
再谈谈组合吧

  1. 从五个人中选出四个人组成冲锋队,有多少种选择方法?
    回答:很明显,没有了次序的困扰,但我们依然可以按照有顺序来思考,就是四个位置,就有5x4x3x2 = 120种,再除去顺序的4x3x2x1=24,那么就是120/24=5种方案;如果这样不好思考,也可以直接从五个种找四个素组成的集合,我们知道就是5种 ;或者从反面思考,去除一个人,就是5种去除的方法;
    看了这一个,同样我们想想这一类的问题,不涉及次序在里面,从m个中选n个,则有C(m,n)=m (m-1) …(m-n+1)/n!种可能性 or m!/(n!(m-n)!)种
  2. 从52张牌中,选出4张,有几种方法?或者选48张,又有几种方法?
    回答:第一个问题,就是4个素的集合,就是C(52,4)=270 725种方法;第二个就是C(52,48) = 270 725,发现是相等的;因此得到C(m,n) = C(m,m-n);

后面是排列与组合的推广

有重复的排列和组合

  • 用英文大写字母可以写出多少个长度为 r 的字符串?
    26x26x26…26×26=26^r个;
    规律就是n^r种;
  • 从包含火龙果,猕猴桃,芒果的篮子里选出四个水果(前提是每种水果碗里至少有4个),有几种方法?
    想了颇久,还是用最笨的方法全列出来
    Dragon Fruit—-D;
    Kiwifruit—-K;
    Mang—-M;
4D 4K
3D,1K 3D,1M
3K,1M 3K,1D
2D,2K 2D,2M
2D,1K,1M 2K,1D,1M
4M 3M,1D
3M,1K 2M,2K
2M,1K,1D

一共15中方式

  • 从包含1美,2美,5美,10美,20美,50美以及100美的钱袋中选出五张纸币,有多少中方式?
    回答:意思是从7个素的集合中允许重复的五素组合问题
    原创

对于这个问题,很典型,可以归纳得到m个素的集合中允许重复的n组合,那么一共有C(m+n-1,n)种组合方式。

  • 方程x1+x2+x3=11有多少个解?都为非负整数
    回答: 那么运用公式就是C(3+11-1,11) = 78种;

  • 方程x1+x2+x3+x4+x5=21有多少解?其中Xi(>2)(i=1,2,3,4,5)是非负整数。
    回答:这个题可以翻译成这样一个问题:在五个不同的盒子里放置21个相同的球有多少种方法,每个盒子至少有两个球。C(21-5×2+5-1,21-5×2)= C(15,11)= 15! / ( 11!4!)=1365种得到;可能有同学不理解括号中的21-5×2+5-1的意义,我们对比公式可以知道重复的个数,我们是先把至少两个的已经放了,那么就放了2×5个素了,重复的个数也变成了21-10=11种,那么再代入公式得到C(11+5-1,11)了,也就是C(15,11)=1365种了。

  • 在下面伪代码被执行之后,k的值会是多少?

k=0; for(i1 = 1;i1 <= n;i1++) { 
    for( i2 = 1; i2 <= i1;i2++) { 
    for(i3 = 1;i3 <= i2;i3++) { 
    for( i4 = 1; i4 <= i3;i4++) { 
    .... for( im = 1;im <= i(m-1);im++) k = k+1; } } } } 

回答:这道题其实还蛮好理解的,相当于{1,2,3…n}的一个序列,里面的素都是允许重复选择m个的整数,即C(m+n-1,m),那么因为每次k++,那么k=C(m+n-1,m)+0;

上面的都是可重复的组合,下面看看不可区别物体的集合

  • 重新排列单词sucess中的字母能构成多少个不同的串?
    回答:首先里面只有4中字符,那么组合的方式应该是C(7,3)*C(4,2)*C(2,1)*C(1,1)=420种;
    从中可以得到一个规律认识:假设物种1有a个,物种2有b个,物种3有c个…,物种k有z个,那么n个物体排列数是n! / (a! b! c!..z!)种

可分辨的物体与可分辨的盒子

  • 把52张牌分给五个人,每人四张,有多少种方式?
    回答:可以当作五个位置,每个位置放四个,那么就是C(52,4)C(48,4)C(44,4)C(40,4)C(36,4)种方式;

可分辨的物体与不可分辨的盒子

  • 把四个不同的雇员安排在三件不可分辨的办公室有几种方式?
    回答:14种;

不可分辨的物体与可分辨的盒子

  • 将5个不可分辨的西瓜放入2个可分辨的篮子里,有几种方式?
    回答:C(5+2-1,5)种;此处的不可分辨的物体可当作重复的素的个数理解;

不可分辨的物体与不可分辨的盒子

  • 将6个无差异的鸡蛋放入4个无差异篮子里,有几种方式?
    回答:
6
5,1
4,1,1
4,2
3,2,1
2,2,1,1
2,2,2
3,3
3,1,1,1

一共9种;

2024最新激活全家桶教程,稳定运行到2099年,请移步至置顶文章:https://sigusoft.com/99576.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请联系我们举报,一经查实,本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处:https://sigusoft.com/161850.html

(0)
上一篇 2024年 7月 5日 下午6:43
下一篇 2024年 7月 5日 下午6:51

相关推荐

关注微信