Question

组合数学

Answer 1

组合数学是离散数学的一个分支。专门研究计数的问题。

一个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