重複順列nΠr≧順列nPr≧組合せnCr

にゃんこ先生といいます。

異なるn個の物からr個を取る。

この取るという動作には、重複を許すやり方と許さないやり方があります。

また、取った後の動作には、並べる方法と組合せにする方法があります。

全部で２＊２＝４つのバージョンが考えられます。

順列nPr=n!/(n-r)!
組合せnCr=n!/(n-r)!r!
重複順列nΠr=n^r
重複組合せnHr=n+r-1Cr=(n+r-1)!/(n-1)!r!

ここで、一般に
重複順列nΠr≧順列nPr≧組合せnCr
が成り立ちますが、nHrとの大小関係はどうなるのでしょうか？

二変数関数としての場合分けが必要とは思うのですがよくわかりません。

No.3 回答者： naniwacchi 回答日時： 2011/04/11 23:24

#2です。

数式の証明はできていないのですが、場合分けは以下のようになりそうです。
（n≧ rということを考慮して）

・n≦ 3 または (n, r)＝ (4, 4), (5, 5)のとき、nＰr≦ nＨr
・上記以外のとき、nＰr≧ nＨr

等号が成立するのは、
・r＝ 1のとき（nはいくつでもよい）　←これは数式で示せます。
・(n, r)＝ (3, 2)のとき

No.2 回答者： naniwacchi 回答日時： 2011/04/10 21:05

#1です。

勘違いをしていました。

＞まず、nＨr＝ (n+r-1)Ｃrと書き下せるので、nＨr≧ nＣrであることが言えます。
ここまではいいと思うのですが、次に nＰrとの比較をしなければなりませんでした。

考え直します。。。

No.1 回答者： naniwacchi 回答日時： 2011/04/10 16:51

こんにちわ。

比較的簡単に求められるかもしれません。

まず、nＨr＝ (n+r-1)Ｃrと書き下せるので、nＨr≧ nＣrであることが言えます。


となると、あとは、nΠrとの大小比較になりますが、
nを固定して数学的帰納法を用いれば nΠr≧ nＨrと示せそうです。

[i] r＝ 1のときは、明らかに nΠr＝ nＨr

[ii] r＝ kのとき nΠk≧ nＨkが成り立つと仮定。
r＝ k+1のとき
nΠ(k+1)- nＨ(k+1)
≧ n* nＨk- nＨ(k+1)
＝ ・・・

計算すると上記の差は 0以上になることが示されるので、
r＝ k+1でも nΠk≧ nＨkが成り立つと言えます。


結果、
nΠr≧ nＨr≧ nＰr≧ nＣr

となります。
ざざっと計算したので、計算間違いをしてたらすみません。＾＾；