して4個以上並ぶものは除外するものとする。
全部で何通り作れますか？
例 ABAAABAAA、BBAAABAAA、CBAAABAAA、･･････、ABCDEFGHI、･･････、
ZYXWVUTSR、･･････、AAABBBCCC、･･････、BAZZZAZZZ など。
らすかるさんからのコメントです。（令和３年６月２１日付け）
4連続以上除外の条件がなければ、26^9通り
1文字目から4文字目(以降)まで同じものは、26・26^5通り
2文字目から5文字目(以降)まで同じものは、26・25・26^4通り
3文字目から6文字目(以降)まで同じものは、26^2・25・26^3通り
4文字目から7文字目(以降)まで同じものは、26^3・25・26^2通り
5文字目から8文字目(以降)まで同じものは、26^4・25・26通り
6文字目から9文字目まで同じものは、26^5・25通り
上記の重複である xxxxyyyy?(?は任意) というパターンは、26・25・26通り
xxxx?yyyy(?はy以外;x=yを含む) というパターンは、26・26・25通り
xyyyyzzzz(x=zを含む) というパターンは、26・25・25通り
よって、求める場合の数は、
26^9-26・26^5-25・26^5・5+26・25・26+26・26・25+26・25・25=5427709641250（通り）
ＧＡＩ さんからのコメントです。（令和３年６月２１日付け）
「 The Nine Billion Names of God 」
1953年のアーサー・クラークの短篇科学小説で、チベットの僧侶が、神の可能な御名は、
彼ら独自のアルファベットで9字以内、さらに、同じアルファベットは4文字以上連続して並ば
ないという条件で神の名前を書き連ねていた。
人の手で1万5千年かかるこの事業も、コンピュータを使えば3か月でやってのけることがで
きると聞き、アメリカのコンピュータ会社に依頼にきた。しかし、それは、90億ある神の名をす
べて書き並べると、神の目的は終わり、人間が創造された理由も失われる。
というような設定で書かれた小説らしい。
そこで、26文字の中から9文字までを重複を許して（ただし同じ文字は連続して4個以上は
並ばない条件を付ける）並べるとき、何通りの神の名前が作れるのか知りたかった。
らすかるさんの求め方を参考に、ｎ種類の文字での名前の付け方をF(n)としたら、
F(n)=n^9-6*n^6+5*n^5+3*n^3-4*n^2+n
なる式で書けそうで、n=1、2、3、4、･･･、12、13、･･･、26 では、
0、298、16572、242820、･･･、5143113228、10577400912、･･･、5427709641250
で、この計算によると、9billion(=90億）を越えるのは、ｎ=12、13の間で超えるので、独自の
アルファベット数を13個にしておけば、全部の神の御名を記述できることになる。
同じく、ｎ種の文字の中から9文字までを重複を許して（ただし同じ文字は連続して3個以上
は並ばない条件を付ける）並べるとき、何通りの神の名前が作れるのかの式G(n)は、
G(n)=n^9-7*n^7+6*n^6+10*n^5-16*n^5-16*n^4+5*n^3+2*n^2-n
となり、n=1、2、3、4、･･･、12、13、･･･、26 では、
0、110、10032、178524、･･･、4929039060、10197487872、･･･、5375246093750
となり、やはり、これでも13個のアルファベットを使っていけば、9billionを作り切ってしまう。
1953年当時計算させて印字し終わるまでこれを3か月でやらせることは可能か？もしそう
ならアーサー・クラークの小説の設定のすばらしさは称賛に価する。
ａｔ さんさんからのコメントです。（令和３年６月２６日付け）
n 種類の異なる文字から重複を許し、k 個の文字を並べた順列を作る。ただし、同じ文字
が連続して r 個以上並ぶものは除外するものとする。
この条件下で、全部で F(n,k,r) 通りの順列が作れるとすると、F(n,k,r)は次のように計算で
きます。
F(n,k,r)
=[t^k](∫_[0〜∞](exp(n*((t-t^r)/(1-t^r))*z)*exp(-z))dz)
=[t^k]((1-t^r)/(1-n*t+(n-1)*t^r))
=[t^k](1-t^r)*Σ[j=0〜∞])((1-n)*t^r)^j/(1-n*t)^(j+1))
=Σ[j=0〜floor(k/r)](1-n)^j*n^(k-r*j)*comb(j+k-r*j,k-r*j)
-Σ[j=0〜floor((k-r)/r)](1-n)^j*n^(k-r-r*j)*comb(j+k-r-r*j,k-r-r*j).
あるいは、
F(n,k,r)
=[t^k](Σ[j=0〜∞]n*(n-1)^(j-1)*(t+t^2+t^3+…+t^(r-1))^j)
=(n/(n-1))*[t^k](Σ[j=0〜∞]((n-1)*(t+t^2+t^3+…+t^(r-1)))^j
=(n/(n-1))*[t^k]1/(1-(n-1)*(t+t^2+t^3+…+t^(r-1)))
=(n/(n-1))*[t^k](1-t)/(1-n*t+(n-1)*t^r)
=(n/(n-1))*(Σ[j=0〜floor(k/r)](1-n)^j*n^(k-r*j)*comb(j+k-r*j,k-r*j)
-Σ[j=0〜floor((k-1)/r)](1-n)^j*n^(k-1-r*j)*comb(j+k-1-r*j,k-1-r*j)).
以下、maximaによる計算結果：
F(n,k,r):=sum(binomial(j+k-r*j,k-r*j)*(1-n)^j*n^(k-r*j),j,0,floor(k/r))
-sum(binomial(j+k-r-r*j,k-r-r*j)*(1-n)^j*n^(k-r-r*j),j,0,floor((k-r)/r))$
F(26,9,4)=5427709641250
F(50,13,5)=12207013984378025750000
F(60,70,8)=2955204414482264804155676597306938299323459020966680383089990592
1393971258246554343706842932374296669429526511730722752000000
ＧＡＩ さんさんからのコメントです。（令和３年６月２６日付け）
このパターンの一般計算式を作れるなんて凄い。前々からatさんは、このような構成が自
家薬籠であることに感心していましたが、今回も見事に作られましたね。この自由自在さを
見習いたいものです。
