<h2>第i条线的多项式系数与第(i-1)条线的系数之间的关系</h2>
<p>在上一篇文章中,计算了<code>c[i][j]</code>。可以检查<code>deg(c[i][j])=j+1</code></p>
<p>这可以通过初始化一个单独的2d数组并按如下方式计算度来检查:</p>
<p><code>deg[i][j] = degree(poly(parse_expr(str(charar[i][j]))))</code></p>
<p>垂直公式:</p>
<p>然后,如果我们用<code>u(i,j,k)</code>表示<code>x^k</code>在<code>c[i][j]</code>中的系数,我们可以尝试找到<code>u(i,j,k)</code>在<code>u(i-1,_,_)</code>中的公式。<code>u(i,j,_)</code>的公式将与<code>u(i+1,j,_)</code>(以及以下所有行)的公式相同,因此有一些缓存的机会</p>
<p>水平公式:</p>
<p>有趣的是,当我们修正<code>i</code>时,发现<code>u(i,j,_)</code>的公式看起来与<code>u(i,j+1,_)</code>的公式一样,除了k的最后3个值。但我不确定这是否可以利用</p>
<p>上面提到的缓存步骤可能有助于跳过不必要的计算</p>
<p>请参阅更多<a href="https://github.com/wsdookadr/so/blob/master/so-65707040/recurrence-coeffs.ipynb" rel="nofollow noreferrer">about this here</a></p>
<h2>关于解析、闭式解和渐近性的一些注记</h2>
<blockquote>
<p>I'm struggling to derive this analytically</p>
</blockquote>
<p>是的,这似乎很难。与这里提到的递归序列相关的最接近的一类被称为<a href="https://en.wikipedia.org/wiki/Holonomic_function#Definitions" rel="nofollow noreferrer">Holonomic sequences</a>(也称为D-有限或<a href="https://en.wikipedia.org/wiki/P-recursive_equation" rel="nofollow noreferrer">P-recursive</a>)。序列<code>c[i][j]</code>不是<a href="https://en.wikipedia.org/wiki/Constant-recursive_sequence" rel="nofollow noreferrer">C-finite</a>,因为它具有多项式系数(在一般情况下,甚至多项式系数的递归的渐近性也是<a href="https://mathoverflow.net/q/223422/112768">an open problem</a>)</p>
<p>但是<code>c[i][j]</code>的递归关系不符合此条件,因为存在导数。如果我们在<code>c[i][j]</code>公式中省略导数,那么它将符合完整序列的条件。以下是我找到这些解决方案的一些地方:</p>
<ol>
<li><a href="https://rads.stackoverflow.com/amzn/click/com/3709104440" rel="nofollow noreferrer">"The Concrete Tetrahedron: Symbolic Sums, Recurrence Equations, Generating Functions, Asymptotic Estimates" by Kauers and Paule</a>-第7章完整序列和幂级数</li>
<li><a href="https://ac.cs.princeton.edu/home/AC.pdf" rel="nofollow noreferrer">Analytic Combinatorics by Flajolet and Sedgewick</a>-附录B.4完整函数</li>
</ol>
<p>但是{<cd1>}也是一个多变量递归,所以这是它不符合上述理论的另一个原因</p>
<p>然而,还有一本书叫做<a href="https://acsvproject.com/ACSVbook.html" rel="nofollow noreferrer">Analytic Combinatorics in Several Variables by Robin Pemantle and Mark C. Wilson</a>,它确实处理了几个变量的重复出现</p>
<p>上面提到的所有书籍都需要很多复杂的分析,它们远远超出了我目前所知道的小数学,所以希望对这类数学有更深入理解的人可以尝试一下</p>
<p>具有生成函数相关操作并可以对此类序列进行操作的最高级CA是<a href="https://www.maplesoft.com/" rel="nofollow noreferrer">Maple</a>和<a href="http://perso.ens-lyon.fr/bruno.salvy/software/the-gfun-package/" rel="nofollow noreferrer">gfun package</a>{a11}(目前仅处理单变量情况)</p>