一定の順序を含む順列

質問

添付した問題の理解で苦しんでいます。

不等号に＝が含まれているので重複する順列だと考え、0～9の10個から重複を許して5つ選ぶので、一つに数につき10通り選べ、5つあるので10^5通りでこれを小さい順に並べる方法は1通り。
ただし0,0,0,0,0のみ条件を満たさないから求める通り数は(10^5)-1=99999

とやってしまったのですが、

解答には

0,1,2,3…,9の10個から重複を許して5個を選んで小さい順にx0,x1,…x4とすればよい。
ただし、このうち0,0,0,0,0のみx4=0となり不適である。
9個の　|　と5個の○の並べ方より、14C5
したがって、(14C5)-1=2001

となっています。

解答に書いてある考え方自体はわかるのですが、自分の考え方のどこがまずかったかがはっきりわかりません。（答えの桁数からして明らかに間違いなのはわかりますが…）

回答No.4

yyssaa

＞参考までに10^5に含まれる重複を数えると
(ア)5種類の数字(ABCDE)の並べ方5!通りは小さい順に並べれば1通りだから
(5!-1)*(10C5)=29988通りが重複しており、
(イ)4種類の数字5個(ABCDD)の並べ方5!/2!通りは小さい順に並べれば1通りだから
(5!/2-1)*(10C4)*4=49560通りが重複しており、
(ウ-1)3種類の数字5個(ABCCC)の並べ方5!/3!通りは小さい順に並べれば1通りだから
(5!/3!-1)*(10C3)*3=6840通りが重複しており、
(ウ-2)3種類の数字5個(ABBCC)の並べ方5!/(2!2!)通りは小さい順に並べれば1通りだから
(5!/4-1)*(10C3)*3=10440通りが重複しており、
(エ-1)2種類の数字5個(ABBBB)の並べ方5!/(4!)通りは小さい順に並べれば1通りだから
{5!/(4!)-1}*(10C2)*2=360通りが重複しており、
(エ-2)2種類の数字5個(AABBB)の並べ方5!/(2!3!)通りは小さい順に並べれば1通りだから
{5!/(2!3!)-1}*(10C2)*2=810通りが重複しており、
(オ)1種利の数字5個の場合は重複は無いが00000の1通りは対象外だから
これら(ア)～(オ)を10^5から除くと
10^5-29988-49560-6840-10440-360-810-1=2001となる。

お礼

お礼が遅くなってしまい、申し訳ありません。
別解として素直に求めるとこうなるのですね。
やはり一つ一つ場合分けすると大変ですね…。
とても参考になります。

回答No.3

chie65536（@chie65535）

＞0～9の10個から重複を許して5つ選ぶので、一つに数につき10通り選べ、5つあるので10^5通りでこれを小さい順に並べる方法は1通り。
＞ただし0,0,0,0,0のみ条件を満たさないから

って考えて

(10^5)-1=99999

って式を立てたと思うけど、これ「並び替えて同じになる物」を重複として除外してないよね？

選んだまま、並び替えしてない状態で

0,0,0,0,1
0,0,0,1,0
0,0,1,0,0
0,1,0,0,0
1,0,0,0,0

の５つは「小さい順に並べる」と、全部

0,0,0,0,1

になるから

0,0,0,1,0
0,0,1,0,0
0,1,0,0,0
1,0,0,0,0

は重複として除外して「並び替え前は５つだったけど、並び替えた後は１つ」として「１個」と数えないといけない。

質問者さんは、これを「５つ」と数えてしまう計算式を立ててしまっている。

つまり「条件 x0<=x1<=x2<=x3<=x4 を考慮に入れてない」って結果になってます。

お礼

回答ありがとうございます。

やはりダブリをそのまま数えてしまっていました。
どおりで大きすぎる数になるはずですね。
ダブリが出ないように数え上げるのはかえってたいへんなので、重複順列として数えているわけですね。

とてもわかりやすい解説でした。ありがとうございます。

回答No.2

Tacosan

「0～9の10個から重複を許して5つ選ぶので、一つに数につき10通り選べ、5つあるので10^5通り」の中には
1, 2, 3, 4, 5
とか
5, 4, 3, 2, 1
とかあるよね. これを「小さい順に並べる」と, 同じものになっちゃう.

お礼

なるほど！
すっきりしました。

小さい順に並べるという作業をすることで、かえってダブリが出てしまっていたのですね。

わかりやすい回答ありがとうございます。

回答No.1

oze4hN6x

「一つに数につき10通り選べ、5つあるので10^5通り」は5桁の整数の個数であり、条件 x0<=x1<=x2<=x3<=x4 を考慮に入れていませんね。そこが間違いの原因です。

補足

迅速な回答、大変感謝いたします。

指摘いただいて、ハッとしましたが、まだ完全に理解しきれていません。

＞「一つに数につき10通り選べ、5つあるので10^5通り」は5桁の整数の個数であり、条件 x0<=x1<=x2<=x3<=x4 を考慮に入れていませんね

先に数字を５つ選び、それをあとから小さい順に並べる、という作業を考えてもだめなのでしょうか？
物わかりが悪くてすみません…。