数え上げ　　 　 　　　　　　　　　　　　　　　　　　　　　　　　　　　　

　当ＨＰがいつもお世話になっているＨＮ「攻略法」さんからの出題です。
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　（平成２４年１０月２２日付け）

問題　　ａ が２個、ｍ が１個、ｚ が１個、合計４個の文字があるとき、これら全部を一列に
　　　　並べてできる順列を列挙してください。






































（答）　 (２＋１＋１)！/(２！１！１！)＝１２（通り）で、実際の並びは、

　 1 : a a m z
　 2 : a a z m
　 3 : a m a ｚ
　 4 : a m z a
　 5 : a z a m
　 6 : a z m a
　 7 : m a a z
　 8 : m a z a
　 9 : m z a a
　10 : z a a m
　11 : z a m a
　12 : z m a a

　　　　　　　　　（終り）


　攻略法さんからの続編です。（平成２４年１０月２９日付け）

問題　　文字列acomの部分文字列をすべて列挙してください。


（答）　空文字列、a、ac、aco、acom、c、co、com、o、om、m　（終り）

　これは、「2つに分割して、前側を採用する」。

　acom　→　a.com、ac.om、aco.m、acom.
　com　→　c.om、co.m、com.
　om　→　o.m、om.
　m　→　m.
と
　空文字列

と考えればよい。


類題　　長さnの文字列C₁C₂…C_nの中に、部分文字列は全部で幾つあるかを表す式を求
　　　　めよ。

　　　　　　ここで、空文字列（長さ0の文字列）とC₁C₂…C_n自身も部分文字列とみなす。

　例えば、長さ3の文字列C₁C₂C₃の中に、部分文字列は、

　　C₁、C₂、C₃、C₁C₂、C₂C₃、C₁C₂C₃　及び　空文字列

の7個がある。

（答）　長さnの文字列の中に長さ0の文字列（空文字列）の数は、1個
　　　　長さnの文字列の中に長さ1の文字列の数は、n個
　　　　長さnの文字列の中に長さ2の文字列の数は、n-1個
　　　　長さnの文字列の中に長さ3の文字列の数は、n-2個
　　　　　・・・・・・・・・・
　　　　長さnの文字列の中に長さn-1の文字列の数は、2個
　　　　長さnの文字列の中に長さnの文字列の数は、1個

　　したがって、部分文字列の個数は、

　 　1+n+(n-1)+(n-2)+ … +2+1=1+{n+(n-1)+(n-2)+ … +2+1}=1+n(n+1)/2

　となる。（終り）


　らすかるさんからのコメントです。（平成２４年１０月２９日付け）

　空文字列以外は、C₁〜C_nから重複を許して2個選び、それを始点・終点とすればよいので
求める場合の数は、　１＋_nＨ₂＝１＋ｎ（ｎ＋１）/２　（個）


　攻略法さんからの続編です。（平成２４年１０月３１日付け）

問題　　D、E、I、O、V の５個の異なったものを並べる順列を考え、それらを辞書式に並べ
　　　　る。このとき、１０９番目の文字列は何であろうか。また、文字列IODEVは何番目であ
　　　　ろうか。（ヒント：よく耳にする英単語です。）

（答）　5!=120通りの並びを列挙すると、

