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

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

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

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

条件
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
★「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=0AqIQfyJX …

また、素因数分解すると・・・
●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.11 回答者： nag0720 回答日時： 2010/06/10 00:39

20080715さんへ

失礼しました。

f(X_1,n)=-10^n-36^(n+1)*((12*(10)^(1/2))^(-1))*(-(-18+6*(10)^(1/2))^(-n)+(-18-6*(10)^(1/2))^(-n))

の=以降をそのままコピーしてExcelのセルに貼り付けて計算したんですが、Excelの計算方法が違っていました。

Excelで、「=-10^n」を計算すると、「=(-10)^n」となってしまうようです。
「-(-18+6*(10)^(1/2))^(-n)」の部分も実際の値と違っていました。


Excelで「=0-10^2」とすると正しく「-100」になるので、
たぶん、単項演算子と二項演算子の違いでそうなるのだと思いますが、Excelを信用しすぎていました。

申し訳ありませんでした。

No.10 回答者： 20080715 回答日時： 2010/06/09 23:06

nag0720さん：

＞＃３のf(X_1,n)の式を使って計算すると、
＞n=1,3,5の場合は＃１と一致してますが、n=2,4,6は違っています。

＃３で私が書いた式
f(X_1,n)=-10^n-36^(n+1)*((12*(10)^(1/2))^(-1))*(-(-18+6*(10)^(1/2))^(-n)+(-18-6*(10)^(1/2))^(-n))
のことですね。

私はこの式を使って、DERIVEという数式ソフトで確認してみました。
f(X_1,1),f(X_1,2),f(X_1,3),f(X_1,4),f(X_1,5),f(X_1,6)
の値をそれぞれ計算させてみた結果、nag0720さんが＃１でお書きになっている
結果とすべて一致しました。
数値がマイナスや非整数になっているということもありませんでした。

＃３で私が書いた式は、指数部分に(1/2),(-1),(-n)などがあってかなり
読みにくいです。

No.9 回答者： nag0720 回答日時： 2010/06/09 14:38

ここを20080715さんも見ているようですので。

＃３のf(X_1,n)の式を使って計算すると、
n=1,3,5の場合は＃１と一致してますが、n=2,4,6は違っています。

＃１は、
f(X_1,2)=1196
f(X_1,4)=1762928
f(X_1,6)=2422685888

＃３は、
f(X_1,2)=-1197.79875
f(X_1,4)=-1762929.705
f(X_1,6)=-2422685890

マイナスになっているし、プラスだとしても1～2違っています。
どこか間違っていませんか？

No.8 回答者： 20080715 回答日時： 2010/06/09 12:04

ああ。

私のNo.5の回答は間違っていますね。
私の回答では、
a.-b.-a
のような、ピリオドとハイフンが混在するようなものまで
数えてしまっていますね。
正しい答えは、
f(X_1∪Y,n)=f(X_1,n)+f(Y,n)-f(X_1∩Y,n)
より導けますね。

No.7 回答者： nag0720 回答日時： 2010/06/09 11:49

ついでに、

＃５と＃６の答えが違っているので、f(X1∪Y,4)を実際に数えてみましょう。

英字をA
数字をN
ピリオドをP
ハイフンをH
とし、４個の文字列をAAAAのように表すとすると、条件を満たす文字列は、

AAAA = 26^4
AAAN,AANA,ANAA,NAAA = 26^3*10 * 4
AANN,ANAN,ANNA,NAAN,NANA,NNAA = 26^2*10^2 * 6
ANNN,NANN,NNAN,NNNA = 26*10^3 * 4
APAA,AAPA,AHAA,AAHA = 26^3 * 4
APAN,APNA,NPAA,AAPN,ANPA,NAPA,AHAN,AHNA,NHAA,AAHN,ANHA,NAHA = 26^2*10 * 12
APNN,NPAN,NPNA,ANPN,NAPN,NNPA,AHNN,NHAN,NHNA,ANHN,NAHN,NNHA = 26*10^2 * 12
NPNN,NNPN,NHNN,NNHN = 10^3 * 4

となり、これらをすべて足すと1856240になります。

なお、Hを含む文字列を除くと1762928となり、これがf(X_1,4)です。

No.6 回答者： nag0720 回答日時： 2010/06/09 11:19

もうやめようと思ってましたが、違う回答が出ていたので・・・

（質問その３）
X_1とYとの共通部分はn個の文字がすべて英字か数字の場合です。
つまり、f(X_1∩Y,n)=36^n-10^n

f(X_1∪Y,n)=f(X_1,n)+f(Y,n)-f(X_1∩Y,n)
=2*36^2*((37-β)*α^(n-2)-(37-α)*β^(n-2))/(α-β)-10^n-36^n
ただし、α=6(3+√10)、β=6(3-√10)

f(X_1∪Y,1)=26
f(X_1∪Y,2)=1196
f(X_1∪Y,3)=48248
f(X_1∪Y,4)=1856240
f(X_1∪Y,5)=70537184
f(X_1∪Y,6)=2669589440

