vbscript insert EaselJS vue请求 android开发项目 php项目实战 oracle数据库版本 python刷题 mysql组合索引 python学习 mysql教程 python断言assert实例 python多线程编程 python在线教程 python正则匹配 python正则匹配空格 java接口 java自学教程 java有哪些数据类型 java网页 linux启动 linuxsudo命令 局域网助手 vs2010sp1 iphone滚动截屏 maxtoc4d java核心技术 谷歌地球用不了 c4dr19 tableau下载 明解c语言 ppt格式刷怎么用 windowsjs延时函数 网红照片男 linux解压命令 vc运行库合集 上单艾克出装 cad圆变成多边形 3dmax布尔运算 php定时任务
当前位置: 首页 > 学习教程  > 编程语言

组合数学(研讨)——前言笔记

2021/3/2 23:59:31 文章标签:

前言 组合数学是一门计算机专业的基础理论课。那它究竟学啥呢?其课程主要内容有:排列与组合、鸽巢原理、生成排列和组合、二项式系数、容斥原理、图论。里面肯定有很熟悉的内容,举个小栗子:鸽巢原理也许有点陌生,那它的…

前言

 组合数学是一门计算机专业的基础理论课。
 那它究竟学啥呢?
 其课程主要内容有:
     排列与组合、鸽巢原理、生成排列和组合、二项式系数、容斥原理、图论。
 里面肯定有很熟悉的内容,举个小栗子:
    鸽巢原理也许有点陌生,那它的别名——抽屉原理呢,把n+1个物体放入n个盒子里,则至少有一个盒子里含有两个或两个以上的物体,
 这么一说就熟悉了一些,当然如果说成是Ramsey定理的特例,那又模糊了,Ramsey定理又是啥,还是看下面的学习吧。
参考书又是一本黑面书,贵滴滴:

在这里插入图片描述

组合数学的发展历史在这里插入图片描述二项式系数

杨辉三角----二项式系数

在这里插入图片描述

组合数学的例子

一. 棋盘的完美覆盖

在这里插入图片描述上面的8×8棋盘例子,可见必然存在完美覆盖,
设棋盘的方格个数为n,
假如n=1,显然这个问题无解,n=3,这个问题也无解,其实这是个简单的逻辑,一个多米诺牌需要占两个方格,也就是说方格总数必须是2的倍数,也就是说n必须是偶数。
首先看一下3*2的棋盘有多少种排列组合方式?
如下图所示。

(1)在这里插入图片描述(2)在这里插入图片描述(3)是(2)上下颠倒的图形。
一共就以上三种排列方式。
接着我们看一下3×4的棋盘有多少种排列方式?除了可以分为两个3×2外,还有可能如下图所示。
在这里插入图片描述注意这也是两种。(上下颠倒)
由此可见,有3×3+2=11种排列方式。
……

啊啊啊啊啊,我半途放弃了,这个8×8的结果12988816,鬼鬼,我一时还是没研究出来,当然百度了下还没找到,但愿我之后还有时间抽空看一下,原谅我~

