2014年1月1日水曜日

重複組合せ(3) 最短経路の数

【問3】
方程式x+y+z=7の負でない整数解は何個あるか。

この問題の方程式の解を順次に書くと、
(x,y,z)=
(0,0,7)
(0,1,6)
(0,2,5)
・・・
と順次に書けます。
xが0~何個かであり、
yが0~何個かであり、
zが0~何個かである
組合せの数を求める問題です。

この問題は、その解の組み合せと1対1に対応する別の組み合わせを求める以下の問題を考えます。そして、その組み合わせの数を考えると解けます。

初めに、(x,y,z)=(0,0,0)としておき、
それらのx,y,zの値を1つづつ増す7つの指令の組合せの数を求める。
その組合せは、以下の、
変数を直接指定する3つの指令と、
変数を間接的に指定する6つの指令
とから成る合計9つの指令のうちから7つを選ぶ組合せと1対1対応します。

x指令:xを選んで、その値を1にする。
y指令:yを選んで、その値を1にする。
z指令:zを選んで、その値を1にする。
第2指令:第1指令で値を設定した変数に更に1を足す。
第3指令:第2指令で値を設定した変数に更に1を足す。
第4指令:第3指令で値を設定した変数に更に1を足す。
第5指令:第4指令で値を設定した変数に更に1を足す。
第6指令:第5指令で値を設定した変数に更に1を足す。
第7指令:第6指令で値を設定した変数に更に1を足す。

上の指令から7つを選ぶ。
その選択の結果、順番が抜けている第n指令の位置に、選ばれたx指令、y指令、z指令のいずれかをx,y,zの順に配置して、第1から第7指令を完成させる。

この指令の組合せは、例えば、
(1)y指令:yを選んで、その値を1にする。
第2指令:第1指令で値を設定した変数に更に1を足す。
第3指令:第2指令で値を設定した変数に更に1を足す。
(4)z指令:zを選んで、その値を1にする。
第5指令:第4指令で値を設定した変数に更に1を足す。
第6指令:第5指令で値を設定した変数に更に1を足す。
第7指令:第6指令で値を設定した変数に更に1を足す。
です。
この指令群の結果、
x=0で変わらず、
y=1+1+1=3
z=1+1+1+1=4
となり、
x+y+z=7
を満足しています。

大事なポイントは、この指令の組み合わせが、x+y+Z=7を満足する負でない整数解に1対1に対応することである。
(1)この指令の組み合わせが、x+y+Z=7を満足する負でない整数解を表す。
(2)逆に、x+y+Z=7を満足する負でない整数解は、必ず、これらの指令を7つ組み合わせることによって表すことができる。

そのため、
方程式x+y+z=7の負でない整数解の数
=x指令とy指令とz指令とその他の6つの指令から7個を選ぶ組み合わせの数
(3+6)
(3+6)
=9×8/2=36

【別解】
方程式x+y+z=7の負でない整数解が何個あるかを以下のようにして求めることもできる。

上図のようにx行とy行とz行との3行を有し、横の長さが7の格子を考える。
格子のA点からB点まで、xの行からzの行まで格子を辿って、右と上に進む最短経路を描く。

上図で、
x=(x行の、A点から昇り階段までの長さ)
y=(y行の、階段と階段の間の長さ)
z=(z行の、階段からB点までの長さ)
とすると、
方程式x+y+z=7がいつでも満たされる。

A点からB点まで、格子をたどって右と上に進む最短経路は、
方程式x+y+z=7を満たす(x,y,z)の組合せに
1対1で対応する。
つまり、
(1)どの(x,y,z)の1つの組合せに対しても、必ず1つだけ、AからBへの最短経路がある。
(2)AからBへのどの最短経路に対しても、必ず1つだけ、(x,y,z)の組合せがある。
という関係(1対1対応する関係)がある。

そのため、A点からB点までの全ての経路の数は、(x,y,z)の組合せの数と等しい。

上図の経路は、
→→↑→→→↑→→
とあらわせる。
すなわち、経路は、(↑)2つと(→)7つの順列であらわされる。
(A点からB点までの経路は、(↑)2つと(→)7つがの順列と1対1対応する)

そのため、図のA点からB点までの全ての経路の数は、(↑)2つと、(→)7つが作る全ての順列の数と等しい。
その数は、
(2+7)!/(2!×7!)
(2+7)
になる。
これは、先の解答と同じ答えである。

(蛇足)
経路を考えずに、いきなり、
(↑)2つと(→)7つの順列が、方程式x+y+z=7を満たす(x,y,z)の組合せに1対1で対応することに注目することで答えを計算することもできる。
(↑)と(↑)の間の(→)の数が、x、y、zに対応するからである。

しかし、その説明では、
(↑)と(↑)の間の(→)の数が、x、y、zに対応するからという説明では、
例えば、
→→↑→→→↑→→
のように、最後にはもう(↑)が無い順列が作られる一方、
例えば、
→→→↑→→→→↑
のように、
最後に並べた(→)の後に、もう必要が無い(↑)をわざわざ加えた順列も作る、
という理由がハッキリしない。

最後に(↑)をわざわざ加えた順列も作られる理由は、
そうしないと、その順列は、(↑)2つと(→)7つの順列とは(↑)の数が不足した異なる種類の順列になってしまうので、都合が悪いからである。
都合が悪いから順列の最後に(↑)をわざわざ加えるという行為が許される理由は、
(x,y,z)の組合せに1対1で対応させる(好きなルールを作って対応させる)ことができる順列がありさえすれば、それで十分だという事情があるからである。

高校数学(グラフと数式、他)一覧
リンク:高校数学の目次

0 件のコメント:

コメントを投稿