计数n元变量F-算术表达式的复杂度与算法研究

《Discrete Applied Mathematics》：On the number of F-arithmetic expressions in n distinct variables

本文研究在任意域F上，由n个不同变量构成的算术表达式的计数问题。作者提出了一种时间复杂度为Θ(n2)的算法，解决了先前由Du (2008)和Radcliffe (2012)分别提出的两个核心问题，并扩展了已有工作[9]的结果。该算法不仅能处理实数域上的情况，而且适用于任意特征（包括特征为2）的域F。文章通过系统地定义表达式树(expression tree)和F-算术表达式(F-arithmetic expression)为F(X)中的元素，引入和类型(sum-type)与积类型(product-type)等概念，并利用形式偏导数(formal partial derivatives)和组合论证，推导出递推关系。最终，基于动态规划(Dynamic Programming)设计出高效的算法，并用C++17实现[10]。该工作从算法复杂度和代数结构两个层面，为算术表达式的计数提供了统一的解决方案。

　　

Highlight 部分暂缺。根据全文内容，以下是相关部分的翻译：

组合恒等式

如已提及，对于任意特征为2的域F，加法求逆(additive inversion)不改变结果，而减法(subtraction)的表现与加法相同。这引出了下一个观察结果。

命题 3.1

设F是任意满足特征char(F)=2的域，且n∈N。则对于每个β∈{OM, MD, MI}，均有c_n(F; OA, β) = c_n(F; AS, β) = c_n(F; AI, β)。

因此，对于特征为2的域F，问题1.3归结为计算所有n∈N对应的c_n(F; OA, OM)、c_n(F; OA, MD)和c_n(F; OA, MI)。在本节中，我们研究了...

和类型与积类型表达式

在本节中，我们研究任意域F上F-算术表达式的结构分解性质。考虑一个F-算术表达式f及其树表示T。我们可以通过将每个减法节点移除并替换为一个加法节点及一个加法求逆节点来修改T。类似地，也可以对所有除法节点进行修改，从而得到表达式树T₁。现在，由于对于任意F-算术表达式f和g，有-(f+g) = (-f)+(-g)、-(fg) = (-f)g 且 -(1/f) = 1/(-f)，因此...

算法概览

在本节中，我们推广了[9, 第4节]中提出的算法，以计算在1.1节所述的(α, β)约束条件下（排除α=NA或β=NM的平凡情况）的F-算术表达式的数量。总共有九种情况。利用命题3.1和定理3.2，我们可以将问题进一步简化为六种情况：当α∈{OA, AI}且β∈{OM, MD, MI}时。此外，当α=AI时，我们可以假设char(F)≠2。

在继续之前，我们扩展了Π₂-型和Π₁-型的定义...

结论

在第3节中，我们证明了对于任意特征char(F)≠2的域F，表2中的解满足第二行和第三行相加等于第四行的性质。此外，我们还证明了，可以在不使用减法或加法求逆的情况下获得的F-算术表达式的加法逆元，正是那些无法在不使用加法求逆的情况下获得的F-算术表达式。

第4节扩展了[9]的结果，表明乘法求逆...