FC2ブログ

Welcome to my blog

[答1153] 隣り合う文字が並ばない順列

ヤドカリ

ヤドカリ


'


[答1153] 隣り合う文字が並ばない順列


 (1) A,B,C,D すべてを並べてできる文字列 4! 個のうち、

   AB,BC,CD を含まないものは何個?

 (2) A,B,C,D,E すべてを並べてできる文字列 5! 個のうち、

   AB,BC,CD,DE を含まないものは何個?

 (3) A,B,C,D,E,F すべてを並べてできる文字列 6! 個のうち、

   AB,BC,CD,DE,EF を含まないものは何個?

 (4) A,B,C,D,E,F,G,H,I,J すべてを並べてできる文字列 10! 個のうち、

   AB,BC,CD,DE,EF,FG,GH,HI,IJ を含まないものは何個?


[解答1]

 一般に、文字数をn個とすれば順列の総数は n! 通り、

 隣り合う2文字の文字列の集合 S={AB,BC,CD,DE,……}の要素は (n-1)個あって、

 Sの要素k個を含む順列は n-1k・(n-k)!=(n-1)!・(n-k)/k!

 Sの要素を含む順列を減じると n!-n-11・(n-1)!=(n-1)! 通り、

 Sの要素2個を含む順列は2回減じられているので加えると

  (n-1)!+(n-1)!・(n-2)/2! 通り、

 Sの要素3個を含む順列は 31=3回減じ、32=3回加えられているので、再度減じ、

  (n-1)!+(n-1)!・(n-2)/2!-(n-1)!・(n-3)/3! 通り、

 Sの要素4個を含む順列は 41=4回減じ、42=6回加え、43=4回減じられているので、更に加え、

  (n-1)!+(n-1)!・(n-2)/2!-(n-1)!・(n-3)/3!+(n-1)!・(n-4)/4! 通り、

 ………… です。

 (1) 3!+3!・2/2!-3!・1/3!=6+6-1=11 通り。

 (2) 4!+4!・3/2!-4!・2/3!+4!・1/4!=24+36-8+1=53 通り。

 (3) 5!+5!・4/2!-5!・3/3!+5!・2/4!-5!・1/5!!=120+240-60+10-1=309 通り。

 (4) 9!+9!・8/2!-9!・7/3!+9!・6/4!-9!・5/5!+9!・4/6!-9!・3/7!+9!・2/8!-9!・1/1!

   =362880+1451520-423360+90720-15120+2016-216+18-1=1468457 通り。


[解答2]

 (1) ACBD,ADCB,BADC,BDAC,BDCA,CADB,CBAD,CBDA,DACB,DBAC,DCBA の 11個です。

 (2) (1)の 11個について、最初,最後,文字の間3ヶ所の、計5ヶ所のうち、

   Dの直後以外の場所に Eを挿入するか、

   (1)で ABDC,ACDB,ADBC,BACD,BCAD,CABD,CDBA,DBCA,DCAB の 9個のように、

   AB,BC,CD を1つだけ含むものは、その間に Eを挿入するか、

   ですので、11・4+9=53 個です。

   なお、(1)と同様、1,3,5,7 すべてを並べてできる文字列のうち、

   13,35,57 を含まないものも 11個あります。

   文字列の 1 の直後に 2 ,3 の直後に 4 ,5 の直後に 6 ,7 の直後に 8 の

   いずれか1つだけを挿入し、小さい数字から順に A,B,C,D,E に書き換えると、

   A,B,C,D,E すべてを並べてできる文字列のうち、AB,BC,CD,DE を1つだけ含むものが

   11・4 個であることが分かります。

 (3) 53・5+11・4=309 個です。

 (4) Gまで:309・6+53・5=2119 個 ,Hまで:2119・7+309・6=16687 個 ,

   Iまで:16687・8+2119・7=148329 個 ,Jまで:148329・9+16687・8=1468457 個 です。

.

スポンサーサイト



Comments 14

There are no comments yet.
ひとりしずか  
No title

わぁ~実がいっぱい!
青い空に心地よさそう~

ゆうこ つれづれ日記  
No title

おはようございます。
何の実かしら?
鳥たちのご馳走ですね。
美味しそう~~~

寒いですね。
インフルエンザも流行りだしているので気をつけたいです。

スモークマン  
No title

グーテンターク ^^
そっか...^^;
4文字のときからして間違ってましたわ...
[解答2]には気づきたかったです...^^;; Orz~

ニリンソウ  
No title

大きな木なんでしょう!
冬空にこの実を見たような気がするんですよ
思い出せませんが。

樹☆  
No title

こんにちは
センダンの実でしょうか?
葉も落ち冬を感じますね。

今年も半月となり、気持ちだけ
焦り気味です。笑

ヤドカリ  
No title

ひとりしずかさん、早速のコメントとナイス!をありがとうございます。
センダンの実がたくさん見えました。
青空を見上げて撮りたいと思っていたのですが、天気に恵まれました。

ヤドカリ  
No title

ゆうこさん、早速のコメントとナイス!をありがとうございます。
センダンの花は夏前に咲きますが、葉は落ちた後の実の方が目立ちます。
ところで、明日からまた寒くなるそうです。
お互い健康には気を付けないといけませんね。

ヤドカリ  
No title

スモークマンさん、コメントとナイス!をありがとうございます。
[解答2]の方が考えやすいかも知れません。
ちょっと条件が付くだけで問題が面白くなりますね。

ヤドカリ  
No title

ニリンソウさん、コメントとナイス!をありがとうございます。
センダンの樹は高くて、写真を撮るのが難しいですが、
長居植物園には撮りやすい樹があり、毎年撮ります。

ヤドカリ  
No title

樹ちゃん、コメントとナイス!をありがとうございます。
仰る通り、センダンの樹の実です。
葉が落ちていると青空によく映えます。
ところで、今年もあと半月、早いですね。

POPS  
No title

こんばんは。
これは何の実でしょうか。
青空に向かって沢山成ってますね~。
形はギンナンぽくも見えますね。
ナイス

ヤドカリ  
No title

POPSさん、コメントとナイス!をありがとうございます。
センダンという樹の実です。
夏前に花が咲きますが、葉が落ちた後の実の方が目立ちます。

アキチャン  
No title

おはようございます。
センダンが出てきませんでした(笑)
青空に気持ちよさそうですね(o^-^o)

ヤドカリ  
No title

アキチャンさん、コメントとナイス!をありがとうございます。
センダンの実が見事についていました。
青空の下だと、見ている方も気持ちいいですね。