葉の個数を指定した順序木の一様ランダム生成

村松 丘親  中野 眞一  

誌名
電子情報通信学会論文誌 A   Vol.J90-A   No.12   pp.940-947
発行日: 2007/12/01
Online ISSN: 1881-0195
DOI: 
Print ISSN: 0913-5707
論文種別: 論文
専門分野: グラフとネットワーク
キーワード: 
順序木,  ランダム生成,  Dyckパス,  Narayana数,  

本文: PDF(798.5KB)
>>論文を購入


あらまし: 
各点の子に順序がある根付き木を,順序木と呼ぶ.点の個数が整数n2である順序木は, カタラン数 2n-2 Cn-1/n個ある.また,点の個数がn3であり,葉の個数がk n-1である順序木は,Narayana数( n-2 Ck-1)(n-1 Ck-1)/k個ある.点の個数がnである順序木を,一様ランダムに生成するアルゴリズムがいくつも知られているが,点の個数がnであり葉の個数がkである順序木を,一様ランダムに生成するアルゴリズムは知られていない.本論文は,整数nkが与えられたとき,点の個数がnであり,葉の個数がkである順序木を,効率的に,一様ランダムに生成する簡単なアルゴリズムを与える.