No.5 回答者： 20080715 回答日時： 2010/06/08 23:40

（質問その３）について：

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

f((X_1∪Y),n)=36*1513^(-1/2)*(-((1513)^(1/2)/72-37/72)^(-n+1)+((1513)^(1/2)/72-37/72)^(-n)-(-(-(1513)^(1/2)/72-37/72)^(-n+1)+(-(1513)^(1/2)/72-37/72)^(-n)))
です。

g(x)のx^nの係数を[x^n]g(x)というように書くことにすれば、
f((X_1∪Y),n)
=Σ[k=1～∞][x^n](((36*x)/(1-36*x))^k)*(2*x/(1-x))^(k-1)
=[x^n]Σ[k=1～∞](((36*x)/(1-36*x))^k)*(2*x/(1-x))^(k-1)
=[x^n]36*x*(1-x)/(36*x^2+37*x-1)
=36*1513^(-1/2)*(-((1513)^(1/2)/72-37/72)^(-n+1)+((1513)^(1/2)/72-37/72)^(-n)-(-(-(1513)^(1/2)/72-37/72)^(-n+1)+(-(1513)^(1/2)/72-37/72)^(-n)))

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

上記のf((X_1∪Y),n)の式を使って、
f((X_1∪Y),1)=36,
f((X_1∪Y),2)=1296,
f((X_1∪Y),3)=49248,
f((X_1∪Y),4)=1868832,
f((X_1∪Y),5)=70919712,
f((X_1∪Y),6)=2691307296.

No.4 回答者： nag0720 回答日時： 2010/06/08 21:08

＃１、＃２です。

なんとかf(X_1,n)が求まりました。

f(X_1,n)=36^2*{(37-β)*α^(n-2)-(37-α)*β^(n-2)}/(α-β)-10^n
ただし、α=6(3+√10)、β=6(3-√10)

No.3 回答者： 20080715 回答日時： 2010/06/08 18:57

（質問その１）について：

f(X_1,n)=-10^n-36^(n+1)*((12*(10)^(1/2))^(-1))*(-(-18+6*(10)^(1/2))^(-n)+(-18-6*(10)^(1/2))^(-n))
です。

ローラン級数f(x)の、x^n の係数を[x^n]と書くことにします。
ピリオドを全く含まない場合と、ピリオドを1個以上含む場合に分けて考えます。
ピリオドを全く含まない場合は、条件を満たすようなn個の文字列は
36^n-10^n ---(1) 通り。
ピリオドを1個以上含む場合は、条件を満たすようなn個の文字列は
Σ[k=1～∞]([x^n]((36*x+(36*x)^2+36*x+(36*x)^3+…)^(k+1))*(x^k))
=Σ[k=1～∞][x^n](36*x)^(k+1)*(x^k)*(1-36*x)^(-k-1)
=Σ[k=1～∞]36^(k+1)*[x^(n-2k-1)](1-36*x)^(-k-1)
=Σ[k=1～floor((n-1)/2)]36^(k+1)*C(n-k-1,n-2k-1)*36^(n-2k-1)
=Σ[k=1～floor((n-1)/2)]C(n-k-1,n-2k-1)*36^(n-k)
=Σ[k=0～floor((n-1)/2)]C(n-k-1,n-2k-1)*36^(n-k) -36^n
=36^(n)*[t^(n-1)]((1-t)^(-1))*(1-(1/36)*t^2*(1-t)^(-1))^(-1) -36^n
=-36^(n+1)*((12*(10)^(1/2))^(-1))*(-(-18+6*(10)^(1/2))^(-n)+(-18-6*(10)^(1/2))^(-n)) -36^n ----(2)
=
以上より、
f(X_1,n)
=(1)+(2)
=-10^n-36^(n+1)*((12*(10)^(1/2))^(-1))*(-(-18+6*(10)^(1/2))^(-n)+(-18-6*(10)^(1/2))^(-n)).

No.2 回答者： nag0720 回答日時： 2010/06/08 15:15

＃１の補足です。

f(C,n)=37*f(C,n-1)-36*f(C,n-3)+36*37^(n-3)
は
f(C,n)-f(C,n-1)=36*f(C,n-1)-36*f(C,n-2)+36*f(C,n-2)-36*f(C,n-3)+36*37^(n-3)
となるので、
g(n)=f(C,n)-f(C,n-1)
とおけば、
g(n)=36*g(n-1)+36*g(n-2)+36*37^(n-3)
となります。
さらに、
α=6(3+√10)、β=6(3-√10)として、
h(n)=g(n)-α*g(n-1)とおけば、
h(n)=β*h(n-1)+36*37^(n-3)

これから、h(n)の一般解を求めれば、さらにさかのぼってg(n)、f(C,n)も求めることができ、
f(X_1,n)の一般解が求まります。


ちょっと計算が大変なので、ここまでにしておきます。