順列と組み合わせ？

質問

情報処理関係の問題で、以下の問題があるのですが、こういった計算問題が苦手なので、解放の仕方をご教授いただければ助かります。
よろしくお願いいたします。

2種類の文字“X”，“Y”を1個以上，最大n個並べた符号を作る。60通りの符号を作るときのnの最小値は幾らか。

回答No.7

info22 · ベストアンサー

X,Yから１つとる(符号長1の)順列(2P1)=2
X,Y

X,Yから２つ並べる(符号長2の)順列(2P1)^2=2^2
XX,XY,YX,YY

X,Yから3つ並べる(符号長3の)順列(2P1)^3=2^3
XXX,YYY,XXY,XYX,YXX,XYY,YXY,YYX
．．．
X,Yからn個並べる(符号長nの)順列(2P1)^n=2^n

したがって
符号長1～nまでの符号数の和は等比数列の和となるから
2+2^2+2^3+ ... +2^n = 2{(2^n)-1}/(2-1) =2{(2^n)-1}
nの最小値は以下の不等式を満たす最小のnになります。
2{(2^n)-1}≧60
から
(2^n)-1≧30
2^n≧31

n=5で2^n=32,n=4で2^n=16なので最小のnは
n=5
と求まります。

お礼

ありがとうございます。
なるほどよくわかりました。

回答No.8

arrysthmia

No.7 の方法で 60 種類の符号が表現できるためには、
“X”，“Y”の 2 種類の文字だけでなく、
“X”，“Y”，区切り の 3 種類の文字が必要です。

お礼

ありがとうございます。

回答No.6

arrysthmia

符号が固定長なら、2^n ≦ 60 であればよいのだから、最小の n は 6。
文字の種類 M が多ければ、M^n - 60 の差を活用して、一部の符号の
文字数を減らすことができる。「最大n個並べた符号」の「最大」には、
その辺の含みがあると思われるが、文字が２種類では、頭語条件の為に
かえって増えるビット数のほうが多いから、固定長にしておくほうが
符号の最大字数は小さくて済む。

お礼

ありがとうございます。

回答No.5

wacchin

あ、間違えました・・・

「求めるのは最大値が60を超える最小のｎを求めればよい。」
のではなく
「和が60を超える最小のｎを求めればよい。」
ですね（汗）
ですから、
　　　　　　　　n！　　　
Σ(k=0,n)　―――――――
　　　　　　　k！(n-k)！
を考えなくてはいけません

n=1のとき２
n=2のとき４
・
・
・
n=5のとき３２
n=6のとき６４

となるので求める最小値は　ｎ=６　ですね。

お礼

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

回答No.4

chie65536（@chie65535）

因みに、文字の種類が何種類でも、考え方は同じ。

2種類の文字“X”，“Y”⇒２進数で何桁になるか考える

3種類の文字“X”，“Y”，“Z”⇒３進数で何桁になるか考える

4種類の文字“W”，“X”，“Y”，“Z”⇒４進数で何桁になるか考える
（中略）
9種類の文字“R”，“S”，“T”，“U”，“V”，“W”，“X”，“Y”，“Z”⇒９進数で何桁になるか考える

10種類の文字“Q”，“R”，“S”，“T”，“U”，“V”，“W”，“X”，“Y”，“Z”⇒１０進数で何桁になるか考える

「情報処理」とは、このような「問題文に書かれた情報を読み取り、解を求めるのに最も簡単な方法が使えるよう、読み取った情報を変換する処理」の事を言います。

「解を求める」のが情報処理の本質なのではなく「情報を変換する」のが情報処理の本質なのです。

そして「正しい方向に情報を変換する」をある程度の回数繰り返すと「もう変換できない状態」になり、その「もう変換できない状態が、求めたい解そのもの」になります。これを「情報処理」と言います。

お礼

ありがとうございます。

回答No.3

wacchin

この問題は、XとYをあわせてｎ個並べるということですよね？
それともXとYをそれぞれｎ個ずつということですか？
前者と見て解きます。

XとYの個数を
X：ｋ個
Y：ｎ-ｋ個　　　（ただし、0≦ｋ≦ｎ）

ここでXとYの並び方は、

　　　　n！　　　
―――――――
　　k！(n-k)！

これの最大値が60を超える最小のｎを求めればよい。
ここで、最大値をとるとき

k=　n/2 (nが偶数のとき)
　 (n±1)/2 (nが奇数のとき)

は明らかであるから、それを考慮に入れて、
n=1のとき最大値は１
n=2のとき最大値は２
・
・
・
n=7のとき最大値は35
n=8のとき最大値は70

以上より
求めるｎの値は n=8

数値代入法になってしまうのが煩わしいですが・・・

お礼

ありがとうございます。

回答No.2

chie65536（@chie65535）

＞2種類の文字“X”，“Y”を1個以上，最大n個並べた符号を作る。60通りの符号を作るときのnの最小値は幾らか。

この問題は「１０進数で０から５９までの６０個の数値を２進数で表わすには、最低、何ビットの２進数が必要か」と言っているのと同じです。

２進数１桁⇒並べる数ｎが１の時、最大２通りの符号が作れる⇒６０通りには不足
２進数２桁⇒並べる数ｎが２の時、最大４通りの符号が作れる⇒６０通りには不足
２進数３桁⇒並べる数ｎが３の時、最大８通りの符号が作れる⇒６０通りには不足
２進数４桁⇒並べる数ｎが４の時、最大１６通りの符号が作れる⇒６０通りには不足
２進数５桁⇒並べる数ｎが５の時、最大３２通りの符号が作れる⇒６０通りには不足
２進数６桁⇒並べる数ｎが６の時、最大６４通りの符号が作れる⇒６０通り以上作れる

という訳で「ｎの最小値は６」が答え。

順列も組み合わせも不要です。

てゆーか、こんな風に複雑に考えなくても、問題文は「１０進数の５９は、２進数で何ビットになるか」と言っているのと同じですから

５９(１０進)＝１１１０１１(２進)

で、６ビットになりますから、答えは「ｎの最小値は６」になります。

お礼

ありがとうございます。

回答No.1

kobold

2種類の文字“X”，“Y”を1個以上，最大n個並べた符号の通りをa_nと置いて漸化式を作ってみたら？

お礼

ありがとうございます。