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} C_{2} = 66$

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

一般の形

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

$_{n + k - 1} C_{k - 1}$

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

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

例：変数が 4 つ

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

$_{8 + 3} C_{3} =_{11} C_{3} = 165$

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

正の整数解

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

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

$_{9} C_{2} = 36$

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

0 以上でよい場合

仕切りは印と同じ列に並べられる。同じ場所に 2 本入ってもよい

1 以上が必要な場合

仕切りは印と印のすき間にしか入らない。1 か所に 1 本まで

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

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

$x + y + z = 10$ で全員 1 以上なら、 $x^{'} + y^{'} + z^{'} = 7$ の 0 以上の解と同じ。 $_{9} C_{2} = 36$ で、さきほどと一致します。

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

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

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

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

$_{6 + 2} C_{2} =_{8} C_{2} = 28$

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

下限があれば先に引いて 0 以上にそろえる

仕切りの式で全体を数える

上限があれば包除原理で引く

上限があるときは引き算

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

$x \geq 6$ になる解を数えます。 $x = x^{''} + 6$ と置くと $x^{''} + y + z = 4$ で、 $_{6} C_{2} = 15$ 通り。

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

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

21 通りです。

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

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

全体は $_{16} C_{2} = 120$ 通り。 $x \geq 7$ なら $x^{''} + y + z = 7$ で $_{9} C_{2} = 36$ 通り、3 つの変数で $3 \times 36 = 108$ 。

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

$120 - 108 + 3 = 15$

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

2 つ同時に破れるかどうかは、上限の 2 倍と右辺を比べれば分かります。上限が 6 で右辺が 14 なら、 $7 + 7 = 14$ で届く。

上限が 5 で右辺が 10 なら $6 + 6 = 12$ が 10 を超えるので、2 つ同時には破れない。

例：不等式の場合

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

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

$_{10 + 3} C_{3} =_{13} C_{3} = 286$

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

例：配る問題として読む

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

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

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

問題文	条件	通り数
もらえない人がいてもよい	0 以上	66
全員が 1 個以上	1 以上	36
1 人 5 個まで	0 以上 5 以下	21

例：積の形に見える問題

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

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

2 の指数 2 を 3 つに分けるのが $_{4} C_{2} = 6$ 通り、3 の指数 1 を 3 つに分けるのが $_{3} C_{2} = 3$ 通り。 $6 \times 3 = 18$ 通りです。

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

$a + b + c + d = 7$ を満たす 0 以上の整数の組は何通りありますか。

35 通り
120 通り
210 通り

__RESULT__

仕切りは 3 本なので $_{7 + 3} C_{3} =_{10} C_{3} = 120$ 通りです。35 は $_{7} C_{3}$ で、印だけから選んだ値になります。

よくある誤り

仕切りの本数を変数の個数と同じにする。変数が

k

個なら仕切りは

k - 1

本です

0 以上と 1 以上をとり違える。前者は

n + k - 1

から、後者は

n - 1

から選びます

下限を引かずに数える。

x \geq 2

なら先に 2 を引いて 0 以上にそろえます

上限を置きかえで消そうとする。上限は包除原理で引くしかありません

足し戻しが要るかを確かめない。上限の 2 倍と右辺を比べます

不等式のまま仕切りを当てる。余りを受けとる変数を 1 つ足します

積の形の方程式に仕切りを使う。素因数分解して指数の和に直します

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

参考文献

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

Stars and bars (combinatorics) - Wikipedia)

Combination - Wikipedia

Inclusion–exclusion principle - Wikipedia

Combinatoire - Wikipédia

Abzählende Kombinatorik - Wikipedia

0 以上の整数で x + y + z = 10 を満たす組は 66 通りです。印 10 個を並べて仕切りを 2 本入れる、と置きかえれば選ぶだけで出ます。1 以上という条件なら仕切りはすき間にしか入らず 36 通り。下限は引いて消せますが、上限は包除原理で引くしかありません。足し戻しが要るかどうかの見分け、不等式にダミー変数を足す手、積の形の方程式を素因数分解で足し算に戻す手まで扱いました。