場合の数の問題です。

質問

場合の数の問題です。
場合分けして説くことはできたのですが
（かなり時間がかかりました）
スマートに説く方法はあるのでしょうか。
　　答えは４９２通りだと思います。

問題。
１から６までかかれたカードが１枚ずつ6枚
１から４までかかれた箱が4つある。
１つの箱には２枚までカードを入れられる。
６枚のカードすべてを４個の箱に入れるとき、
カードと箱の番号が全く一致しない入れ方は何通りか？
ただしカードを入れない箱があってもよい。

よろしくお願いします。

回答No.3

nag0720 · ベストアンサー

＃１です。

＃１の方法は計算で求める方法でしたが、場合分けで求めるなら、

まず、５と６のカードが同じ箱に入るか、別の箱に入るかで場合分けします。

同じ箱に入る場合は、１～４の箱の４通り。
１の箱に入った場合は、１のカードが入る箱は２～４の箱の３通り。
１のカードが２の箱に入った場合は、２のカードが入る箱は３～４の箱の２通り。
２のカードが３の箱に入った場合は、
３と４のカードが入る箱の組み合わせは、２－３、４－２、４－３の３通り。
以上から、
４×３×２×３＝７２通り

別の箱に入る場合は、その組み合わせは１２通り。
１と２の箱に入った場合、１と２のカードが入る箱の組み合わせは、
２－１の場合、
３－４、４－３の場合、
３－３、４－４の場合、
２－３、２－４、３－１、４－１の場合
の４パターンあり、それぞれの３と４のカードが入る箱の組み合わせは、
２－１の場合は、４－３の１通り
３－４の場合は、１－２、１－３、２－１、２－３、４－１、４－２、４－３の７通り
３－３の場合は、１－２、２－１、４－１、４－２の４通り
２－３の場合は、１－３、４－１、４－３の３通り
以上から、
１２×（１×１＋２×７＋２×４＋４×３）＝４２０通り

計４９２通り

お礼

二度も丁寧にありがとうございます。

いろいろな解き方がありますね。
三校にさせていただきます。

回答No.2

20080715

確かに答えは492通りですね。
あまりスマートとはいえませんが、包含と排除の原理を使えば、
次のような計算式で答えを出すことは可能です。
(以下では、comb(a,b)は二項係数の意味です。)

Σ[k=0～4]Σ[j=0～2]comb(4,k)*((-1)^k)*(6-k)!*comb(4-k,j)*comb(k+j,2-j)*(1/2)^(4-k-j)
=492.

１つの箱に高々２枚までカードを入れるとき、
4個ある箱のうち、特定の k 箱にその箱と同じ数字のカードが入っているような
入れ方は、x の多項式
(6-k)!*((1+x)^k)*(1+x+x^2/(2!))^(4-k)
を展開したときのx^(6-k)の係数に等しいです。
この係数をf(k)とすると、
f(k)=Σ[j=0～2](6-k)!*comb(4-k,j)*comb(k+j,2-j)*(1/2)^(4-k-j)
とかけます。
そこで包含と排除の原理より、求める場合の数は、
Σ[k=0～4]comb(4,k)*((-1)^k)*f(k) = 492 となります。

お礼

私の説明不足で申し訳ございません
高校数学の範囲で制限時間５分で解けるらしいのです。

この度は解答ありがとうございました。

回答No.1

nag0720

この問題はちょっとやっかいですね。

１つの箱には２枚までという制限だけを考えると、
2-2-2-0のパターンが４通り
2-2-1-1のパターンが６通り
それぞれのカードの入れ方は、
2-2-2-0の場合は、6!/(2!2!2!)=90
2-2-1-1の場合は、6!/(2!2!)=180

ここで、カードと箱の番号が一致しないという条件を加えると、

2-2-2-0の場合
1のカードが1の箱に入る組み合わせの数は、
5!/(2!2!)=30
2のカードが2の箱に入る組み合わせの数、3のカードが3の箱に入る組み合わせの数も同様です。

1のカードが1の箱に入り、2のカードが2の箱に入る組み合わせの数は、
4!/(2!)=12
他の組み合わせも同様

1のカードが1の箱に入り、2のカードが2の箱に入り、3のカードが3の箱に入る組み合わせの数は、
3!=6

カードと箱の番号が一致しない組み合わせの数は、これらを差し引きして、
6!/(2!2!2!)－5!/(2!2!)*3＋4!/(2!)*3－3!=30

2-2-1-1の場合も同様に計算して、
6!/(2!2!)－(5!/(2!)*2+5!/(2!2!)*2)＋(4!+4!/(2!)*4+4!/(2!2!))－(3!*2+3!/(2!)*2)＋(2!)=62

以上から
30*4＋62*6=492

お礼

ありがとうございます。

私が解いた方法よりスマートに解けました。
ただ、制限時間5分で解けるらしいのです。

もし他の方法がありましたらお願いいたします