Cardinal Treeの数え上げ
最近輪講で"Compact Data Structures(Gonzalo Navarro, 2016)"という本を読んでいるのですが、そこでCardinal Treeと呼ばれる木の個数がn頂点のとき$$\frac{\binom{nk+1}{n}}{nk+1}$$個（$k$は子の最大個数）であると紹介されていました。その証明を考えてみたところなかなか面白かったので、紹介してみようと思います*1。
1. Cardinal Treeとは
子に1以上k以下のラベルが付いていて、同じ親を持つ子同士でラベルの重複がない（つまり1つの親が持てる子の最大個数はk個）根付き木のことをCardinal Treeといいます。
n頂点の順序木の個数がn-1に対するカタラン数であることは有名ですが、これは漸化式を用いて求める方法が一般的らしいです。同様にCardinal Treeの個数も漸化式で求めようとすると、これはなかなかうまくいきません。しかし、実はCardinal Treeの個数は、Cardinal Treeをビット列として表して、Cardinal Treeの条件を満たすようなビット列の個数を数え上げることでうまく求められるのです！これを次節で紹介します。
2. Cardinal Treeの数え上げ
さて、n頂点のCardinal Treeの個数を数え上げるための準備として、まずCardinal Treeをビット列として表してみます。
Cardinal Treeのビット列による表現は、Cardinal Treeの各頂点に長さkのビット列を対応させ、そのビット列が頂点が持つ子のラベルを表すというものです。
例えば、先ほど例に出したCardinal Treeのビット表現は
となります。
つまり、まず根に対応する長さkのビット列から始まり、次に根の子の数だけ根の子に対応する長さkのビット列が続き、次に根の孫のビット列が続き…というようなビット表現となります。
さて、このようにCardinal Treeをビット列で表したとき、頂点数をnとすると、長さがnkで、1がn-1個含まれるビット列になります。そこで、まずは安直に、長さnkで、1がn-1個含まれるビット列の個数を求めてみると$$\binom{nk}{n-1}$$個です。
この中でCardinal Treeのビット表現になっているものがどれくらいあるかを考えます。実は、これに関して次の2つの事実が成り立ちます。
- 長さnkで1をn-1個含むビット列を長さkの区間に分割し、分割してできたn個の区間に先頭から番号を1,2,..,nとつけていく。この区間列1,2,...,nを、1以上n以下の整数iに対してi,i+1,...,n,1,2,...,i-1と並べ替える操作を回転とよぶことにする。このとき、区間列1,2,...,nを回転させてできるn通りのビット列はすべて異なる。
- 長さnkで1をn-1個含むビット列に対して、回転させてできるn通りを考えると、その中でただ一つだけCardinal Treeのビット表現になっている。
この2つの事実が証明できたとすると、長さnkで1をn-1個含むビット列の中で、Cardinal Treeのビット表現となっているものは$$\frac{\binom{nk}{n-1}}{n}=\frac{\binom{nk+1}{n}}{nk+1}$$個であることがわかるので、頂点数nのCardinal Treeの個数は$$\frac{\binom{nk+1}{n}}{nk+1}$$個であるとわかります。
ではこの2つの事実を証明してみましょう。
1.の証明
長さnkで1をn-1個含むビット列を、長さkの区間ごとに分割して区間に番号をつけて並べたものを1,2,...,nとする。これを回転させてできるn通りの中に同じビット列があるとき、区間列は周期性を持つはずである。区間j個で1周期をなしているとすると、jは区間数nの約数である。ここで、1周期の中で含まれる1の個数をc個とすると、ビット列全体に含まれる1の個数はcn/j個である。これはn-1に等しいが、nとn-1は互いに素なのでj=nである必要がある。つまり区間n個で1周期なので、区間列は周期性を持たず、区間列を回転させてできるn通りのビット列はすべて異なる。
2.の証明
1.の証明と同様のビット列、区間分割を考える。ここで、各区間に対して、区間に入っている1の数-1を返す関数$f(i)$($i$は区間番号)を考える。さらに、$f(1)$から$f(i)$までの累積和を$g(i)(1\leq i\leq n)$と表すことにする。このとき、前にCardinal Treeのビット表現の例で出てきたビット列に対する$g(i)(1\leq i\leq 9)$をグラフで表すと下図のようになる。
ここで$g(i)$を観察しながら、ビット列がCardinal Treeのビット表現になっているための条件を考えてみよう。Cardinal Treeのビット表現では、$g(i)(1\leq i\leq n)$は、頂点1,2,...,iを用いてCardinal Treeの部分木を作ったときに、その木の頂点が追加で持つ予定の子の個数-1を表している。つまり、Cardinal Treeのビット表現では、$g(i)$は$i=n$の場合を除いて非負である。
さて、Cardinal Treeのビット表現の特徴づけがわかったところで、長さnk、1をn-1個含む任意のビット列に対して、それを回転して得られるn通りのうちただ一つだけがCardinal Treeのビット表現になっていることを示そう。
実は、長さnk、1をn-1個含む任意のビット列に対して、$g(i)(1\leq i\leq n)$が最小であるような区間のうち最も左の区間（番号が最小の区間）iを見つけ、区間i+1が先頭になるように回転すればCardinal Treeのビット表現になっている。また、それ以外の区間が先頭になるように回転すると、それはCardinal Treeのビット表現にはなっていない。
まずは実際に例で確認してみよう。次のCardinal Treeのビット表現になっていないビット列に対する$g(i)(1\leq i\leq 9)$を観察してみる。
この場合$g(i)$が最小である区間のうち、最も左の区間は6なので、7を先頭に回転してみる。
このとき、確かに回転後のビット列は$g(i)$が$i<9$において非負なので、Cardinal Treeのビット表現になっている。
また、ほかの区間を先頭にして回転すると、$g(i)$が$i<9$のどこかで負になることが確認できるだろう。
これは、$g(i)$が最小である区間のうち、最も左の区間をiとして、区間i+1が先頭になるように回転すると、区間iが回転後に$g$が最小になる唯一の区間であり、また区間i+1以外が先頭になるように回転すると、区間iでの$g$の値が回転後に負になるからである。
