本文主要是介绍4月16日学习笔记 组合数学数论，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1.现由一个问题引入：N个人坐在和自己编号不同的座位上问有多少种坐法？
这是一个错排问题。首先简单介绍错排
当n个编号元素放在n个编号位置，元素编号与位置编号各不对应的方法数用D(n)表示，那么D(n-1)就表示n-1个编号元素放在n-1个编号位置，各不对应的方法数，其它类推.
第一步，把第n个元素放在一个位置，比如位置k，一共有n-1种方法；
第二步，放编号为k的元素，这时有两种情况：⑴把它放到位置n，那么，对于剩下的n-1个元素，由于第k个元素放到了位置n，剩下n-2个元素就有D(n-2)种方法；⑵第k个元素不把它放到位置n，这时，对于这n-1个元素，有D(n-1)种方法；
综上得到
D(n) = (n-1) [D(n-2) + D(n-1)]
特殊地，D(1) = 0, D(2) = 1.
这样我们就可以用递归求D(n)了。。。。、
2,由12个不同颜色的珠子串成一条项链，能够有多少种不同的项链？
解：12个珠子排成一列 有12！种
除去移位的重复得12！/12；
除去翻转得12！/12/2 就是最终结果
3，Catalan数
一个 栈(无穷大)的 进栈序列为1，2，3，…，n，有多少个不同的 出栈序列? [4-5]
常规分析
首先，我们设f（n）=序列个数为n的出栈序列种数。同时，我们假定，从开始到栈第一次出到空为止，这段过程中出栈的序数最大的是k。特别地，如果栈直到整个过程结束时才空，则k=n
首次出空之前第一个出栈的序数k将1~n的序列分成两个序列，其中一个是1~k-1，序列个数为k-1，另外一个是k+1~n，序列个数是n-k。
此时，我们若把k视为确定一个序数，那么根据 乘法原理，f（n）的问题就等价于——序列个数为k-1的出栈序列种数乘以序列个数为n - k的出栈序列种数，即选择k这个序数的f（n）=f（k-1）×f（n-k）。而k可以选1到n，所以再根据 加法原理，将k取不同值的序列种数相加，得到的总序列种数为：f（n）=f（0）f（n-1）+f（1）f（n-2）+……+f（n-1）f（0）。
看到此处，再看看卡特兰数的递推式，答案不言而喻，即为f（n）=h（n）= C（2n,n）/（n+1）= c（2n,n）-c（2n,n+1）（n=0，1，2，……）。
最后，令f（0）=1，f（1）=1。
待续。。。
这篇关于4月16日学习笔记 组合数学数论的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
