【读书笔记】有序分拆和无序分拆的结论速览

2021/6/6 10:32:18

本文主要是介绍【读书笔记】有序分拆和无序分拆的结论速览,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

目录
  • EXAMPLE I.4. Compositions with restricted summands
  • EXAMPLE I.5. Partitions with restricted summands (硬币找零问题)
  • EXAMPLE I.6. Compositions with a fixed number of parts.
  • EXAMPLE I.7. Partitions with a fixed number of parts
  • 结论表格
  • 最后还有一些
  • SEE ALSO





composition是带序的分拆(不允许和数有0)
partition 是不带序的分拆(不允许和数有0)
Cyclic compositions (wheels)是说有序分拆,然后做个圆排列
Partitions into distinct summands. 字面意思

主要的研究方法是:

由组合对象间的关系推出或者直接写出OGF

然后如果好反演的话找到通项公式\(a_n=[z^n]f(z)\),不好反演就算了

接着通项简单的话直接分析渐进性质,否则用分析方法研究\(f(z)\)得到\(a_n\)的渐进性质

upd 2021-03-29 今天读了Stanley的《计数组合学·第一卷》第一章的开始的部分,里面提到了如何计数有如下的几种常见方法:
1.如果简单,直接写出显式公式
2.写出递推式和边界条件,也可以算是得到了可靠的结果
3.给出它关于变量的渐进估计
4.用生成函数描述





EXAMPLE I.4. Compositions with restricted summands

image-20200727154615753

image-20200727154625418

EXAMPLE I.5. Partitions with restricted summands (硬币找零问题)

(32)这里按我的想法解释的话,展开是\((1+x+x^2+...)(1+x^2+x^4+x^6+...)(1+x^3+x^6+x^9+...)...(1+x^r+x^{2r}+x^{3r}+...)\)
你第一个括号里拿的是\(x^4\),说明你的分拆里有4个1;...;你最后一个括号里拿的是\(x^{2r}\),说明你的分拆里有2个r
image-20200727155213049

EXAMPLE I.6. Compositions with a fixed number of parts.

image-20200727155454202

EXAMPLE I.7. Partitions with a fixed number of parts

image-20200727160002664

image-20200727160030610

结论表格

提醒一下,那个无限制的Composition个数是\(2^{n-1}\),智力题,想象\(n-1\)个隔板。拿mma求解可以用Combinatorica程序包里的Compositions函数
提醒一下,那个n的k部分Partition个数是\([z^n]z^k \prod\limits_{m=1}^{k}(1-z^m)^{-1}\)。mma代码就是IntegerPartitions[2010, {3}];Length@%
提醒一下,如果记\(p(n,k)\)是n的k部分的partition的方案个数,那么有\(p(n,k)=p(n-1,k-1)+p(n-k,k)\).证明是考虑最小的那个和数,如果是1对应于\(p(n-1,k-1)\)这一项,如果>1对应于\(p(n-k,k)\)这一项.更详细的解释看这个帖子。

最后还有一些

image-20200727162601859
I.14写成显式公式就是

\[\sum_{j}(-1)^{j}\left(\begin{array}{l} k \\ j \end{array}\right)\left(\begin{array}{c} n-r j-1 \\ k-1 \end{array}\right) \]

I.15用q-analogue很容易理解,可以看我写过的这篇文章

SEE ALSO

Restricted Weighted Integer Compositions and Extended Binomial Coefficients
Compositions of n with parts in a set




书用的是Analytic Combinatorics

资料来自网络



这篇关于【读书笔记】有序分拆和无序分拆的结论速览的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程