　 1:DEIOV 2:DEIVO 3:DEOIV 4:DEOVI 5:DEVIO 6:DEVOI 7:DIEOV 8:DIEVO 9:DIOEV 10:DIOVE
　 11:DIVEO 12:DIVOE 13:DOEIV 14:DOEVI 15:DOIEV 16:DOIVE 17:DOVEI 18:DOVIE 19:DVEIO 20:DVEOI
　 21:DVIEO 22:DVIOE 23:DVOEI 24:DVOIE 25:EDIOV 26:EDIVO 27:EDOIV 28:EDOVI 29:EDVIO 30:EDVOI
　 31:EIDOV 32:EIDVO 33:EIODV 34:EIOVD 35:EIVDO 36:EIVOD 37:EODIV 38:EODVI 39:EOIDV 40:EOIVD
　 41:EOVDI 42:EOVID 43:EVDIO 44:EVDOI 45:EVIDO 46:EVIOD 47:EVODI 48:EVOID 49:IDEOV 50:IDEVO
　 51:IDOEV 52:IDOVE 53:IDVEO 54:IDVOE 55:IEDOV 56:IEDVO 57:IEODV 58:IEOVD 59:IEVDO 60:IEVOD
　 61:IODEV 62:IODVE 63:IOEDV 64:IOEVD 65:IOVDE 66:IOVED 67:IVDEO 68:IVDOE 69:IVEDO 70:IVEOD
　 71:IVODE 72:IVOED 73:ODEIV 74:ODEVI 75:ODIEV 76:ODIVE 77:ODVEI 78:ODVIE 79:OEDIV 80:OEDVI
　 81:OEIDV 82:OEIVD 83:OEVDI 84:OEVID 85:OIDEV 86:OIDVE 87:OIEDV 88:OIEVD 89:OIVDE 90:OIVED
　 91:OVDEI 92:OVDIE 93:OVEDI 94:OVEID 95:OVIDE 96:OVIED 97:VDEIO 98:VDEOI 99:VDIEO 100:VDIOE
　101:VDOEI 102:VDOIE 103:VEDIO 104:VEDOI 105:VEIDO 106:VEIOD 107:VEODI 108:VEOID 109:VIDEO
　110:VIDOE 111:VIEDO 112:VIEOD 113:VIODE 114:VIOED 115:VODEI 116:VODIE 117:VOEDI 118:VOEID
　119:VOIDE 120:VOIED　　（終り）


（コメント）　多少手計算の部分を加味した。

　D****　、E****　、Ｉ****　、O****　は、それぞれ ４！＝２４　（通り）ずつあるので、

あわせて　２４×４＝９６　（通り）

　したがって、１０９番目の文字列は、V****　のタイプである。

　ところで、　VＤ***　、VE***　は、それぞれ ３！＝６　（通り）ずつあるので、

あわせて　６×２＝１２　（通り）　　ここまでで、９６＋１２＝１０８　（通り）

　よって、１０９番目の文字列は、VＩ***　のうち、D、E、O を用いた最初の並びである。

従って、１０９番目の文字列は、VＩDEO　となる。

　また、文字列IODEVについては、D****　、E****　は、それぞれ ４！＝２４　（通り）ずつ

あるので、あわせて　２４×２＝４８　（通り）

　さらに、ＩD***　、IE***　は、それぞれ ３！＝６　（通り）ずつあるので、あわせて

６×２＝１２　（通り）

　よって、文字列IODEVは、　４８＋１２＋１＝６１番目　となる。


　数え上げについて、ＧＡＩ さんからの出題です。（平成２４年１１月１日付け）

問題　　A、A、E、E、I、I、L、L、M、N、O、P、S、S、T、V の同じものを含む１６個のものを並
　　　　べる順列を考え、それらを辞書式に並べる。このとき、466458479240番目の文字列
　　　　は何であろうか。

（ヒント）　よく耳にする英単語です。


　空舟さんからのコメントです。（平成２４年１１月１日付け）

　私が計算機を使いつつ考察すると、答は、plasmatelevision となりました。


　らすかるさんからのコメントです。（平成２４年１１月１日付け）

