バクスター順列

組合せ 数学において、バクスター順列は次の一般化されたパターン回避特性を満たす順列 である。 ${\displaystyle \sigma \in S_{n}}$

• またはとなるようなインデックスは存在しません。${\displaystyle i<j<k}$ ${\displaystyle \sigma (j+1)<\sigma (i)<\sigma (k)<\sigma (j)}$ ${\displaystyle \sigma (j)<\sigma (k)<\sigma (i)<\sigma (j+1)}$

同様に、破線パターンの表記法を使用すると、バクスター順列は 2 つの破線パターンと を回避する順列になります。 ${\displaystyle 2-41-3}$ ${\displaystyle 3-14-2}$

たとえば、（1 行表記で記述）の順列は、 、および をとると最初の条件に違反する ため、バクスター順列では ありません。${\displaystyle \sigma =2413}$ ${\displaystyle S_{4}}$ ${\displaystyle i=1}$ ${\displaystyle j=2}$ ${\displaystyle k=4}$

これらの順列はグレン・E・バクスターによって数学的解析の文脈で導入された。^[1]

列挙

の場合、長さのバクスター順列の数は ${\displaystyle n=1,2,3,\ldots }$ ${\displaystyle a_{n}}$ ${\displaystyle n}$

1、2、6、22、92、422、2074、10754、58202、326240、1882960、11140560、67329992、414499438、2593341586、16458756586、...

これはOEISの配列（ OEISの配列A001181）です。一般に、は以下の式を持ちます。 ${\displaystyle a_{n}}$

${\displaystyle a_{n}\,=\,\sum _{k=1}^{n}{\frac {{\binom {n+1}{k-1}}{\binom {n+1}{k}}{\binom {n+1}{k+1}}}{{\binom {n+1}{1}}{\binom {n+1}{2}}}}。}$ ^[2]

実際、この式は順列内の 下降の数によって段階分けされており、つまり、下降を含むバクスター順列が存在します。 ^[3]${\displaystyle {\frac {{\binom {n+1}{k-1}}{\binom {n+1}{k}}{\binom {n+1}{k+1}}}{{\binom {n+1}{1}}{\binom {n+1}{2}}}}$ ${\displaystyle S_{n}}$ ${\displaystyle k-1}$

その他の特性

• 長さ の交代バクスター順列の数はであり、カタラン数の平方であり、長さ の交代バクスター順列の数は${\displaystyle 2n}$ ${\displaystyle (C_{n})^{2}}$ ${\displaystyle 2n+1}$

${\displaystyle C_{n}C_{n+1}}$ 。

• 長さとの両方が交互に存在するバクスター順列（つまり、両方とその逆が交互に存在する順列）の数はカタラン数である。^[4]${\displaystyle 2n}$ ${\displaystyle 2n+1}$ ${\displaystyle \sigma }$ ${\displaystyle \sigma ^{-1}}$ ${\displaystyle C_{n}}$
• バクスター順列はホップ代数^[5] 、平面グラフ^{[6]、タイリング[7]}と関連している。 [ ^{8 ]}

動機：通勤機能

バクスターは、可換連続関数 の不動点を研究する中で、バクスター置換を導入した。特に、と が区間 から自身への連続関数であって、すべての に対して、かつ 内の有限個の に対して と なるとき、以下の関係が成り立つ。 ${\displaystyle f}$ ${\displaystyle g}$ ${\displaystyle [0,1]}$ ${\displaystyle f(g(x))=g(f(x))}$ ${\displaystyle x}$ ${\displaystyle f(g(x))=x}$ ${\displaystyle x}$ ${\displaystyle [0,1]}$

• これらの固定点の数は奇数です。
• 不動点が の場合、は互いに逆順列として作用する。${\displaystyle x_{1}、x_{2}、x_{2k+1}$ ${\displaystyle f}$ ${\displaystyle g}$

${\displaystyle \{x_{1},x_{3},\ldots ,x_{2k+1}\}}$ そして; ${\displaystyle \{x_{2},x_{4},\ldots ,x_{2k}\}}$

• によって誘導される順列は、によって誘導される順列を一意に決定する。${\displaystyle f}$ ${\displaystyle \{x_{1},x_{3},\ldots ,x_{2k+1}\}}$

${\displaystyle f}$ の上; ${\displaystyle \{x_{2},x_{4},\ldots ,x_{2k}\}}$

• 自然な再ラベル付け、などの下では、 に誘導される置換はバクスター置換である。${\displaystyle x_{1}\to 1}$ ${\displaystyle x_{3}\to 2}$ ${\displaystyle \{1,2,\ldots ,k+1\}}$

参照

• 特定の順列クラスの列挙

参考文献

1. バクスター、グレン (1964)、「可換関数の合成の不動点について」(PDF)、アメリカ数学会紀要、15 (6): 851– 855、doi : 10.2307/2034894、JSTOR  2034894。
2. Chung, FRK ; Graham, RL ; Hoggatt, VE Jr. ; Kleiman, M. (1978)、「バクスター順列の数」（PDF） , Journal of Combinatorial Theory , Series A, 24 (3): 382– 394, doi : 10.1016/0097-3165(78)90068-7 , MR  0491652。
3. Dulucq, S.; Guibert, O. (1998)、「バクスター順列」、離散数学、180 ( 1–3 ): 143– 156、doi : 10.1016/S0012-365X(97)00112-X、MR  1603713。
4. ギベール、オリヴィエ; リヌソン、スヴァンテ (2000)、「二重交互バクスター順列はカタランである」、離散数学、217 ( 1–3 ): 157– 166、doi : 10.1016/S0012-365X(99)00261-7、MR  1766265。
5. Giraudo, Samuele (2011), 「バクスター順列における代数的および組合せ的構造」,第23回国際形式冪級数および代数的組合せ論会議 (FPSAC 2011) , Discrete Math. Theor. Comput. Sci. Proc., vol. AO, Assoc. Discrete Math. Theor. Comput. Sci., Nancy, pp.  387– 398, arXiv : 1011.4288 , Bibcode :2010arXiv1011.4288G, MR  2820726。
6. ニコラ・ボニション; Bousquet-Mélou, ミレイユ; Fusy、Éric (2009 年 10 月)、「Baxter permutations and plan bipolar Orientations」、Séminaire Lotharingien de Combinatoire、61A、Art. B61Ah、29pp、arXiv : 0805.4180、Bibcode :2008arXiv0805.4180B、MR  2734180。
7. Korn, M. (2004)、ポリオミノタイルの幾何学的および代数的性質、マサチューセッツ工科大学博士論文。
8. アッカーマン、エヤル；バレケ、ギル；ピンター、ロン・Y.（2006）「順列とフロアプラン間の一対一対応とその応用」離散応用数学、154（12）：1674–1684、doi：10.1016/j.dam.2006.03.018、MR  2233287。

外部リンク

• OEIS配列A001181（長さnのバクスター順列の数）