場合の数について質問させてください。

質問

場合の数について質問させてください。

以下のような文字列は全部で何種類あるか？

（質問その１）================

条件
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
★「a,b,c,d,e......,z」（小文字のアルファベット。全部で２６個）
「0以上9以下の整数」（全部で１０個）
「．」（ピリオド）（１個）
の、計３７個の文字（以下、「文字」と呼ぶとき、0から９とか記号も含むこととします）から、ｎ個の文字を選び、文字列を形成する
★文字列中に同じ文字が複数回登場しても構わない。

★文字列の最初に記号（この場合はピリオド）をおいてはいけない
★文字列の最後にも記号（この場合はピリオド）をおいてはいけない
★文字列の中で、記号（この場合はピリオド）が連続してはいけない
★文字列を形成する文字が、「すべて数字」であってはいけない
　（つまり、ｎ個の文字のうち、１個以上、「小文字アルファベットまたはピリオド」が含まれなければいけない）
　（ちなみに、「073754555555」みたく、一番左が０でも【「すべて数字」】ならだめです）
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

なお、これらを満たす文字列すべてを要素とする集合をX_1と呼ぶことにします。
また、X_1に属する要素の総数を、f(X_1,n)とよぶことにします。
（後述の、別の集合についてもおなじく）

で・・・。
★k=1,2,3,4,5,6のそれぞれの場合について、f(X_1,k)はいくつ？

あと、できれば、
★一般項（？）、つまり、f(X_1,n)も知りたいです。

（質問その２）================

（質問その１）の条件の、一番上を変更し、
「A,B,C,D,E,F....Z」（大文字のアルファベット。全部で２６個）
も使っていいこととします。（つかわなくてもOK)

で、そうすると、計６３個の文字から、ｎ個の文字を選び、文字列を形成することになります。

このとき（他の条件は全部同じ）、
これらを満たす文字列すべてを要素とする集合をX_2と呼ぶことにします。

で・・・。
★k=1,2,3,4,5,6のそれぞれの場合について、f(X_2,k)はいくつ？

あと、できれば、
★一般項（？）、つまり、f(X_2,n)も知りたいです。

（質問その３）================

質問その１の「．」（ピリオド）を、「-」（ハイフン）に変更します。
他の条件は全て同じとします。

で、全部の条件を満たす文字列すべてを要素とする集合をYと呼ぶことにします。

で・・・、
f(Y,n)=f(X_1,n)であることはわかります。

でもって・・・

★k=1,2,3,4,5,6のそれぞれの場合について、f( (X_1∪Y) ,k)はいくつでしょうか？

あと、できれば、
★一般項（？）、つまり、f( (X_1∪Y) ,n)も知りたいです。

＝＝＝

同じように、
★k=1,2,3,4,5,6のそれぞれの場合について、f( (X_2∪Y) ,k)はいくつでしょうか？

あと、できれば、
★一般項（？）、つまり、f( (X_2∪Y) ,n)も知りたいです。

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
以下、参考までに（関係ないのも含まれてるかもしれませんが）

●「p=10,26,11,27とか・・・、k=1,a2,3,4,5,6」について、

p^k、p_C_k の値を計算しておきました。
↓
http://spreadsheets.google.com/pub?key=0AqIQfyJXnDwXdHBNcFZMNXVpS29Dcm10OWFjU3hqSGc&hl=en&output=html

また、素因数分解すると・・・
●10=2*5
●11は素数(=1+10)
●22=2*11(=(1+10)*2)
●26=2*13
●27=3^3(=1+26)
●36=(2^2) * (3^2)(=10+26)
●37は素数(=1+10+26)
●52=(2^2) * 13(=26*2)
●63=(3^2) * 7(=1+10+26*2)
●100=(2^2)*(5^2)(={1+10+26}+{1+10+26*2}=37+63)

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

よろしくお願いいたします。

回答No.1

nag0720

おもしろそうだったので（質問その１）だけ回答します。

一般的に、条件A,Bがあり条件Aを満たす数をn(A)のように表すとすると、
n(A∪B)=n(A)+n(B)-n(A∩B)
が成り立ちます。

条件がA,B,C,Dの４つある場合は、
n(A∪B∪C∪D)=n(A)+n(B)+n(C)+n(D)-n(A∩B)-n(A∩C)-n(A∩D)-n(B∩C)-n(B∩D)-n(C∩D)+n(A∩B∩C)+n(A∩B∩D)+n(A∩C∩D)+n(B∩C∩D)-n(A∩B∩C∩D)
が成り立ちます。

n個の文字列に対する条件A,B,C,Dを、
条件A:最初がピリオドである
条件B:最後がピリオドである
条件C:ピリオドが連続している
条件D:すべて数字である
とすると、条件Dは、条件A,B,Cと相反する条件なので、
n(A∪B∪C∪D)=n(A)+n(B)+n(C)+n(D)-n(A∩B)-n(A∩C)-n(B∩C)+n(A∩B∩C)
が成り立ちます。

求める場合の数f(X_1,n)は、
f(X_1,n)=37^n-f(A∪B∪C∪D,n)
=37^n-{f(A,n)+f(B,n)+f(C,n)+f(D,n)-f(A∩B,n)-f(A∩C,n)-f(B∩C,n)+f(A∩B∩C,n)}
で計算できます。

f(A,n)=f(B,n)=37^(n-1)　　（n≧1）

f(C,1)=0
f(C,2)=1
f(C,3)=73
f(C,n)=37*f(C,n-1)-36*f(C,n-3)+36*37^(n-3)　　（n≧4）

f(D,n)=10^n　　（n≧1）

f(A∩B,1)=1
f(A∩B,n)=37^(n-2)　　（n≧2）

f(A∩C,1)=f(B∩C,1)=0
f(A∩C,n)=f(B∩C,n)=f(C,n)-36*f(C,n-1)　　（n≧2）

f(A∩B∩C,1)=0
f(A∩B∩C,2)=1
f(A∩B∩C,n)=f(C,n)-72*f(C,n-1)+36^2*f(C,n-2)　　（n≧3）

より、

f(X_1,n)=37^n-{f(A,n)+f(B,n)+f(C,n)+f(D,n)-f(A∩B,n)-f(A∩C,n)-f(B∩C,n)+f(A∩B∩C,n)}
=1296*37^(n-2)-10^n-36^2*f(C,n-2)

f(C,n)が漸化式になっていますが、もしf(C,n)の一般解を求めることができれば、
f(X_1,n)の一般解が求まります。

なお、f(C,n)とf(X_1,n)（n≦6）は下記のとおりです。

f(C,1)=0
f(C,2)=1
f(C,3)=73
f(C,4)=4033
f(C,5)=198469
f(C,6)=9164233

f(X_1,1)=26
f(X_1,2)=1196
f(X_1,3)=46952
f(X_1,4)=1762928
f(X_1,5)=65451680
f(X_1,6)=2422685888