　A***************： 15!/16個
　E***************： 15!/16個
　I***************： 15!/16個
　L***************： 15!/16個
　M***************： 15!/32個
　N***************： 15!/32個
　O***************： 15!/32個
　PA**************： 14!/16個
　PE**************： 14!/16個
　PI**************： 14!/16個
　PLAA************： 12!/8個
　PLAE************： 12!/4個
　PLAI************： 12!/4個
　PLAL************： 12!/8個
　PLAM************： 12!/8個
　PLAN************： 12!/8個
　PLAO************： 12!/8個
　PLASA***********： 11!/4個
　PLASE***********： 11!/2個
　PLASI***********： 11!/2個
　PLASL***********： 11!/4個
　PLASMAE*********： 9!/2個
　PLASMAI*********： 9!/2個
　PLASMAL*********： 9!/4個
　PLASMAN*********： 9!/4個
　PLASMAO*********： 9!/4個
　PLASMAS*********： 9!/4個
　PLASMATEE*******： 7!/2個
　PLASMATEI*******： 7!個
　PLASMATELEI*****： 5!個
　PLASMATELEN*****： 5!/2個
　PLASMATELEO*****： 5!/2個
　PLASMATELES*****： 5!/2個
　PLASMATELEVII***： 3!個
　PLASMATELEVIN***： 3!個
　PLASMATELEVIO***： 3!個
　PLASMATELEVISINO： 1個
　PLASMATELEVISION： 1個　　　計 466458479240個

　よって、466458479240番目は、PLASMATELEVISIONですね。


　
　ＧＡＩ さんからの再出題です。（平成２４年１１月２日付け）

問題　　a、a、e、e、i、i、l、l、m、n、o、p、s、s、t、v　の１６枚のカードを何枚でもよいから並
　　　　べ異なる単語を作るとする。さて何種類の単語を構成することが可能か？
　　　（単に異なる順列がいくつできるかと考えて下さい。）


　らすかるさんからのコメントです。（平成２４年１１月２日付け）

　Σ_n=1〜16Σ_{p=max(n-11,0)〜min(floor(n/2),5) 5}C_p・_11-pC_n-2p・n!/２^p=1814751099426（種類）


　ＧＡＩ さんからのコメントです。（平成２４年１１月２日付け）

　ご明算です。イヤーすばらしい!!! 一つの式にされたのには驚きました。この式を追いかけ
てみると、単語の長さ別に作られる個数が

　単語の長さ：１・・・11個
　単語の長さ：２・・・115
　単語の長さ：３・・・1140
　単語の長さ：４・・・10680
　単語の長さ：５・・・94140
　単語の長さ：６・・・776340
　単語の長さ：７・・・5947200
　単語の長さ：８・・・41945400
　単語の長さ：９・・・269325000
　単語の長さ：１０・・1551652200
　単語の長さ：１１・・7868599200
　単語の長さ：１２・・34203708000
　単語の長さ：１３・・122594472000
　単語の長さ：１４・・340540200000
　単語の長さ：１５・・653837184000
　単語の長さ：１６・・653837184000

の内分けが見えてきました。


　攻略法さんからの続編です。（平成２４年１１月２日付け）

問題　　g、i、r、l の４文字を使って、長さ 0、1、2、3、4 の文字列をつくる。何通りあるか。

　例　g、i、gr、rg、gir、gri、rgi、 ．．．など。

（答）　長さ0は、空文字の1通り
　　　　長さ1は、g、i、r、lと選んで、1+1+1+1=4通り
　　　　長さ2は、gi、gr、gl、ir、il、rlと選び、その並べ方を考慮して、2!+2!+2!+2!+2!+2!=12通り
　　　　長さ3は、gir、gil、grl、irlと選んで、3!+3!+3!+3!=24通り
　　　　長さ4は、girlと選んで、4!=24通り

　　よって、1+4+12+24+24=65通り　　（終り）

（別解）　(1+ｘ)ⁿのｘ^kの係数に着目して、二項展開から、Σ_{k=0〜n ｎ}C_ｋ・ｋ！
　　　　　n=4として、1・0!+4・1!+6・2!+4・3!+1・4!=65通り　　（終り）


　らすかるさんからのコメントです。（平成２４年１１月２日付け）

　長さｋのとき、4文字からk文字とって並べる順列なので、Σ_{k=0〜4 4}P_k=65

　一般の文字数nで、

　　Σ_k=0〜n ｎPk=Σ_k=0〜n n!/(n-k)!=Σ_k=0〜n n!/k!=n!Σ_k=0〜n 1/k!=[e*n!]


