A Recurrence for the Number of Baxter PermutationsVia Rectangular Partition

摘要

A rectangular partition is a subdivision of a rectangle into rectangles by horizontal and vertical line segments. Enumerating the number of rectangular partitions into n rectangles is an interesting combinatorial problem. Recently, it has been proved that there exists a bijection between rectangular partitions and Baxter permutations. That is, the problem is reduced to enumeration of the number of Baxter permutations. However, all known formulae and recurrences are complicated. In this report, we derive a simple linear recurrence and an enumerating algorithm directly from rectangular partitions.%矩形分割とは水平および垂直線分による矩形の分割である．れ個の小矩形への矩形分割の総数を求めることは興味深い数え上げの問題であるが，近年，矩形分割とBaxter permutation の間に全単射が存在するとが示された．すなわち，矩形分割の数え上げはBaxter permutationの数え上げに帰着された．しかしながら，Baxter permutationの総数を与える既知の公式及び漸化式はいずれも複雑なものである．本報告では，矩形分割から直接その総数を求めることにより，簡単な（多変数の）定数係数線形漸化式とアルゴリズムを導出する．