FAQ
RSS
このクイズのヒント
-
ヒント知らないよ
このクイズの参加者（6人）
算数・数学クイズ
算数・数学クイズ
広告
クイズ大陸関連書籍
|
|
ツイート
|
 単語を作ろう
難易度：★
 ぼやき餅
2014/10/15 14:20
「場合の数」の問題を作ってないなぁと思ったのでこんな問題を。
A,B,C,D の4文字を書き並べて文字列を作る。文字は横一列に書き並べる。 同じ文字を何度使ってもよい。ただし、文字列は左からアルファベット順でなければならない。 (AAB、BBBCC、BCD、DDDD などはよいが、 BA、CCBC などはダメ) 以上の条件を満たし、p個の文字から成る文字列を、「長さp の単語」と呼ぶ。 (1) 長さ1の単語、長さ2の単語を列挙(全部挙げる)せよ。 (2) 長さ10の単語の総数を求めよ。 (1)はルール確認、(2)が本題です。 簡単な問題ですがヒント(反転) 左端の文字を消去した時の、残りの長さp−1の単語の構成を考える。
|
回答募集は終了しました。
|
p≧4の場合、
4行p列に並んでいるブロックを考え、 左上のブロックから右または下に移動して右端のブロックに到達する経路の数に等しい。 求める数は、 C(p+2,3)+C(p+1,2)+C(p,1)+C(p-1,0)=(p+1)(p+2)(p+3)/6 p=10の場合、286個となります。 ちなみに1≦p≦3の場合もこの式でOKです。 
一般解を考えてみました。
ぼやき餅
な、なるほど･･･
 その式ならp がある程度大きくなっても求められそうですね。 この発想は無かった 
(1) 長さ1の単語＝4個（A,B,C,D）、長さ2の単語＝ 10個（AA,AB,AC,AD,BB,BC,BD,CC,CD,DD）
(2) 一般的に、長さp の単語の数は、白石Ｐ個、黒石３個を一列に並べる組み合わせの数に等しい。（＝Ｐ+３個から３個選ぶ組み合わせ） （例）白石10個、黒石３個を順に並べ、 ○○○●○●○●○○○○○ なら ＡＡＡ Ｂ Ｃ ＤＤＤＤＤ ●○○○●○○○○○○●○ なら ＢＢＢ ＣＣＣＣＣＣ Ｄ 一般にn個の場合、n*(n-1)*(n-2)/3!個 p=10個の場合、286個
長さ１０にもなればさすがに一般解から解きたいです
 
ぼやき餅
本解では式を単純化してひたすら足し算するという
１．長さ１の単語。A,B,C,D
長さ２の単語。AA,AB,AC,AD,BB,BC,BD,CC,CD,DD ２．長さ１０の単語の総数は２８６
一応 やってみました。
ぼやき餅
正解でーす
(1)
長さ1 … A B C D 長さ2 … AA AB AC AD BB BC BD CC CD DD (2) AとB、BとC、CとDの間に「o」を入れて、A、B、C、Dを「X」に変換すと 「n文字の単語」は「n文字のXと3文字のoを一列に並べる方法」と一対一対応する。 A <-> Xooo D <-> oooX ABCCCD <-> XoXoXXXoX AAACCCCCCCDDDD <-> XXXooXXXXXXXoXXXX よって、「長さnの単語」の総数は、n個の"X"と3個の"o"を一列に並べる組み合わせの総数に等しく、(n+3)C3通り。 「長さ10の単語」の総数は13C3 = 286。
どこかで聞いたような。
ぼやき餅
一応オリジナルですが
一般解から求めてる方ばかりなのでもしかして既出だったか？ 
長さp、かつ、Aで終わる単語の数をApとする。
A1=1、B1=1, C1=1, D1=1 であり、 1以上の自然数nにおいて、 An+1 = An Bn+1 = An+Bn Cn+1 = An+Bn+Cn Dn+1 = An+Bn+Cn+Dn が成り立つ。（ここまで前半） これは階差型の漸化式に展開できます。 An = 1 Bn+1-Bn = An Cn+1-Cn = Bn Dn+1-Dn = Cn
既出、というより、数学的に「解きやすい」良問ということだと思いますよ
 高校数学の問題集にそのまま載っていておかしくないレベルだと思います。 ところで、ぼやき餅さんの意図した解法は、上の囁きの前半部分でしょうか？ だとしたら「階差型漸化式」で一般解を求めることもできるのですが、 これを解くくらいなら n=10までずらずらっと紙に書いたほうが絶対速いですね。
ぼやき餅
はい、まさにその通りなのです。
p=10という設定を選んだのも、紙に書き並べるのがギリギリ面倒じゃないレベルだからという
単語を前半（A,Bの部分）と後半（C,Dの部分）に分ける。
前半と後半の文字数ががそれぞれ 0,10なら単語数は11通り 1,9なら2*10で20通り 2,8なら3*9で27通り 3,7なら4*8で32通り 4,6なら5*7で35通り 5,5なら6*6で36通り 後の部分のパターン数は最初の5ケースと一緒、ゆえに全パターン数は (11+20+27+32+35)*2+36=286パターン 一般の場合、文字数nの時の全パターン数は Σ[k=0,n](k+1)(n-k+1) =Σ[k=0,n]kn-k^2+n+1 =((n^3+n^2)/2)-(n(n+1)(2n+1)/6)+n^2+2n+1
でーきたっ。
ぼやき餅
なるほど、こんな考え方もありましたか
ＡＢとＣＤに分けて考えると
ＡＢの個数の合計がＮ個の時、ＣＤの個数１０−Ｎ（０≦Ｎ≦１０） ＡＢの並べ方Ｎ+１、ＣＤの並べ方１１-Ｎ ＡＢＣＤの並べ方（Ｎ+1）（１１-Ｎ） Ｎ+１＝ｋとおいてｋ（１２-ｋ） １１ Σｋ（１２-ｋ） ｋ＝１ 計算すると２８６
久々に数列使った
ぼやき餅
sqrt-1さんと同様の回答です。
本解はもっと幼稚ですが 数学的にはこの解答の方が良いのかも。
はい、では解答公開したので本解の発表。
〈解説〉 例えば、単語「A ｋｎｎｎｎｎ」を考えます。 これは長さ7の単語です。左端の文字Aを消去すると、 「ｋｎｎｎｎｎ」となり、これは長さ6の単語となります。 この時、左端の文字「ｋ」は、元の単語の先頭の文字がAだったので、 A・B・C・Dのいずれかとなります。 (元の単語が「B ｋｎｎｎｎｎ」の時は、ｋはB・C・Dのいずれか。) このように、長さ6の単語の総数がわかっていれば、長さ7の単語の総数が求められます。 一般の数字pとp−1 に関しても同様で、(以下、kから始まる長さPの単語の総数をkPとする。) AP＝AP−1＋BP−1＋CP−1＋DP−1 BP＝BP−1＋CP−1＋DP−1 CP＝CP−1＋DP−1 DP＝DP−1 が成り立ちます。長さPの単語の総数はAP＋BP＋CP＋DPなので、 上の関係式を使ってひたすら足し算すると、(A1＝B1＝C1＝D1＝1 です。) 長さ10の単語の総数は286個となります。 |
問題へジャンプ