x + y + z = 10 の「整数解の組」は仕切りで数える

$x+y+z=10$ を満たす 0 以上の整数の組は 66 通りあります。全部書き出すのは大変ですが、印と仕切りに置きかえると 1 行で出る。

方程式の整数解を数える問題は、同じものを配る問題と同じ形をしています。置きかえができれば、あとは組合せの計算だけです。

印と仕切りに置きかえる

$x+y+z=10$ を、10 個の印を 3 つの箱に分ける問題と見ます。箱に入った個数が $x$、$y$、$z$ にあたる。

印を一列に並べ、仕切りを 2 本入れれば 3 つに分かれます。仕切りの位置を決めることが、解を 1 つ決めることと同じ。

印 10 個と仕切り 2 本、合わせて 12 個の場所から、仕切りの位置 2 か所を選ぶ。

$${}_{12}{\mathrm{C}}_2=66$$

66 通りです。この数え方を仕切りの方法といいます^[1]。

一般の形

変数が $k$ 個、右辺が $n$ のとき、0 以上の整数解の個数は次の式になります^[1]。

$${}_{n+k-1}{\mathrm{C}}_{k-1}$$

仕切りは $k-1$ 本。印 $n$ 個と合わせた $n+k-1$ か所から、仕切りの位置を選ぶ形です。

重複を許して選ぶ ${}_k{\mathrm{H}}_n$ と同じ値になります。$k$ 種類から $n$ 個を選ぶことと、$k$ 個の変数に $n$ を分けることが同じだから。

例：変数が 4 つ

$x+y+z+w=8$ の 0 以上の整数解を数えます。仕切りは 3 本。

$${}_{8+3}{\mathrm{C}}_3={}_{11}{\mathrm{C}}_3=165$$

165 通りです。変数が増えると仕切りが増え、選ぶ個数も増えます。

正の整数解

$x$、$y$、$z$ がすべて 1 以上という条件なら、数え方が変わります。空の箱を認めない形です。

印 10 個を一列に並べ、その間の 9 か所のすき間から 2 か所を選んで仕切りを入れる。両端やすき間の重複は使えません。

$${}_9{\mathrm{C}}_2=36$$

36 通り。一般には ${}_{n-1}{\mathrm{C}}_{k-1}$ になります^[1]。

置きかえで下限をそろえる

$1$ 以上の場合は、置きかえでも解けます。$x=x^{\prime }+1$ のように、下限のぶんを先に引いておく。

$x+y+z=10$ で全員 1 以上なら、$x^{\prime }+y^{\prime }+z^{\prime }=7$ の 0 以上の解と同じ。${}_9{\mathrm{C}}_2=36$ で、さきほどと一致します。

下限がばらばらでも同じ手が使えます。

例：下限がそろっていない場合

$x+y+z=12$ で、$x\ge 1$、$y\ge 2$、$z\ge 3$ とします。

$x=x^{\prime }+1$、$y=y^{\prime }+2$、$z=z^{\prime }+3$ と置くと、$x^{\prime }+y^{\prime }+z^{\prime }=12-6=6$。

$${}_{6+2}{\mathrm{C}}_2={}_8{\mathrm{C}}_2=28$$

28 通りです。下限は引いてしまえば消えます。上限のほうは、この手では消えません。

上限があるときは引き算

$x+y+z=10$ で、$0\le x,y,z\le 5$ とします。上限は置きかえで消せないので、破った場合を引きます。

$x\ge 6$ になる解を数えます。$x=x^{\prime \prime }+6$ と置くと $x^{\prime \prime }+y+z=4$ で、${}_6{\mathrm{C}}_2=15$ 通り。

$y$ と $z$ についても同じく 15 通りずつ。2 つ以上が同時に 6 以上になると和が 12 を超えるので、そういう解はありません。

$$66-3\times 15=66-45=21$$

21 通りです。

例：足し戻しが必要な場合

$x+y+z=14$ で $0\le x,y,z\le 6$ とします。今度は 2 つが同時に上限を破れます。

全体は ${}_{16}{\mathrm{C}}_2=120$ 通り。$x\ge 7$ なら $x^{\prime \prime }+y+z=7$ で ${}_9{\mathrm{C}}_2=36$ 通り、3 つの変数で $3\times 36=108$。

$x\ge 7$ かつ $y\ge 7$ なら $x^{\prime \prime }+y^{\prime \prime }+z=0$ で 1 通り。そういう組が 3 通りあるので 3 を足し戻します。

$$120-108+3=15$$

15 通りです^[3]。上限が小さいほど、足し戻しの項が効いてきます。

例：不等式の場合

$x+y+z\le 10$ を満たす 0 以上の整数解を数えます。等号でないので、そのままでは仕切りが使えません。

余りを受けとる変数 $w$ を足します。$w=10-(x+y+z)$ と置けば $w\ge 0$ で、$x+y+z+w=10$ になる。

$${}_{10+3}{\mathrm{C}}_3={}_{13}{\mathrm{C}}_3=286$$

286 通りです。不等式は、ダミーの変数を 1 つ足して等式に直す。

例：配る問題として読む

同じ形の問題は、言い回しを変えて何度も出ます。

「同じあめ玉 10 個を 3 人に配る。もらえない人がいてもよい」なら 66 通り。「全員が 1 個以上もらう」なら 36 通り。

「1 人 5 個までしかもらえない」なら 21 通り。方程式の姿になっていなくても、印と仕切りに置きかえられます。

例：積の形に見える問題

$xyz=12$ を満たす正の整数解は、この方法では出ません。掛け算は仕切りに置きかえられない。

こちらは素因数分解で考えます。$12=2^2\times 3$ なので、2 の指数 2 を 3 人に分ける形と、3 の指数 1 を 3 人に分ける形を掛ける。

2 の指数 2 を 3 つに分けるのが ${}_4{\mathrm{C}}_2=6$ 通り、3 の指数 1 を 3 つに分けるのが ${}_3{\mathrm{C}}_2=3$ 通り。$6\times 3=18$ 通りです。

指数に注目すれば、足し算の形に戻ります。積の問題を見たら、まず素因数分解する。

よくある誤り

方程式を見たら、印と仕切りの絵に置きかえられるかを考える。置きかえられれば、あとは選ぶだけです。

参考文献

^[1] が仕切りによる数え方、^[2] が組合せの公式、^[3] が上限を処理する足し引き、^[4] と ^[5] が各国語での整理です。