母関数を使って括弧のパターンを求めてみた

数学

n個の対応する括弧のパターンの数を母関数を使って求めてみました。
これはid:nobsunさんが指摘なさっているようにカタラン数という数になるんですが、そういう前提知識なしで機械的に解きたいような場合に使えます。
いろんな教科書があると思いますが、私は以下の本で学びました。
参考書籍：

コンピュータの数学

コンピュータの数学

まず求めるパターンを全て書きだした形式的なべき級数を考えてみます。式の中の1は括弧を一個も使わないパターンのつもり。

T = 1 + () + ()() + (()) + ()()() + ()(()) + (())() + (()()) + ((())) + ()()()() + ...

ここで括弧一組をxと置き換えてみると、

T = 1 + x + x^2 + x^2 + x^3 + x^3 + x^3 + x^3 + x^3 + x^4 + ... = 1 + x + 2 x^2 + 5 x^3 + 14 x^4 + ...

という級数になりますが、このx^nの各係数が求める答えであるという事が分かるかと思います。このように求める数列を係数としてもつ関数を母関数といいます。この母関数は式の再帰的な構造に注目すると簡単に求める事ができます。

では順番にやっていきます。
とりあえず、xに置き換える前の式に戻ります。

T = 1 + () + ()() + (()) + ()()() + ()(()) + (())() + (()()) + ((())) + ()()()() + ...

ここで途中で複数に分割できるパターン("()()"とか"()(())"とか)を(交換出来ない)掛け算だと思って、左端をくくり出すと

T = 1 + () {1 + () + ()() + (()) + ()()() + ...} + (()) {1 + () + ()() + (()) + ()()() + ...} + (()()) {1 + () + ()() + ...} + ...

くくった結果再びTが現れたので整理すると

T = 1 + () T + (()) T + (()()) T + ...

となります。今度はTをくくると

T = 1 + {() + (()) + (()()) + ...} T

となります。ここで残った中括弧の中身はTの各項を括弧で囲んだ物であることがわかります。つまり

() + (()) + (()()) + ... = '(' {1 + () + ()() + (()) + ...} ')'

となってますから、以下のシンプルな式を得ます。

T = 1 + '(' T ')' T

'...'がなくなったら括弧をxに置き換えます。この置き換えでx^nの係数は変わらない事が分かると思います。

T = 1 + x T^2

これは2次方程式ですから解の公式で解けて

T = (1 - sqrt(1- 4 x)) / (2 x)

と母関数が求まります。コイツのx^nの係数が求める答えです。
一応こいつの無限級数展開をWolfram Alphaで聞いてみると

確かに各係数(1,1,2,5,14,42,..)が求める答えになっている事がわかります。この係数の一般項を具体的求めると、それがカタラン数である事が分かるのですがWolfram Alphaはそこまでは教えてくれませんでした。

一般項を求めないで、漸化式を導くという事をやっても良いかと思います。
一つ前の式に戻ります。

T = 1 + x T^2

これから漸化式が作れます。n組の括弧からなるパターンの数をT(n)とおくと

T(n) = T(0) + T(1) x + T(2) x^2 + T(3) x^3 + T(4) x^4 + ...

となってる訳ですから、両辺を展開してx^nの係数だけ比較してみると、n > 0の時は

T(n) = T(0) T(n-1) + T(1) T(n-2) + ... + T(n-1) T(0)

となります。カタラン数の漸化式を機械的に求める事が出来ました。
参考までにですが、右辺の形は畳込みと言って「母関数の積(T^2)の係数 = 母関数の係数の畳込み」という有名な性質です。他にも微分・積分やシフト演算などを用いる母関数についての公式がありますので、それを覚えとくとこういった計算が素早くできます。

さて、「漸化式」があるならば「動的計画法」が定石です。rubyで書いてみるとこんな感じになります。(n=100まで求めてみます)

t = []
t[0] = 1
(1..100).each do |n|
    x = 0
    (0..n-1).each do |k|
        x += t[k] * t[n-k-1]
    end
    t[n] = x
    puts t[n]
end

