4
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 1 year has passed since last update.

重複数に上限がある場合の重複組合せを1回の計算で解ける場合

Last updated at Posted at 2021-08-13

 重複数に上限がある場合の重複組合せにおいて、特殊なケースでは計算が簡単になるよという話。https://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q10113338515 を見て知った解法ですが、僭越ながら回答者さんの説明が少し分かりづらいかなと思ったので、自分の中での噛み砕きも兼ねて整理。

 問題は以下のような感じ。

\displaylines{
「200個の区別のないボールを、A,B,Cの3箱に入れる。\\
ただし、それぞれの箱にボールは100個までしか入らない。\\
ボールの入れ方は何通りか。」\\
\\}

解1(包除原理)

 これが正攻法になると思います。上限数がないすべての場合から、上限数を超えた場合を除きます。

_3H_{200}-3\times_3H_{99}\\
=5151

解2(特殊ケース)

 少しテクニカルになります。最初にすべての箱に100個ずつ入ってる(つまり合計300個)と考え、そこからの100個抜き出す場合の抜き出し方を考えます。

_3H_{100} = 5151

 なんと1回の計算で解けてしまいました。

解2が成り立つケースは?

 $n$種類のものから$r$個を選び、各上限が$m$のとき、「抜き出す数」が$m$を超えると上の解法は破綻します。100個入の箱から101個のボールを取り出すことはできないので。

 さて、抜き出す数は$nm-r$となるため、

\displaylines{
nm-r \leq m\\
r \geq (n-1)m}

 $r$の上限は$nm$であることを考えると、

(n-1)m\leq r \leq nm

 つまり、解2は$r$が上の範囲でのみ成り立つことがわかります。

4
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
4
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?