　攻略法さんからの続報です。（平成２４年１１月３日付け）

（別解）　長さ0は、空文字列の1通り

　次に、4文字を1列に並べる順列から、それぞれの部分文字列を考える。

　長さ1、2、3、4は、

　 1: gilr　→ g,gi,gil
　 2: girl　→ gir
　 3: glir　→ gl,gli
　 4: glri　→ glr
　 5: gril　→ gr,gri
　 6: grli　→ grl
　 7: iglr　→ i,ig,igl
　 8: igrl　→ igr
　 9: ilgr　→ il,ilg
　10: ilrg　→ ilr
　11: irgl　→ ir,irg
　12: irlg　→ irl
　13: lgir　→ l,lg,lgi
　14: lgri　→ lgr
　15: ligr　→ li,lig
　16: lirg　→ lir
　17: lrgi　→ lr,lri
　18: lrig　→ lrg
　19: rgil　→ r,rg,rgi
　20: rgli　→ rgl
　21: rigl　→ ri,rig
　22: rilg　→ ril
　23: rlgi　→ rl,rlg
　24: rlig　→ rli

よって、1+4+12+24+24=65通り　　（終り）

（別解）　順列 F(g,i,r,l)=(g+i+r+l)! として、

　　　Σ_g=0〜1Σ_i=0〜1Σ_r=0〜1Σ_l=0〜1F(g,i,r,l)=65（通り）

（g、i、r、lの値は、2*2*2*2=16通り（=1+4+6+4+1）を計算する）　　（終り）


類題　　a、a、m、zの4文字を使って、長さ0,1,2,3,4の文字列をつくる。何通りあるか。

（答）　長さ0は、空文字列の1通り
　　　　長さ1、a、m、zと選んで、1+1+1=3通り
　　　　長さ2、aa、am、az、mzと選んで、1+2!+2!+2!=7通り
　　　　長さ3、aam、aaz、amzと選んで、3!/(2!1!)+3!/(2!1!)+3!=3+3+6=12通り
　　　　長さ4、aamzと選んで、4!/(2!1!1!)=12通り

　　よって、1+3+7+12+12=35通り　　（終り）

（別解）　長さ0は、空文字列の1通り

　長さ1,2,3,4は、

　 1 : aamz　→ a,aa,aam
　 2 : aazm　→ aaz
　 3 : amaz　→ am,ama
　 4 : amza　→ amz
　 5 : azam　→ az,aza
　 6 : azma　→ azm
　 7 : maaz　→ m,ma,maa
　 8 : maza　→ maz
　 9 : mzaa　→ mz,mza
　10 : zaam　→ z,za,zaa
　11 : zama　→ zam
　12 : zmaa　→ zm,zma

よって、1+3+7+12+12=35通り　　（終り）

（別解）　同じものを含む順列 F(a,m,z)=(a+m+z)!/(a!m!z!) として、

　　　Σ_a=0〜2Σ_m=0〜1Σ_z=0〜1F(a,m,z)=35通り

　　　（a,m,zの値は、3*2*2=12通りを計算する）　　（終り）


　攻略法さんからの続報です。（平成２４年１１月７日付け）

　I like” ピラミッド算”

マジック編　　3個の数1,2,3として、1番下の数8を当てる。

バトル編　　4個の数の場合、1から4までの数とする。

（考察）　高校生のお兄さん、お姉さんに聞いてみよう。最大値、最小値が解るかも!?おねえ
　　　　さんなら、4!通りを検証してみるね♪　（終り）


　攻略法さんからの続報です。（平成２４年１１月８日付け）

　いくつか特別の並びについて、高校生のお兄さん、お姉さんに聞いてみた。

等差数列　　初項a、公差d、項数nの数列を考える。具体的に見てみると、

　a 　a+d 　a+2d 　a+3d 　a+4d
　 2a+d 2a+3d 　2a+5d  2a+7d
　　 4a+4d  4a+8d 　4a+12d
　　　　8a+12d  8a+20d
　　　　　　16a+32d

