同じものを含む順列について

今、次の問題を考えているのですが困っています。

「MATHEMATICS」の11文字から4文字を取りだして1列に並べる方法は何通りあるか？

まず2つずつあるM、A、Tをそれぞれ区別して並べると
11P4＝7920通りとなりますよね？

ここからダブっている分を引けば求められると思うのですが
そのダブっている分の出し方がわかりません。

わかる方がおられましたら教えてください。
よろしくお願いします。。

No.2 ベストアンサー 回答者： R_Earl 回答日時： 2008/07/15 03:32

場合分けして、足すのが良いと思います。

[1]
(M, A, T, H, E, I, C, S)の8つから、4文字取り出して並べる方法。
Mは最大1個、Aは最大1個、Tは最大1個しか使わない。

[2-1]
M2個と『(A, T, H, E, I, C, S)の6つのうち、2個』を並べる方法

[2-2]
A2個と『(M, T, H, E, I, C, S)の6つのうち、2個』を並べる方法

[2-3]
T2個と『(M, A, H, E, I, C, S)の6つのうち、2個』を並べる方法

[3-1]
M2個とA2個を並べる方法

[3-2]
A2個とT2個を並べる方法

[3-3]
T2個とM2個を並べる方法

なお、ANo.1の方の解法ではおそらく解けません。
7920通りの文字列の中には、「HEIC」のようにMが含まれないものが存在します。
なので7920÷2を計算すると、「Mのダブり」と共に無関係な文字列まで取り除かれます。

> そのダブっている分の出し方がわかりません。

このダブってる分だけ取り除こうとしても、おそらく場合分けが必要になる気がします。
なので最初から場合分けで解く方法を提示してみました。

もしかしたらもっとスマートな解法があるかもしれません。

この回答へのお礼

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

大変良くわかりました。
はじめからこのように場合分けするとわかりやすいですね。
ありがとうございました！

お礼日時：2008/10/02 06:27

No.4 回答者： 20080715 回答日時： 2008/07/15 15:32

＞ここからダブっている分を引けば求められると思うのですが

そのダブっている分の出し方がわかりません。

ダブっている分を引くという方針で解けば、
11P4-5*4!*7-3*10*4!*3-3*4!*(7/2)-3*10*4!-3*2*5*4!*(3/2)-3*10*4!*(1/2)-3*4!*(3/4)
= 2454 通り(答)　となります。

次のように多項式の展開に帰着させて解く方法もあります。
求める場合の数は 4!*((1+x+x^2/2)^3)*(1+x)^5 の x^4 の係数。
x^4 の係数は、
4!*((1/2)^3)*(comb(11,4)+3*comb(9,4)+3*comb(7,4)+comb(5,4)) = 2454.

この回答へのお礼

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

多項式の展開で解く方法もあるのですね。
やはり、はじめから場合分けする方法が一番簡単な気がするので、今後このような問題を解く際には注意したいと思います。
ありがとうございました！

お礼日時：2008/10/02 06:31

No.3 回答者： himajin100000 回答日時： 2008/07/15 03:46

>今回のように11文字から4文字を取りだす場合でも割ることで

ダブりを取り除くことができるのでしょうか？？

問題文よく読めてなかった。俺の回答は無視してください

No.1 回答者： himajin100000 回答日時： 2008/07/15 02:45

Mだけに注目して考えます

二つのMが区別されていたら,それぞれM1,M2となっていたとして

M1 M2
M2 M1

という組み合わせが考えられます。
この二つの組み合わせを同一としてみるわけですから

2で割ります

7920 / 2 / 2 / 2 ← Mが2個,Aが2個,Tが2個
===============
もしMが3個あったら

M1, M2, M3
M1, M3, M2
M2, M1, M3
M2, M3, M1
M3 ,M1, M2
M3 ,M2, M1
の3! = 6通りが同じ組み合わせとして考えるのであれば

6で割るわけです

この回答へのお礼

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

たとえば「MATHEMATICS」の11文字を1列に並べる方法は何通りあるか？

というような問題の場合だったら、

11!/(2!×2!×2!)　となると思うのですが、

今回のように11文字から4文字を取りだす場合でも割ることで
ダブりを取り除くことができるのでしょうか？？

ありがとうございました。

お礼日時：2008/07/15 03:19