問題14936・・・やどかりさんのブログ https://blogs.yahoo.co.jp/oka_yadokary/38173611.html#38173611 より Orz〜
(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-1Ck・(n−k)!=(n−1)!・(n−k)/k!
Sの要素を含む順列を減じると n!−n-1C1・(n−1)!=(n−1)! 通り、
Sの要素2個を含む順列は2回減じられているので加えると
(n−1)!+(n−1)!・(n−2)/2! 通り、
Sの要素3個を含む順列は 3C1=3回減じ、3C2=3回加えられているので、再度減じ、
(n−1)!+(n−1)!・(n−2)/2!−(n−1)!・(n−3)/3! 通り、
Sの要素4個を含む順列は 4C1=4回減じ、4C2=6回加え、4C3=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 個 です。
*撃沈...^^;;
[解答2]に気付けなかったのが敗因...^^;;
|