となる。1番下の数は、16a+32d=8{a+(a+4d)}　と初項と末項を使って表すことができる。

　また、項数nにおける1番下の数は、上記の三角形の1列目に現れる。

　すなわち、　n=1なら、a=a　　　n=2なら、2a+d=1{a+(a+d)}

　　　　　　　　　n=3なら、4a+4d=2{a+(a+2d)}　　　n=4なら、8a+12d=4{a+(a+3d)}

である。一般的に、初項a、公差d、項数nの数列を考えると、並びは、

　　a　a+d　a+2d　a+3d　…　a+(n-2)d　a+(n-1)d

となる。1番下の数は、初項と末項を使って、(a+{a+(n-1)d})・2^n-2　と表せる。

　すなわち、並びを、　a[1]　a[2]　a[3]　a[4]　…　a[n-1]　a[n]　と表現すれば、1番下の数は

　　　(a[1]+a[n])・2^n-2

となる。ｎが奇数の場合、真ん中の数a[(n+1)/2]は、{a+(a+(n-1)d)}/2=a+d(n-1)/2　なので、

　　{a+d(n-1)/2}・2^n-1=a[(n+1)/2]・2^n-1


等比数列　　初項a、公比r、項数nの数列を考える。具体的に見てみると、

　a　　　ar　　　　ar^2　　　ar^3　　　　ar^4　　　ar^5
　　a(1+r)　ar(1+r)　ar^2(1+r)　ar^3(1+r)　ar^4(1+r)
　　　a(1+r)^2　ar(1+r)^2　ar^2(1+r)^2 ar^3(1+r)^2
　 　　　　a(1+r)^3 　ar(1+r)^3 　ar^2(1+r)^3
　　　　　　　　a(1+r)^4 　ar(1+r)^4
　　　　　　　　　　　a(1+r)^5

となる。また、項数nにおける1番下の数は、上記の三角形の1列目に現れる。

　すなわち、　n=1なら、a　　n=2なら、a(1+r)　　n=3なら、a(1+r)^2

　　　　　　　　n=4なら、a(1+r)^3　　n=5なら、a(1+r)^4

である。一般的に、初項a、公比r、項数nの数列を考えと、並びは、

　　a　ar　ar^2　ar^3　…　ar^(n-2)　ar^(n-1)

となる。1番下の数は、a(1+r)^(n-1)　と表せる。


フィボナッチ数列

　1,1,2,3,5,8,13,21,34,55,89,144,… の場合、項数nなら、F[2n-1]


　攻略法さんからの続報です。（平成２４年１１月１４日付け）

　４つの数が、「1、2、3、4」　なら、

　1 3 4 2
　 4 7 6
　 11 13
　  24

が最大値となる。他に、「1432」、「2341」、「2431」がある。

　3 1 2 4
　 4 3 6
　  7 9
　  16

が最小値となる。他に、「3214」、「4123」、「4213」 がある。


　４つの数を「L、I、K、E」とすると、
　L　 　I 　　 K　　 ∈
　 L+I   I+K   K+E
　 L+2I+K  I+2K+E
　   L+3I+3K+E

なので、最大（最小）にするには係数が大きいところに大きな数（小さな数）を入れればよい。

　（閑話休題）

格子状の経路の道順を考える。

L　 I　   K　 ∈
＼／＼／＼／
　 ＼／＼／
　　  ＼／
　　  　T

（１）　地点Lから地点Tへの最短経路は何通り？
（２）　地点Iから地点Tへの最短経路は何通り？
（３）　地点Kから地点Tへの最短経路は何通り？
（４）　地点Eから地点Tへの最短経路は何通り？

答え　それぞれ　1、3、3、1通り　　（終り）

　L+3I+3K+E　の係数の並びは上記の値と一致している。それはパスカルの三角形である。

　　 　 1
　 　 1  1
　  1  2  1
　1 　3　 3　 1