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

摘要

各点の子に順序がある根付き木を，順序木と呼ぶ，点の個数が整数n ≥2 である順序木は，カタラ ン数2n -2 Cn -1/n 個ある．また，点の個数がn≧3 であり，葉の個数がκ≦n-1である順序木は，Narayana 数（n-2Ck-1）（n-1Ck-1）/k個ある．点の個数がnである順序木を，一様ランダムに生成するアルゴリズムが いくつも知られているが，点の個数がれであり葉の個数がたである順序木を，一様ランダムに生成するアルゴリ ズムは知られていない．本論文は，整数nとkが与えられたとき，点の個数がれであり，葉の個数がたである 順序木を，効率的に，一様ランダムに生成する簡単なアルゴリズムを与える．キーワード。