组合数学1-漫谈组合数学
循环棋盘，第一排正中间放1，放右上角，如果已经有数字，放于正下方 多少种构造方法？ 变形幻方：素数，数列，相乘 由数字1,2,3,4,5可以构成多少个四位数？要求四位数的所有数字都不相同。P(5,4)=5x4x3x2=120 某场大型比赛中共有569个参赛者，如果进行单场淘汰赛，直至决出冠军，请问一共要进行多少场比赛？568 每场比赛淘汰一个人，一共需要淘汰n-1人 在中国古代，有五行相克之说。五行即金、木、水、火、土。而相克是金克木、木克土、土克水、水克火、火克金。从五行中找出互不相克的两行，共有几种不同选法？ （金，土），（金，水），（木，水），（木，火），（土，火）一共五种 如下图所示的六桥问题一共有多少种不重复遍历6座桥的走法？ 从1出发回到4有16种： a-b-c-f-d-e a-b-c-f-e-d a-b-d-e-c-f a-b-d-f-c-e a-b-e-d-c-f a-b-e-f-c-d c-b-a-f-d-e c-b-a-f-e-d c-d-e-b-a-f c-d-f-a-b-e c-e-d-b-a-f c-e-f-a-b-d f-d-c-a-b-e f-d-b-a-c-e f-e-b-a-c-d f-e-c-a-b-d 同理，从4出发回到1也有16种走法，请大家一一枚举。 下图是一个部分4X4方阵，能否在此基础上构造出来一个由数字1-16构成的4阶幻方？ 假设可以构造出来一个如下4阶幻方： 则1≤a,b,c,d,e,f,g,h,i,j,k≤16且a,b,c,d,e,f,g,h,i,j,k互不相等 4阶幻和为34 将第一行和第一列分别相加得： 2+3+a+b=34 2+4+f+i=34 于是有： a+b=29 f+i=28 哪些数字作为幻和，可以构造出由不重复的 正整数 构成的三阶幻方？18 先构造一个三阶幻方： 假设幻和为k,有： 三个式子相加得到： M1+M2+M3+3M5+M7+M8+M9=3k 又有： M1+M2+M3=k M7+M8+M9=k 将上面两个式子代入（1）化简得到：M5=k/3 构造幻和为3的倍数的幻方方法： 设k=3 (5+m)，m>=0，那么任取一个三阶幻方，将其中每个数加上m，即可形成幻和。 题中18=3 (5+1)，即三阶幻方每个元素加1即可。 （减1为12） 其他幻方： 确定一个唯一的四阶幻方至少需要知道其中几个数字? https://zhidao.baidu.com/question/561002163716082204.html 四组任意的数，只要每组的四个数相互之间的差值都相同，就可以组成四阶 幻方 。如以下四组数 【A、A+x、A+y、A+z】、 【B、B+x、B+y、B+z】、 【C、C+x、C+y、C+z】、 【D、D+x、D+y、D+z】、 幻和值=A+B+C+D+x+y+z 所以，要确定一个唯一的四阶至少需要知道7个数。 三阶幻方 世界级的幻方问题 http://blog.sina.com.cn/s/blog_44bcb6a50102vjzn.html 欧拉的六桥问题 基础的组合问题（画图） https://baijiahao.baidu.com/s?id=1660850310258445979&wfr=spider&for=pc 总结：老师讲的这些变式问题都很有趣，练习题也很有意思，还额外去查了很多资料，不过本来想听英文的，结果连字幕都是英文，又是陌生的知识，我怂了，看回中文的了。
组合数学
组合数学是离散数学的一个分支。专门研究计数的问题。 一个N*N的方格，是否存在组合 无论每行的和，每列的和，对角线的和都相等？ 一个数n，到底存在多少个不同的幻方？ 据不完全统计 如果全世界有224个队伍参加比赛，两两组合进行直接淘汰赛，那么一共需要进行多少场比赛可以决出冠军？ 答案是：224-1 因为没进行异常两两组合的比赛，会淘汰1个队伍，那么要决出冠军，需要淘汰224-1只队伍，所以答案可以直接给出223 路径数为C(m + n, n) 从(0, 0)到(m, n)只能向右和向上走，一共走m + n步，要向右走m步，向上走n步。 那么就排列成一个xyx....xxyy的一个组合 那么问题就规约为m + n的位置上，选择m个位置作为x（向右走），那么就可以得出组合的计数 从n个不相同的元素取r个排成一个圆，的排列数为P(n, r)/r n个不同的乒乓球，进入r个洞的的方案数 P(n + r, n + r)/ r! x1 + x2 + ... xn = b 的正整数解的个数为C(n + b -1, b) 从{1, 2, .. n}取出r个不相邻的数 问题归约为从1到n - r个数取r个数的问题 所以计数为C(n - r - 1, r) 再计算n!的时候，当n足够大后，计算n!将会相当困难 一个函数： 如果关注的是x的解，那么G(x)是一个函数 如果关注的是c0, c1...的序列，那么G(x)就是一个母函数 可得x的5次方系数为2 所以是两种 计算出x的n次方的系数 则为计数的答案 如果直到母函数G(x)的表达式 通过对G(x)化简，对每一个单项进行泰勒展开式分解，可以得到任意复杂的序列C(n) 假设有以下序列的递推关系，并构造母函数，有 通过化简，可得 通过泰勒展开得 通过母函数的定义可知 Ck为x的k次方的组合数 而P(n, k) = Ck * k! 因此，如果要利用母函数计算x的k次方的排列数 则为 如果有n-1个抽屉，有n个球，那么至少有一个抽屉有至少两个球 pendig
