重複組合せ（３） X+Y+Z=N問題と最短経路の数

以下はここをクリックした先の問題の解答です。

【問３】
方程式ｘ＋ｙ＋ｚ＝７の負でない整数解は何個あるか。

【第１の解】
この問題の方程式の解を順次に書くと、
（ｘ，ｙ，ｚ）＝
（０，０，７）
（０，１，６）
（０，２，５）
・・・
と順次に書けます。
ｘが０～何個かであり、
ｙが０～何個かであり、
ｚが０～何個かである
組合せの数を求める問題です。

　このようにしてあらわした、その解の組み合せと１対１に対応する以下の経路を考える。
方程式ｘ＋ｙ＋ｚ＝７の負でない整数解の数は、その経路の数に等しい。

上図のようにｘ行とｙ行とｚ行との３行を有し、横の長さが７の格子を考える。
格子のＡ点からＢ点まで、ｘの行からｚの行まで格子を辿って、右と上に進む最短経路を描く。

上図で、
ｘ＝（ｘ行の、Ａ点から昇り階段までの長さ）
ｙ＝（ｙ行の、階段と階段の間の長さ）
ｚ＝（ｚ行の、階段からＢ点までの長さ）
とすると、
方程式ｘ＋ｙ＋ｚ＝７がいつでも満たされる。

Ａ点からＢ点まで、格子をたどって右と上に進む１つの最短経路は、
方程式ｘ＋ｙ＋ｚ＝７を満たす（ｘ，ｙ，ｚ）の１つの組合せに
１対１で対応する。
つまり、
（１）どの（ｘ，ｙ，ｚ）の１つの組合せに対しても、必ず１つだけ、ＡからＢへの最短経路がある。
（２）ＡからＢへのどの最短経路に対しても、必ず１つだけ、（ｘ，ｙ，ｚ）の組合せがある。
という関係（１対１対応する関係）がある。

そのため、Ａ点からＢ点までの全ての経路の数は、（ｘ，ｙ，ｚ）の組合せの数と等しい。

上図の経路は、
→→↑→→→↑→→
とあらわせる。
すなわち、経路は、(↑)２つと(→)７つの配列であらわされる。
-------（注意）-------
ここで、「配列」という用語の定義を、同じ(↑)２つの順や同じ(→)７つの順を区別しないで配列の数を数える事を「配列の数を数える」と定義する。
「順列」という用語の定義を、１つ１つの(↑)や(→)に名前を付けた９つの要素の順の配列の数を数える事を「順列の数を数える」と定義する。その順列の数＝９！である。
-----（注意のおわり）--------------

（Ａ点からＢ点までの経路は、(↑)２つと(→)７つの配列と１対１対応する）

そのため、図のＡ点からＢ点までの全ての経路の数は：
（３）：　(↑)２つと、(→)７つが作る全ての色配列の数と等しい。ただし、その色配列は、その配列において、個々の(↑)２つの配列の順を区別せず、個々の(→)７つの配列の順を区別しない。

（４）：　その色配列の数は、合計（２＋７）個の矢印から２つを選んで上向き矢印にし、それ以外の矢印は横向き矢印にする組み合わせの数と等しい。

よって、その組み合わせの数は、
（２＋７）！／（２！×７！）
＝_{（２＋７）}Ｃ_２
になる。
（第１の解おわり）

【第２の解（概要のみ）】
　経路を考えずに、
(↑)２つと(→)７つの配列が、方程式ｘ＋ｙ＋ｚ＝７を満たす（ｘ，ｙ，ｚ）の組合せに１対１で対応することに注目することで答えを計算することもできる。
(↑)と(↑)の間の(→)の数が、ｘ、ｙ、ｚに対応するからである。

ここで、
→→↑→→→↑→→
のように、最後にはもう(↑)が無い配列が作られる一方、
例えば、
→→→↑→→→→↑
のように、
最後に並べた(→)の後に、(↑)を加えた配列も作られる。

最後に(↑)を加えた配列は、最後にあたるZの数が０であることをあらわす。

リンク：高校数学の目次
場合の数と確率