TMO2022(D) - 母関数を用いる解法

$A,B,C,D$ それぞれに $a,b,c,d$ 票入ったとすると, 非負整数の組 $(a,b,c,d)$ が満たす条件は以下である.

• $a\gt \max\{b,c,d\}$.
• $a+b+c+d=100$.

これを満たす $(a,b,c,d)$ を母関数を用いて数え上げる. 具体的には以下の母関数の $x^{100}$ の係数である.

$$\begin{aligned} \sum_{a=0}^{\infty}\sum_{b=0}^{a-1}\sum_{c=0}^{a-1}\sum_{d=0}^{a-1}x^{a+b+c+d}&=\sum_{a=1}^{\infty}x^a\Big(\sum_{b=0}^{a-1}x^b\Big)^3\\ &=\sum_{a=0}^{\infty}x^a\Big(\frac{1-x^a}{1-x}\Big)^3\\ &=\frac{1}{(1-x)^3}\sum_{a=0}^{\infty}(x^a-3x^{2a}+3x^{3a}-x^{4a})\\ &=\frac{1}{(1-x)^4}-3\frac{1}{(1-x)^3}\frac{1}{1-x^2}+3\frac{1}{(1-x)^3}\frac{1}{1-x^3}-\frac{1}{(1-x)^3}\frac{1}{1-x^4}\\ &=\frac{1}{(1-x)^4}-3\frac{(1+x)^3}{(1-x^2)^4}+3\frac{(1+x+x^2)^3}{(1-x^3)^4}-\frac{(1+x+x^2+x^3)^3}{(1-x^4)^4} \end{aligned}$$ これは以下のように計算できる. $$\begin{aligned} &[x^{100}]\frac{1}{(1-x)^4}-3[x^{100}]\frac{(1+x)^3}{(1-x^2)^4}+3[x^{100}]\frac{(1+x+x^2)^3}{(1-x^3)^4}-[x^{100}]\frac{(1+x+x^2+x^3)^3}{(1-x^4)^4}\\ &=[x^{100}]\frac{1}{(1-x)^4}-3[x^{100}]\frac{1+3x^2}{(1-x^2)^4}+3[x^{100}]\frac{3x+6x^4}{(1-x^3)^4}-[x^{100}]\frac{1+12x^4+3x^8}{(1-x^4)^4}\\ &=\binom{100+3}{3}-3\binom{50+3}{3}-9\binom{49+3}{3}+9\binom{33+3}{3}+18\binom{32+3}{3}-\binom{25+3}{3}-12\binom{24+3}{3}-3\binom{23+3}{3}\\ &=\mathbf{43567} \end{aligned}$$