五の一 高校数学 場合の数

質問

30個の正の整数x[1],x[2],...x[30]がx[1]<=x[2]<=...<=x[29]<=x[30] x[30]=3
をみたすとすると　このような数の並び(x[1],x[2],...x[30])は何通りあるか

回答1

1<=x[1]<=x[2]<=...<=x[29]<=3は1<=x[2]+1<x[3]+2<...<x[29]+28<=31

と同値なので、この不等式をみたす整数の組x[1],x[2]+1,...,x[29]+28がいくつあるか数えると
31C29=465通り

回答2 a[1]+a[2]+a[3]=29・・・(1)をみたす負でない整数解(a[1],a[2],a[3])がいくつあるか数えると良くてa[1]の値で場合わけすると30+29+28+・・・1+=465

(1)⇔(a[1]+1)+(a[2]+2)+(a[3]+3)=32と考えると32個を3分割すると方法は何通り?となり

31C2通りと数えることができる

となっていたのですが

回答1では何で1<=x[1]<=x[2]<=...<=x[29]<=3と

1<=x[1]<x[2]+1<x[3]+2<...<x[29]+28<=31が同値になるんですか？全然違う式に見えますが、不等号が成り立つのはわかりますが　後は最後の整数の組x[1],x[2]+1,...x[29]+28の組み合わせの数が31C29となるのがわかりません

回答2はa[1]+a[2]+a[3]=29・・・(1)をみたす負でない整数解(a[1],a[2],a[3])がいくつあるか数えると良くてというのが何でそれで今回の場合の数を求めることになるのかわかりません

a[1]の値で場合わけすると30+29+28+・・・1+=465の所も何でこういう式になるのかわからないです

(a[1]+1)+(a[2]+2)+(a[3]+3)=32と考えると32個を3分割するの所も何でこんな事をするのかわかりませんa[1]に1を足したりa[2]に2を足したりは何でするのですか？この式から31C2とするのも良くわかりません

回答No.2

sippu-0722 · ベストアンサー

No.1の者です。

>1を足す場合全部のx[1]からx[29]に足さないと同じ不等式にならないんじゃないんですか？
>x[3]より右の項だけに1を足したとしても、同じにはならないんじゃないですか？

たしかに「同値変形」という意味では，そうしなければいけません。ですので，今回の変形は「同値変形」と呼ばないほうが正しいのかもしれません。
こういう操作は「置き換え」と呼ぶことが多いと思います。
（「右辺をx[2]からx[2]+1に置き換える」という具合です。）

ただ大事なのは，「右辺だけに1を加える事で，【<=】から【<】に置き換えることができる」というところなので，そこを理解してもらえればいいと思います。

>何故そのように解釈できるんですか？
>等号がないことから全部違う値で順に大きくなっているというのはわかりますが、そしてその選び方が何故31 C 29　となるんですか？

x[1]からx[29]までに，1～31の数を当てはめます。
ただし，数が重複してはいけない，全てのx[*]は一つ左の値よりも大きくなければいけない。という制限がついています。ここまでは大丈夫でしょうか？

x[1]からx[29]までに重複なく当てはめるので，数は29種類必要ですね。しかし私達が使える数は1～31の31種類あります。
そこで，31種類から29種類に絞らないといけません。
よって，　31 C 29　を計算して，31種類から29種類選ぶ選び方を計算しています。

*補足*
または，「使わない2つを選ぶ」という考え方もできます。
例えば「1と2を使わない」とすると，3～31の29種類を並べればいいことになります。
この，31種類から使わない2つを選ぶ選び方は
31 C 2　となり，同じ結果になります。

n C k　と　n C (n-k)　は同じ結果になることは習ったと思います。

>>「1が並ぶゾーン」「2が並ぶゾーン」「3が並ぶゾーン」の3つに分けるという考え方だ
>>と思います。
>もう少し詳しくお願いします

この部分は私も理解が足りていないので，きちんとは説明できませんが・・・。

「○○○...○○」というふうに30個並べたいとします。使う数字は1,2,3のどれかですね。
そして，あるところで 1 から 2 に変わったとしたら，それ以降は 1 は登場しませんね。
ということは，並んだ30個は
「1のゾーン」「2のゾーン」「3のゾーン」の順に並んでいるはずです。（1や2は0個の場合もありますが）
なので，30個の整列を，どこで区切って次のゾーンにするか　という区切り方を計算しているのだと思います。

[1ゾーン] [2ゾーン] [3ゾーン]
○○○...○|○○...○|○○

この「|」をどこに挿入するか。ということです。

お礼

御返答有難うございます

補足

>こういう操作は「置き換え」と呼ぶことが多いと思います。
置き換えた後の不等式が成り立つのはわかるのですが、置き換える前と置き換えた後で場合の数が同じになるかはわからないんじゃないですか？同じになるとありますが、何故同じだと言えるのかが分からないです

