OMC113(E)

包除原理パートの説明です．

$x=2a+1, y=2b+1, z=2c+1, w=2d+1$ と置くと， 求めるものは 「$xyzw=999999$ かつ $x\neq1$ かつ $y\neq1$ かつ $z\neq1$ かつ $w\neq1$ 」を満たす正整数 $(x,y,z,w)$ の組です．ここで，$xyzw=999999$ を満たす $(x,y,z,w)$ の組のうち $x=1$ を満たすものの集合を $X$ と置きます．同様に $y=1, z=1, w=1$ を満たす組の集合を $Y,Z,W$ と置きます．このとき，($xyzw=999999$ を満たすすべての $(x,y,z,w)$ の組の個数)$-|X\cup Y\cup Z\cup W|$ が答えになります．

($xyzw=999999$ を満たすすべての $(x,y,z,w)$ の組の個数) を求めるのは容易です．$3$ の $x,y,z,w$ への分配方法が ${}_6\mathrm{C}_{3}$ 通り，$7,11,13,37$ の分配方法がそれぞれ $4$ 通りなので ${}_6\mathrm{C}_{3}\times4^4$ 個になります．

また，包除原理より以下が成り立ちます． $$\begin{aligned} &|X\cup Y\cup Z\cup W|\\ =&|X|+|Y|+|Z|+|W|\\ -&|X\cap Y|-|X\cap Z|-|X\cap W|-|Y\cap Z|-|Y\cap W|-|Z\cap W|\\ +&|X\cap Y\cap Z|+|X\cap Y\cap W|+|X\cap Z\cap W|+|Y\cap Z\cap W|\\ -&|X\cap Y\cap Z\cap W| \end{aligned}$$

右辺のそれぞれの段について考えてみます．

• 一段目のついて：$|X|$ は「$xyzw=999999$ かつ $x=1$」，すなわち $yzw=999999$ を満たす $(y,z,w)$ の個数です．これは先ほど同様に分配方法を考えることで ${}_5\mathrm{C}_{3}\times3^4$ と求めることができます．$|Y|, |Z|, |W|$ も同様です．よって一段目の値は $4\times{}_5\mathrm{C}_{3}\times3^4(={}_4\mathrm{C}_{1}\times{}_5\mathrm{C}_{3}\times3^4)$ です．
• 二段目について：$|X\cap Y|$ は「$xyzw=999999$ かつ $x=1$ かつ $y=1$」，すなわち $zw=999999$ を満たす $(z,w)$ の個数です．これも先ほど同様に分配方法を考えることで ${}_4\mathrm{C}_{3}\times2^4$ と求めることができます．他も同様です．よって三段目の値は $6\times{}_4\mathrm{C}_{3}\times2^4(={}_4\mathrm{C}_{2}\times{}_4\mathrm{C}_{3}\times2^4)$ です．
• 三段目について：$|X\cap Y\cap Z|$ は「$xyzw=999999$ かつ $x=1$ かつ $y=1$ かつ $z=1$」，すなわち $w=999999$ を満たす $(w)$ の個数です．これも先ほど同様に分配方法を考えることで ${}_3\mathrm{C}_{3}\times1^4$ と求めることができます．他も同様です．よって三段目の値は $4\times{}_3\mathrm{C}_{3}\times1^4(={}_4\mathrm{C}_{1}\times{}_3\mathrm{C}_{3}\times1^4)$ です．
• 四段目について：$|X\cap Y\cap Z\cap W|$ は「$xyzw=999999$ かつ $x=1$ かつ $y=1$ かつ $z=1$ かつ $w=1$」を満たす $(x,y,z,w)$ の個数ですが，これを満たすものは存在しないので $0$ です．

以上の値をもとの式に代入することで，公式解説の式を得ます．