【貌似是组合数学】求有多少组合方式以及列举

  1. 3月前

    原发数学吧。


    设有四个数a0, a1, a2, a3, 其中a0=0. 如果按照角标序号存在这样的关系:两相邻数(后数减前数)间相差的数只能为Δa=2,3,4,5,7,并且任意两数的差值除以12的余数不能为1,6,11, 那么一共有几种可能的组合方式?应该怎么列举出它们?
    如果有5个数,那么可能的组合方式是多少?


    这个问题编程来解并不困难,实际上是个分叉的树状模式,先填a1然后a2等等;由于总数n=4并不太大,人工列举也是可以做到的。
    穷举的话我们知道先考虑Δa一共125种,检验并划去所有不符合条件的即可。
    如果对于n=5,那么有625种,数量大了些,人工列举并不容易,但是看起来可以根据n=4的条件递推。事实上n=2五种,n=3手动列举有20种,递推出来n=4有65种,楼主动手列的不保证没有漏的。


    我想问的是如果非编程不穷举的话,是否有办法迅速得出种类数量?这是不是跟马尔科夫链有关系。
    或者是否从n=2,3的时候建立归纳假设来递推?

  2. @FatFish
    看起来实际数量的增长速度远不及最大可能数量的增长速度:
    实际数量n增长1常常对应翻=<4倍,但是最大可能数量直接就以5^n来增长。
    不知道能否求出一个n对应数量的增长公式。

 

后才能发言