みなさん、あるアルゴリズムの計算量の上限値や下限値を考えているときに自分で数列の一般式を求めることありませんか？そんなあなたにJohn H. Conway and Richard K. Guy著, 根上 生也訳‥数の本に紹介されていました、数列データベースをご紹介いたします。
●On-Line Encyclopedia of Integer Sequences
この数列データベースはキーワードや数列を検索キーとして登録されているデータベースの中から検索をしてくれます。
例えば、深さnのラベルなし二分木の種類数は、`1, 3, 21, 651, 457653'という数列になります。これを検索キーとして検索すると以下のような検索結果がでます。
●Number of binary trees of height n; or products (ways to insert parentheses) of height n when multiplication is non-commutative and non-associative
この検索結果にはこの数列の初出の論文や本、一般式、生成アルゴリズムが載っています。不意に思い出したのでご紹介まで。ちなみにここに載っている数列の一般式を必死こいて2週間考えていたことがあります。探す方法を知らないって怖いよね。