%nineties% time ruby kakko.rb
1
2
5
14
42
132
429
1430
4862
16796
58786
208012
742900
2674440
... 中略 ...
896519947090131496687170070074100632420837521538745909320
ruby kakko.rb  0.03s user 0.01s system 77% cpu 0.057 total

文字列集合を得る

ここでも上で求めた式が使えます

T = 1 + '(' T ')' T

Haskellでやってみようと思いますが、右辺に無限リストが2つあるので漸化式に直しとく必要があります。

T(0) = 1
T(n) = '(' T(0) ')' T(n-1) + '(' T(1) ')' T(n-2) + ... + '(' T(n-1) ')' T(0)

これを立式すると次のようになります。

pattern 0 = [""]
pattern n = [concat["(",l,")",r] | i <- [0..n-1], l <- pattern i, r <- pattern (n-i-1)]

もしくは無限リストとして自分自身を参照するようにするとこんな感じになります。

pattern = [""] : [[concat["(",l,")",r] | i <- [0..n-1], l <- pattern !! i, r <- pattern !! (n-i-1)] | n <- [1..]]

patternは括弧のつけ方の無限リストになっています。

%ghci
GHCi, version 6.12.1: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
Prelude> :l kakko.hs
[1 of 1] Compiling Main             ( kakko.hs, interpreted )
Ok, modules loaded: Main.
*Main> take 7 pattern
[[""],["()"],["()()","(())"],["()()()","()(())","(())()","(()())","((()))"],["()()()()","()()(())","()(())()","()(()())","()((()))","(())()()","(())(())","(()())()","((()))()","(()()())","(()(()))","((())())","((()()))","(((())))"],["()()()()()","()()()(())","()()(())()","()()(()())","()()((()))","()(())()()","()(())(())","()(()())()","()((()))()","()(()()())","()(()(()))","()((())())","()((()()))","()(((())))","(())()()()","(())()(())","(())(())()","(())(()())","(())((()))","(()())()()","(()())(())","((()))()()","((()))(())","(()()())()","(()(()))()","((())())()","((()()))()","(((())))()","(()()()())","(()()(()))","(()(())())","(()(()()))","(()((())))","((())()())","((())(()))","((()())())","(((()))())","((()()()))","((()(())))","(((())()))","(((()())))","((((()))))"],["()()()()()()","()()()()(())","()()()(())()","()()()(()())","()()()((()))","()()(())()()","()()(())(())","()()(()())()","()()((()))()","()()(()()())","()()(()(()))","()()((())())","()()((()()))","()()(((())))","()(())()()()","()(())()(())","()(())(())()","()(())(()())","()(())((()))","()(()())()()","()(()())(())","()((()))()()","()((()))(())","()(()()())()","()(()(()))()","()((())())()","()((()()))()","()(((())))()","()(()()()())","()(()()(()))","()(()(())())","()(()(()()))","()(()((())))","()((())()())","()((())(()))","()((()())())","()(((()))())","()((()()()))","()((()(())))","()(((())()))","()(((()())))","()((((()))))","(())()()()()","(())()()(())","(())()(())()","(())()(()())","(())()((()))","(())(())()()","(())(())(())","(())(()())()","(())((()))()","(())(()()())","(())(()(()))","(())((())())","(())((()()))","(())(((())))","(()())()()()","(()())()(())","(()())(())()","(()())(()())","(()())((()))","((()))()()()","((()))()(())","((()))(())()","((()))(()())","((()))((()))","(()()())()()","(()()())(())","(()(()))()()","(()(()))(())","((())())()()","((())())(())","((()()))()()","((()()))(())","(((())))()()","(((())))(())","(()()()())()","(()()(()))()","(()(())())()","(()(()()))()","(()((())))()","((())()())()","((())(()))()","((()())())()","(((()))())()","((()()()))()","((()(())))()","(((())()))()","(((()())))()","((((()))))()","(()()()()())","(()()()(()))","(()()(())())","(()()(()()))","(()()((())))","(()(())()())","(()(())(()))","(()(()())())","(()((()))())","(()(()()()))","(()(()(())))","(()((())()))","(()((()())))","(()(((()))))","((())()()())","((())()(()))","((())(())())","((())(()()))","((())((())))","((()())()())","((()())(()))","(((()))()())","(((()))(()))","((()()())())","((()(()))())","(((())())())","(((()()))())","((((())))())","((()()()()))","((()()(())))","((()(())()))","((()(()())))","((()((()))))","(((())()()))","(((())(())))","(((()())()))","((((()))()))","(((()()())))","(((()(()))))","((((())())))","((((()()))))","(((((())))))"]]

