和が30になる大小順の組

方針

解答

⓪ 発想 — どう考え始めるか。 $x\le y\le z$ の条件を保ったまま数えるのは難しい。そこで、いったん順序を区別して数え、並べ替えの束で割る方針を立てる。

ただし注意がいる。大小順の組 $(1,2,27)$ には順序つきの組が $3!=6$ 個対応するが、$(0,15,15)$ には3個、$(10,10,10)$ には1個しか対応しない。束の大きさが組によって違うのだ。

だから「すべて異なる」「ちょうど2つ等しい」「3つとも等しい」に分類してから束ねる。これが正しい手順になる。

① 順序を区別した総数。 $x+y+z=30$ の0以上の整数解は、○30個と仕切り2本の並べ替えで

$${}_{32}{\mathrm{C}}_2=\frac{32\cdot 31}{2}=496\text{個}$$

② 等しい成分を含む組を数える。 3つとも等しいのは $x=y=z=10$ の1組(順序つきでも1個)。ちょうど2つ等しい組は、等しい値を $t$ として $2t+z=30$、$z=30-2t$。$t=0,1,\dots ,15$ の16通りから、$z=t$ になってしまう $t=10$ を除いて15組。順序つきでは1組につき(どの位置が仲間はずれかで)3個ずつあるから $15\times 3=45$ 個。

③ 分類して束ねる。 すべて異なる順序つきの組は

$$496-45-1=450\text{個}$$

これらは6個ずつ束になり、大小順の組 $450÷6=75$ 個を与える。よって求める個数は

$$75+15+1=91\text{個}$$

まとめ: 「順序をつけて数えて割る」は、等しいものを含む組の補正とセットで初めて正しくなる。分類ごとに束の大きさ(1・3・6)が違う。この一点が急所だ。

発展 — 一歩先へ。 答えの91は、$\frac{(30+3{)}^2}{12}=90.75$ に最も近い整数になっている。実は $x\le y\le z$、$x+y+z=n$ の解の個数は、つねに $\frac{(n+3{)}^2}{12}$ に最も近い整数だ。3つの場合の補正が、この「丸め」の中に折りたたまれている。

別解

差の変数に取り替える(束ねずに直接数えるルート)。 大小の条件そのものを、新しい変数に吸収させてしまう方法もある。

$x\le y\le z$ を、$x=a$、$y=a+b$、$z=a+b+c$($a,b,c$ は0以上の整数)と書き直す。大小関係は自動的に満たされ、条件はただ1本:

$$x+y+z=3a+2b+c=30$$

あとはこの方程式の0以上の整数解を数える。$a$ を $0$ から $10$ まで動かし、各 $a$ で $b$ は $2b\le 30-3a$ の範囲($c$ は残りで自動的に決まる):

$$16+14+13+11+10+8+7+5+4+2+1=91\text{個}$$

束ね上げも重複補正も現れない。「不等式つきの数え上げは、差を新しい変数にすると等式だけになる」— この取り替えは、順序つき分割の問題全般で使える定番の一手だ。