>全てのx[*]は一つ左の値よりも大きくなければいけない。という制限がついています。こ>こまでは大丈夫でしょうか？
はい

>この「|」をどこに挿入するか。ということです。
仕切りの数は回答は31本で○は32個ですが何故ですか？○は30個じゃないんですか？仕切りの数も何故この数なのか分かりません

回答No.1

sippu-0722

はじめまして。数学のプロでもなんでもないので，分かりにくいかもしれないですが，参考までに読んでみてください。

【回答1について】
不等式における「同値」とは「お隣さんとの大小の関係が変わらなければいい」くらいに思ってください。

　1<=x[1]<= x[2]<=...<=x[29]<=3　　　　　（↓x[2]より右の全ての項に1をたす）
　1<=x[1]【<】x[2]+1<=x[3]+1...<=x[29]+1<=4（↓x[3]より右の全ての項に1をたす）
　1<=...<x[2]+1【<】x[3]+2...<=x[29]+2<=5　（↓x[4]より右の全ての項に1をたす）
　...
　1<=...<x[27]+26【<】x[28]+27...<=x[29]+27<=30（↓x[29]より右の全ての項に1をたす）
　1<=x[1]<x[2]+1<x[3]+2<...<x[29]+28<=31

このように，同じ操作を繰り返すことで，不等式の関係性を崩すことなく【<=】が1つずつ【<】に変わっていきますね。
また，x[2]からx[29]まで28回繰り返すので，最右辺は　3+28=31　になります。

そして変形後の不等式は，【<=】から【<】に変わったおかげで，次のように解釈できます。
　「1から31までの自然数を，重複しないように29個選ぶ」

この選び方は，31 C 29　となるわけです。

【回答2について】
まず，この問題をもう一度確認してみましょう。求める1つの場合は例えば次のようなものなどです。
　1,1,1,...,2,2,2,...,3,3,3（合計30個）
　2,2,2,...,2,2,3（合計30個）
つまり，「1,2,3を30個並べる。右端は3で。隣り合う数字は，左<=右　の関係を守る」です。

よって，使う数字は3種類で，それぞれを何個使うか　を考えればよさそうです。
1の個数をa[1]，2の個数をa[2]，3の個数をa[3]（ただし，30個目はノーカウント）と考えれば，
　a[1]+a[2]+a[3]=29　をひらめきます。
ここで，0<=a[1],a[2],a[3]<=29　に注意してください。30個目をノーカウントにしているので，合計29個ですね。

あとはこの場合の数を求めます。回答にあるように，3つ一気に考えると大変なので，a[1]を固定して考えます。

【a[1]＝0の場合】
a[2]+a[3]=29になるような場合は，a[2]:0～29, a[3]:29～0の　30通り

【a[1]＝1の場合】
a[2]+a[3]=28になるような場合は，a[2]:0～28, a[3]:28～0の　29通り

...

【a[1]＝28の場合】
a[2]+a[3]=1になるような場合は，a[2]:0～1, a[3]:1～0の　2通り

【a[1]＝29の場合】
a[2]+a[3]=0になるような場合は，a[2]:0, a[3]:0の　1通り

全て合計すると，30+29+...+2+1＝31×15＝465　となります。

最後の　(1)⇔(a[1]+1)+(a[2]+2)+(a[3]+3)=32　は正直私もよく分かりません。
まず右辺を整理すると(1)⇔a[1]a[2]+[3]＝26　となり同値変形できていませんし。
しかし，3分割というのは30個並べるときに，「1が並ぶゾーン」「2が並ぶゾーン」「3が並ぶゾーン」の3つに分けるという考え方だと思います。

以上です。参考になれば幸いです。

お礼

御返答有難うございます

補足

>1<=x[1]<= x[2]<=...<=x[29]<=3　　　　　（↓x[2]より右の全ての項に1をたす）>1<=x[1]【<】x[2]+1<=x[3]+1...<=x[29]+1<=4（↓x[3]より右の全ての項に1をた>す）
>1<=...<x[2]+1【<】x[3]+2...<=x[29]+2<=5　（↓x[4]より右の全ての項に1をた
>す）
1を足す場合全部のx[1]からx[29]に足さないと同じ不等式にならないんじゃないんですか？
x[3]より右の項だけに1を足したとしても、同じにはならないんじゃないですか？

>そして変形後の不等式は，【<=】から【<】に変わったおかげで，次のように解釈でき
>ます。「1から31までの自然数を，重複しないように29個選ぶ」
何故そのように解釈できるんですか？等号がないことから全部違う値で順に大きくなっているというのはわかりますが、そしてその選び方が何故31 C 29　となるんですか？

>全て合計すると，30+29+...+2+1＝31×15＝465　となります。
非常に分かりやすかったです、有難うございます

>「1が並ぶゾーン」「2が並ぶゾーン」「3が並ぶゾーン」の3つに分けるという考え方だ
>と思います。
もう少し詳しくお願いします