TMO2022(K)

　問題の条件より, $S$ に含まれる元について, $a+b+c\leq 8$ なる非負整数 $(a,b,c)$ を用いて, $100$ の位を $1+a$, $10$ の位を $1+a+b$, $1$ の位を $1+a+b+c$ と表すことができる.よって, 求めるのは, $$\sum_{i\neq j}S_iS_j= \frac{1}{2}\Big(\Big(\sum_{a+b+c\leq 8}(111+111a+11b+c)\Big)^2-\sum_{a+b+c\leq 8}(111+111a+11b+c)^2\Big)$$であり, $a+b+c\leq 8$ なる非負整数の組 $(a,b,c)$と $a+b+c+d=8$ なる非負整数の組 $(a,b,c,d)$ は一対一に対応することから, 以下のように表せる. $$\frac{1}{2}\Big(\Big(\sum_{a+b+c+d= 8}(111+111a+11b+c)\Big)^2-\sum_{a+b+c+d=8}(111+111a+11b+c)^2\Big)$$ $\displaystyle\sum_{a+b+c+d= 8}a=\sum_{a+b+c+d= 8}b$ など対称性に注意して展開すると,以下のように式変形できる.
ただし, 下の式変形について, $$\sum_{k=0}^{\infty}kx^k=\dfrac{x}{(1-x)^2},\:\sum_{k=0}^{\infty}k^2x^k=\dfrac{x+x^2}{(1-x)^3}$$ が成り立つことを用いている. $$\begin{aligned} &\sum_{a+b+c+d=8}(111+111a+11b+c)\\ &=111\Big(\sum_{a+b+c+d=8}1\Big)+123\Big(\sum_{a+b+c+d=8}a\Big)\\ &=111[x^8]\Big(\frac{1}{1-x}\Big)^4+123[x^8]\frac{x}{(1-x)^2}\times\Big(\frac{1}{1-x}\Big)^3 \end{aligned}$$ $$\begin{aligned} &\sum_{a+b+c+d=8}(111+111a+11b+c)^2\\ &=111^2\Big(\sum_{a+b+c+d=8}1\Big)+2\times(111\times111+111\times11+111\times1)\Big(\sum_{a+b+c+d=8}a\Big)\\ &+(111^2+11^2+1^2)\Big(\sum_{a+b+c+d=8}a^2\Big)+2(111\times11+11\times1+1\times111)\Big(\sum_{a+b+c+d=8}ab\Big)\\ &=12321[x^8]\Big(\frac{1}{1-x}\Big)^4+27306[x^8]\frac{x}{(1-x)^2}\times\Big(\frac{1}{1-x}\Big)^3\\ &+12443[x^8]\frac{x+x^2}{(1-x)^3}\times\Big(\frac{1}{1-x}\Big)^3+2686[x^8]\Big(\frac{x}{(1-x)^2}\Big)^2\times\Big(\frac{1}{1-x}\Big)^2 \end{aligned}$$ 　これは $\displaystyle[x^n]\frac{1}{(1-x)^m}=\binom{n+m-1}{m-1}$ などを用いると計算できる.