答えを\(f(n)\)としたとき、以下の形式的べき級数を考えましょう。

\[\sum_{n=0}^{\infty}f(n)x^n\]

ただし、便宜上\(f(0)=0\)とします。

以下のように級数を定めます。

• \(A(x)\)：\(x^N\)の係数が「文字数が\(N\)であって、1-9が使えるときの式全ての答えの総和」であるような級数

• \(B(x)\)：\(x^N\)の係数が「文字数が\(N\)であって、1-9と*が使えるときの式全ての答えの総和」であるような級数

• \(C(x)\)：\(x^N\)の係数が「文字数が\(N\)であって、1-9と*と+が使えるときの式全ての答えの総和」であるような級数

• \(D(x)\)：\(x^N\)の係数が「文字数が\(N\)であって、1-9が使えるときの式の総数」であるような級数

• \(E(x)\)：\(x^N\)の係数が「文字数が\(N\)であって、1-9と*が使えるときの式の総数」であるような級数

ここで、

\[C(x)=\sum_{n=0}^{\infty}f(n)x^n\]

について、\([x^n]C(x)\)が求められれば十分です。

ここで、\([x^n]P(x)\)を,\(P(x)\)の\(x^n\)の係数です。

\(A,B,C,D,E\)のうち簡単なものから求めましょう。

すると、

\[A(x)=\dfrac{45x}{(1-9x)(1-90x)}\]

\[D(x)=\dfrac{9x}{1-9x}\]

となります。

\(B(x)\)については、\(k\)個の数があって、\(i\)番目は\(a_i\)桁\((1\leq a_i)\)であるような状況を考えます。

ここで、\(k\)の範囲としては、\(1\leq k,2k-1\leq N\)

であり、さらに文字数としてのつじつま合わせを考えると

\[a_1+\cdots+a_k=N-k+1\]

となります。

すると、

\[[x^N]B(x)=\sum_{k}\sum_{\sum a_i=N-k+1}\prod_{i=1}^{k}[x^{a_i}]A(x)\]

であり、これは

\[[x^N]B(x)=\sum_{k}[x^{N-k+1}]A(x)^k=[x^{N+1}]\sum_{k}\{xA(x)\}^k\]

これを踏まえると、

\[[x^N]B(x)=[x^{N+1}]\dfrac{xA(x)}{1-xA(x)}\]

であるため。

\[B(x)=\dfrac{A(x)}{1-xA(x)}=\dfrac{45x}{1-99x+765x^2}\]

同様の手法で、\(E(x)\)も計算できて、

\[E(x)=\dfrac{D(x)}{1-xD(x)}=\dfrac{9x}{1-9x-9x^2}\]

となります。

\(C(x)\)については、式が\(k\)個の和に分解されて、各項が\(a_i\)文字で表現されているような状況を考えます。

ただし、\(1\leq k,2k-1\leq N,a_i\geq 1,\sum_{i=1}^{k}a_i=N-k+1\)です。

すると、

\[[x^N]C(x)=\sum_{k}\sum_{\sum a_i=N-k+1}\sum_{i=1}^{k}[x^{a_i}]B(x)\prod_{i\neq j}[x^{a_j}]E(x)\]

よって、

\[[x^N]C(x)=\sum_{k\geq 1}[x^{N-k+1}]\sum_{i=1}^{k}B(x)E(x)^{k-1}\]

\[[x^N]C(x)=[x^N]\sum_{k\geq 1}kB(x)(xE(x))^{k-1}\]

\[[x^N]C(x)=[x^N]\dfrac{B(x)}{(1-xE(x))^2}\]

よって、

\[C(x)=\dfrac{45x-810x^2+2835x^3+7290x^4+3645x^5}{1-117x+2592x^2-17901x^3+2673x^4+215784x^5+247860x^6}\]

となります。

級数の値については、Bostan-Mori Algorithmなどを使えば高速に計算することができます。