而扩展到m×n棋盘呢?此时它的完美覆盖不一定存在,满足什么条件才一定存在完美覆盖呢?不难看出,当且仅当m和n中至少有一个是偶数,等价说成这个棋盘的方格数为偶数时。
在这里插入图片描述把一个棋盘随意剪去一些方格,得到的是一张“残缺棋盘”。那么,关于残缺棋盘的覆盖问题又怎么样呢?
在这里插入图片描述这样分析:每一张骨牌覆盖相邻的两个方格,那么就假设棋盘是黑白相间的,呈现这样的场景:
在这里插入图片描述去掉的两个方格必然是相同的颜色,于是原来32张黑色和32张白色变成了32黑色(白色),30白色(黑色)。
如果31张骨诺牌能够完美覆盖,那么就产生了这样的关系式: 31(black+white)=32black+30white[or: 32white+30black],这显然是不成立的。
在这里插入图片描述所以一种完美覆盖都不存在。
那是否棋盘具有相同的黑方格数和白方格数,就存在完美覆盖呢?下面这个反例给出答案。
在这里插入图片描述拓展
如果棋盘的规格是m×n,且一张牌的长度是b(称作b格牌),那么这样的棋盘能够被b格牌完美覆盖吗?
在这里插入图片描述显然,想要完美覆盖,b必然是m×n的因子,这就是充分条件:b是m或者n的因子(联系实际)。事实上,有这样的结论:m×n的棋盘有b格牌的完美覆盖当且仅当b是m或者n的一个因子。
下面证明它为必要条件
已知bk=mn,这里重点是分类讨论b

  1. 当b是质数时,显然b或者是m的一个因子或者是n的一个因子。
  2. 当b是合数时,设m和n除以b时的商和余数分别为p,q,r,s,则:m=pb+r(0<=r<=b-1),n=qb+s(0<=s<=b-1)
    通过交换棋盘的行和列,不妨设r<=s,下证r=0。
    我们将棋盘进行染色,用1~b的颜料,相邻两个格子颜色不同。
    完美覆盖的每一张b格牌覆盖b个方格且每一个方格覆盖一种颜色。因此,在棋盘上每一种颜色的方格数一定相同。
    我们将一个棋盘分为三个部分:上方pb×n部分,左下方r×qb部分和右下方r×s部分。
    在上方部分,每一列上每一种颜色出现p次,所以总共出现pn次。
    同理,在左下方部分,每一行上,因为每一种颜色出现q次,因此它们总共出现rq次。
    因此在左上方和上方每一种颜色出现的次数相同。结合前文中“因此,在棋盘上每一种颜色的方格数一定相同。”得到右下方每种颜色出现次数也相同,即r×s=r×b,得到b=s,与前文“(0<=s<=b-1)”矛盾,证毕。在这里插入图片描述
二. 幻方

在这里插入图片描述

n=2时,不存在幻方。

在这里插入图片描述

用这个方法构造如下5阶幻方:

17241815
23571416
46132022
101219213
11182529
三. 36军官问题

大数学家欧拉曾提出一个问题:即从不同的6个军团各选6种不同军阶的6名军官共36人,排成一个6行6列的方队,使得各行各列的6名军官恰好来自不同的军团而且军阶各不相同,应如何排这个方队?如果用(1,1)表示来自第一个军团具有第一种军阶的军官,用(1,2)表示来自第一个军团具有第二种军阶的军官,用(6,6)表示来自第六个军团具有第六种军阶的军官,则欧拉的问题就是如何将这36个数对排成方阵,使得每行每列的数无论从第一个数看还是从第二个数看,都恰好是由1、2、3、4、5、6组成。历史上称这个问题为三十六军官问题。

在这里插入图片描述

解决:
三十六军官问题提出后,很长一段时间没有得到解决,直到20世纪初才被证明这样的方队是排不起来的。尽管很容易将三十六军官问题中的军团数和军阶数推广到一般的n的情况,而相应的满足条件的方队被称为n阶欧拉方
欧拉曾猜测:对任何非负整数t,n=4t+2阶欧拉方都不存在。
t=1时,这就是三十六军官问题,而t=2时,n=10,数学家们构造出了10阶欧拉方,这说明欧拉猜想不对。
但到1960年,数学家们彻底解决了这个问题,证明了n=4t+2(t≥2)阶欧拉方都是存在的。

这种方阵在近代组合数学中称为正交拉丁方,它在工农业生产和科学实验方面有广泛的应用。现已经证明,除了2阶6阶以外,其它各阶3,4,5,7,8,……各阶正交拉丁方都是作得出来的。
举例:
3阶:
(1,1) (2,2) (3,3)
(2,3) (3,1) (1,2)
(3,2) (1,3) (2,1)
4阶:
(2,1) (4,4) (3,2) (1,3)
(4,2) (2,3) (1,1) (3,4)
(3,3) (1,2) (2,4) (4,1)
(1,4) (3,1) (4,3) (2,2)
5阶:
(1,1) (2,2) (3,5) (4,3) (5,4)
(4,5) (1,3) (5,2) (3,4) (2,1)
(2,4) (5,5) (4,1) (1,2) (3,3)
(5,3) (3,1) (1,4) (2,5) (4,2)
(3,2) (4,4) (2,3) (5,1) (1,5)

在这里插入图片描述

四. 最短路径问题

在这里插入图片描述

什么是组合数学

在这里插入图片描述

组合数学的研究工具

在这里插入图片描述

小结

在这里插入图片描述


本文链接: http://www.dtmao.cc/news_show_758628.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?