方程式x+y+z=nの整数解の組数を効率よく求める方法

プロフィール

・地方の公立進学校から高校３年間塾に通わず、1浪を経て京大医学部に合格。（歩兵について詳しくはこちら）

・塾や家庭教師における指導数は10を超え、医学部や国公立合格を多数輩出。

・現役医学生ながら「本質的な学び」や「誰にでも再現可能な勉強法」についてブログで発信中。

生徒

先生！場合の数の分野で、なぜ整数解の問題が出てくるのですか？

歩兵

それはね、場合の数の考えを使えば組み合わせの数を求めることができるからだよ

生徒

何を言ってるかさっぱりわかりません…

方程式\(x+y+z=n\)とは何か

方程式\(x+y+z=n\)は、三つの変数x、y、zが与えられた整数nと等しくなるような整数解（x、y、z）を見つける問題です。

よく場合の数の分野で出てくる問題にあるのは、「\(x+y+z=7\)を満たすような０以上の整数x、y、zの組み合わせの個数を求めよ」といったものです。この問題でいうと、例えばといった組み合わせが条件に当てはまります。一見整数の問題に見えますが、実は場合の数の組み合わせを用いて解くことができてしまいます。

基本的な解き方：整数解の利用

今回は次の様な問題を解いてみましょう。

解き方①：整数解をすべて求める

まず、最初に考えられるのは自力で整数解をすべて求めてその個数を数える解き方です。これは、つまり(x,y,z)=(1,3,4) (2,2,4) (1,5,2)という風に地道に整数解を出していき、最後に全ての組み合わせの個数を数えます。

しかし、この方法では、整数解を全て求めるのに膨大な時間がかかる、数え忘れなどのミスが多発するといった欠点があります。

よって、1個ずつの数え上げはあまり現実的な方法とはいえません。

生徒

私なら絶対数え間違えが出ちゃうよ～

歩兵

ミス多発のほかに、例えば\(x+y+z=20\)といった問題では、数が大きすぎて実際に数え上げるのはほぼ不可能です。

解き方②：重複順列の考え方を使う

はじめに重複順列を復習しましょう。

8個の玉を用意して1列に並べます。その列の中に、2本の仕切りを適当に入れます。2本の仕切りで分けられた玉の数を、左からx,y,zとします。（該当スペースに玉がなければ0個とみなす）

その時、この玉の仕切り方の場合の数は、\(x+y+z=8\)(x,y,zは０以上の整数)の(x,y,z)の組み合わせの数と同じです。

ここで、仕切り方の場合の数は、８個の玉と２本の仕切りの重複順列なので、$$\frac{10!}{2!8!}=45$$

解答の作り方：整数解の組み合わせの数

応用問題：整数解の利用

今まで、扱ってきた問題では、全て整数は０以上でした。しかし、整数が自然数や２以上といった制約がついた場合、今までの方法は使えません。

ですが、ちょっとした工夫を行えば、先ほどの問題と同じように重複順列で解くことができます。

生徒

なんか難しそうでよく分からないなあ

歩兵

では、実際の問題で見ていきましょう！

応用例題

考え方

\(X=x-1\),\(Y=y-1\),\(Z=z-1\)とすると、条件の式は、

$$X+Y+Z=11$$(X,Y,Zは０以上)

となる。この組み合わせの数は、先ほどの重複順列の考え方で求めることができる。

生徒

なるほど！自分が扱いやすいように式を変形すればいいんですね

実際の解答

まとめ：整数解の組み合わせの数

今回の記事はいかがでしたか？最後までご覧いただきありがとうございます。