Sun, 27th October 2019Edit on Githubalgorithmanalytic combination
2008年5月KeyTo9_Fans等在百度数学吧讨论由算24问题派生出来的计数问题,就是将n个不同的数字通过加减乘除运算(可以改变数字顺序和添加括号)连接起来 可以产生多少个不等价的表达式。其中比如(a+b)+c+d和a+(b+c)+d等价,因为可以通过我们熟悉的交换律分配率或结合律等相互转化。
mathe和KeyTo9_Fans共同出手并相互验证,最后mathe抢先得出n=100时,总共有 449917517701763281317016679046006077977987086161265203561131799463636866125482192454546567903120426734284631438483334078738257721979009093443435909627076270897944886935144957288232557564081388424946360387439835357455680511571869059290 个不等价的表达式。
由于百度贴吧信息都已经丢失,我们只能在数学研发论坛找到部分还保留的信息,这里基本上只包含了mathe给出的信息,而没有KeyTo9_Fans的信息。
mathe给出了如下的算法的思路
关于这个题目,用五个数字情况作为例子,比如现在有一个表达式
这个表达时最外层计算是加减计算,而且,我们发现可以通过去掉部分括号将其他一些加减也提升到最外层,比如上面表达式可以写成:
在这些括号去除以后,我们可以发现,所有在最外层的加减计算都是可以交换计算顺序的,比如上面这个表达式同下面几个都等价:
所以如果允许第一个数字前面也添加正负号,那么所有最外层计算中,我们只需要考虑每一项的符号,而不用管它们的顺序。
而如果需要考虑第一项不允许添加负号,由于各项之间顺序可以任意安排,所以只要至少有一项是正的,我们就可以表达出来。
所以像上面的表达式,我们可以看成分组
里面,每一组都添加正号或负号然后求和的所有可能,其中不允许所有的都选择负号。
所以上面分组用加减号连接最多有15种不同的可能
同样,如果表达式最外层运算是乘除运算,我们考虑表达式
同样,我们可以把它改写成
类似前面,我们把这个表达式看成分组
通过乘除运算组合到一起中的一种,组合过程中,每个数可以选择用作乘数或除数,但是不能够所有的数都选择为除数。
所以上面的分组用乘除号连接最多有种不同的连接方式.
现在我们来看第三种特殊的表达式
这个表达式同
也是等价的,但是这种等价关系前面的分析过程无法得出,主要原因在于对于某个连乘式:
和
如果两个连乘式中对应项绝对值都相同,那么最后乘积也必然相等或互为相反数。
所以我们需要对所有结果为互为相反数的项做特殊处理:
可以发现,对于一个分组的加减组合中我们允许第一项也添加负号,那么对于每个表达式,我们总可以找到和它互为相反数的一项。
所以我们可一将互为相反数的项看成等价的表达式,最后计算出总数目,然后在总数目上乘2就可以了(因为对于最后的表达式,也是每个表达式,其相反数必然可以构造出来)
而对于最终的表达式,如果它的相反数不能表示出来(不允许第一项添加负号的情况下),容易看出,只能表达式中没有用过减号。
所以我们可以通过分别计数情况1:第一项允许添加负号;情况2:没有使用任何负号的表达式。
利用上面算法在2008年5月19日mathe将结果计算到100余项并将结果提交到了A140606。
2018年8月Zhujun Zhang使用解析组合得出更好的算法,将结果更新到了300项,比如第三百项是
72190028147018889750335485131328303931152274582550236089525162409795374552101273176794454983868785962708688202710181198684352866146727661739564511680864977514566139496879769349359289549566028996044476516485895050609304963244258584965660688879810583890530231617438520357138548072805455108020217067359180748422323864413955769641649473209885524803873657901023082852855074512602102118234803504483350613423240988997188280088539348565629602280338815644982671693200891519489372327809082142923858939068708053619624995070063973108938476056358131172343896608014407677212410031033341157688603637733542123642865148016593343643219416232187380709150093319011151323845637138861981383252936745634980311080707083425397147421602918476666397675833977564301679029137943021579679971179004749690773848817257553051528298367371360988489078773939477280125867271746491441210
所以合适的算法很重要,而合适的数学方法能显示更加强大的威力。