「日本の硬貨を使ってn円払う払い方の総数は？」

母関数の応用として有名な例を一つ紹介。

1 + x + x^2 + x^3 + ...

のx^nの係数が1円玉のみでn円払う払い方の総数(つまり1通り)。

1 + x^5 + x^10 + x^15 + x^20 + ...

のx^nの係数が5円玉のみでn円払う払い方の総数(つまり1通り)。
...
これらの組み合わせを考えれば良いので、母関数は

T = (1 + x + x^2 + x^3 + ..) (1 + x^5 + x^10 + x^15 + x^20 + ...) (1 + x^10 + x^20 + ...) (1 + x^50 + x^100 + ...) (1 + x^100 + x^200 + ...) (1 + x^500 + x^1000 + ...)

となります。それぞれの形式的級数(無限等比級数の和の公式を使って)を閉形式にすると

T = 1/(1-x) 1/(1-x^5) 1/(1-x^10) 1/(1-x^50) 1/(1-x^100) 1/(1-x^500)

となります(ここでは発散とか考えなくてよし)。
これから一般解を求める事ができますが、めんどくさいので省略。
漸化式を作ります。
分母を払うと

(1-x)(1-x^5)(1-x^10)(1-x^50)(1-x^100)(1-x^500)T = 1 .... (1)

となります。
さてTのx^nの係数T(n)の漸化式を求めます。
まず(1-x^500)Tのx^nの係数は

A(n) = T(n)-T(n-500)

です。(但し、X(n)の中身が負になったときはX(n)=0とします。)
よって(1-x^100)(1-x^500)Tのx^nの係数は

B(n) = A(n) - A(n-100)

です。これを繰り返すと

A(n) = T(n)-T(n-500)
B(n) = A(n) - A(n-100)
C(n) = B(n) - B(n-50)
D(n) = C(n) - C(n-10)
E(n) = D(n) - D(n-5)
F(n) = E(n) - E(n-1)

となります。
これを移項して整理すると

T(n) = T(n-500) + A(n)
A(n) = A(n-100) + B(n)
B(n) = B(n-50) + C(n)
C(n) = C(n-10) + D(n)
D(n) = D(n-5) + E(n)
E(n) = E(n-1) + F(n)

となって下から上に向かって動的計画法で解ける形になります。
F(n)が(1)式の左辺のx^nの係数なのでF(0) = 1で、n > 0の時はF(n) = 0となる事に注意してください。
rubyで書くと以下の様になります。せっかくのRubyなので「インデックスが負なら0」をArrayの[]を書き換えて実装してみました。

class Array
    def [](i)
        i < 0 ? 0 : at(i)
    end
end

t = []
a = []
b = []
c = []
d = []
e = []

(0..10000).each do |n|
    f = (n == 0) ? 1 : 0
    e[n] = e[n-1] + f
    d[n] = d[n-5] + e[n]
    c[n] = c[n-10] + d[n]
    b[n] = b[n-50] + c[n]
    a[n] = a[n-100] + b[n]
    t[n] = t[n-500] + a[n]
    puts "#{n}円 : #{t[n]}通り"
end

nineties% time ruby kouka.rb
0円 : 1通り
1円 : 1通り
2円 : 1通り
3円 : 1通り
4円 : 1通り
5円 : 2通り
6円 : 2通り
7円 : 2通り
8円 : 2通り
9円 : 2通り
10円 : 4通り
11円 : 4通り
...

9996円 : 7825615000通り
9997円 : 7825615000通り
9998円 : 7825615000通り
9999円 : 7825615000通り
10000円 : 7844606371通り
ruby kouka.rb  0.19s user 0.06s system 63% cpu 0.395 total

この例では問題の難易度に比べて大げさすぎる気がしますが、まぁおもしろいんではないかと思います。他にもいろんな応用がありますので、是非調べてみて下さい。。