加减乘除产生的表达式计数

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给出了如下的算法的思路

关于这个题目,用五个数字情况作为例子,比如现在有一个表达式
a(b×c(d+e))a-(b\times c-(d+e))
这个表达时最外层计算是加减计算,而且,我们发现可以通过去掉部分括号将其他一些加减也提升到最外层,比如上面表达式可以写成:
ab×c+d+ea-b\times c+d+e
在这些括号去除以后,我们可以发现,所有在最外层的加减计算都是可以交换计算顺序的,比如上面这个表达式同下面几个都等价:
a+d+eb×ca+d+e-b\times c
b×c+a+d+e-b\times c+a+d+e
所以如果允许第一个数字前面也添加正负号,那么所有最外层计算中,我们只需要考虑每一项的符号,而不用管它们的顺序。
而如果需要考虑第一项不允许添加负号,由于各项之间顺序可以任意安排,所以只要至少有一项是正的,我们就可以表达出来。
所以像上面的表达式,我们可以看成分组
(b×c,a,d,e)(b\times c, a, d, e)
里面,每一组都添加正号或负号然后求和的所有可能,其中不允许所有的都选择负号。
所以上面分组用加减号连接最多有15种不同的可能2412^4-1

同样,如果表达式最外层运算是乘除运算,我们考虑表达式
ab+cd×e\frac{\frac{a}{b+c}}{d\times e} 同样,我们可以把它改写成 a(b+c)×d×e\frac{a}{(b+c)\times d\times e} 类似前面,我们把这个表达式看成分组
(a,b+c,d,e)(a, b+c, d, e)
通过乘除运算组合到一起中的一种,组合过程中,每个数可以选择用作乘数或除数,但是不能够所有的数都选择为除数。 所以上面的分组用乘除号连接最多有2412^4-1种不同的连接方式.

现在我们来看第三种特殊的表达式
a(bc)+d×e\frac{a}{(b-c)}+d\times e 这个表达式同
d×eacbd\times e-\frac{a}{c-b}
也是等价的,但是这种等价关系前面的分析过程无法得出,主要原因在于对于某个连乘式:
x1x2..xtx_1x_2..x_ty1y2...yty_1y_2...y_t
如果两个连乘式中对应项绝对值都相同,那么最后乘积也必然相等或互为相反数。

所以我们需要对所有结果为互为相反数的项做特殊处理:
可以发现,对于一个分组的加减组合中我们允许第一项也添加负号,那么对于每个表达式,我们总可以找到和它互为相反数的一项。
所以我们可一将互为相反数的项看成等价的表达式,最后计算出总数目,然后在总数目上乘2就可以了(因为对于最后的表达式,也是每个表达式,其相反数必然可以构造出来) 而对于最终的表达式,如果它的相反数不能表示出来(不允许第一项添加负号的情况下),容易看出,只能表达式中没有用过减号。 所以我们可以通过分别计数情况1:第一项允许添加负号;情况2:没有使用任何负号的表达式。

利用上面算法在2008年5月19日mathe将结果计算到100余项并将结果提交到了A140606

2018年8月Zhujun Zhang使用解析组合得出更好的算法,将结果更新到了300项,比如第三百项是

72190028147018889750335485131328303931152274582550236089525162409795374552101273176794454983868785962708688202710181198684352866146727661739564511680864977514566139496879769349359289549566028996044476516485895050609304963244258584965660688879810583890530231617438520357138548072805455108020217067359180748422323864413955769641649473209885524803873657901023082852855074512602102118234803504483350613423240988997188280088539348565629602280338815644982671693200891519489372327809082142923858939068708053619624995070063973108938476056358131172343896608014407677212410031033341157688603637733542123642865148016593343643219416232187380709150093319011151323845637138861981383252936745634980311080707083425397147421602918476666397675833977564301679029137943021579679971179004749690773848817257553051528298367371360988489078773939477280125867271746491441210

所以合适的算法很重要,而合适的数学方法能显示更加强大的威力。

Github