Catalan number と関連した概念

葉の数を決めた planar binary tree の数を数えると Catalan number という数が得られる。 Catalan number の歴史については, この Igor Pakのblog が興味深い。Speculation とことわっているが。 その Pak が [Pak] で Catalan number の歴史について書いている。 Stanley の本の appendix になる予定のものらしい。 Pak は Catalan number についての website も運営している。

Binary と限らないで数えると super Catalan number という数が得られる。 Fuß-Catalan number と呼ばれる一般化もある。

• super Catalan number
• Fuß-Catalan number

Loday は [Lod02] で binary tree の集合のレベルでの操作を考えている。これは Catalan number や super Catalan number の categorification レベルでの操作を考えていると言える。 Bruno と Yasaki による解説 [BY11] がある。Buckley と Garner と Lack と Street の[Buc+] では, Catalan number の categorification は Catalan set と呼ばれている。

• Catalan set

Catalan set としては, Ganyushkin と Mazorchuk [GM11] の 0-Hecke monoid の quotient として作られる monoid もある。 もちろん他にも様々なものがある。Forcey らの [For+13] では, それらの間の bijection が構成されている。 Buckely, Garner, Lack, Street [Buc+15] は, simplicial set の構造を定義できることを示している。Catalan number の associahedron との関 係から予想されるように, monoidal structure を記述するのに使えるようである。より正確にいうと, associator などが invertible でなくてもよい skew-monoidal structure であるが。

• Catalan simplicial set

このように, Catalan number は数多くの解釈を持つため, 様々な分野に登場する。そして, そのため様々な一般化が提案され, 使われている。 例えば planar binary tree の数を associahedron の頂点の数と解釈すると, associahedron の一般化に対応して Catalan number の一般化が得られるが, Armstrong らは [ARW13] で rational associahedron を導入し, 対応して rational Catalan number という一般化を定義している。

• rational Catalan number

Catalan number を対称群に対応するものと考え, 他の Coxeter group へ一般化することを考えたのは Reiner [Rei97] だろうか。 Armstrong は thesis [Arm09] で Coxeter-Catalan number と呼んでいる。 Fuß-Catalan number については, Bessis の [Bes03] がある。

Catalan number (とその一般化) は, noncrossing partition という組み合せ論的構造の数とも考えることができる。これについては Armstrong の [Arm09] を見るとよい。

• noncrossing partition

Catalan number の一般化としては, 他にも Garsia と Haiman [GH96] の \((q,t)\)-Catalan number がある。 \((q,t)\)-Fuß-Catalan number というものもある。Stump [Stu08; Stu10] は, その“Coxeter版”を考えている。 Bergeron らによる一般化 [BDZ10] もある。

• \((q,t)\)-Catalan number
• \((q,t)\)-Fuß-Catalan number

Berenstein と Retakh [BR19] は, free Laurent polynomial algebra の元として, noncommutative Catalan number を定義している。

• noncommutative Catalan number

Canoと Díaz [DC19]は, Catalan number の continuous version を考えている。

• continuous Catalan number

3次元版が Borie [Bor17] により考えられている。その続編 [BF] では, 古典的な Catalan number に関連した概念の 3次元版が存在することが述べられている。

• \(3\)-dimensional Catalan number

他にも様々な変種が考えられている。

• Eulerian-Catalan number [BS11]
• modular Catalan number [HH17; HH22]
• weighted Catalan number [GG21]
• positroid Catalan number [GL]
• \(s\)-Catalan number [Lin22]
• hypergraph Catalan number [Gun21]
• hypergraph Fuß-Catalan number [CLS]
• Motzkin number [BH14]
• Raney number [Ran60; BD15]

References

[Arm09]

Drew Armstrong. “Generalized noncrossing partitions and combinatorics of Coxeter groups”. In: Mem. Amer. Math. Soc. 202.949 (2009), pp. x+159. arXiv: math/0611106. url: http://dx.doi.org/10.1090/S0065-9266-09-00565-1.

[ARW13]

Drew Armstrong, Brendon Rhoades, and Nathan Williams. “Rational associahedra and noncrossing partitions”. In: Electron. J. Combin. 20.3 (2013), Paper 54, 27. arXiv: 1305.7286. url: https://doi.org/10.37236/3432.

[BD15]

Jonathan E. Beagley and Paul Drube. “The Raney generalization of Catalan numbers and the enumeration of planar embeddings”. In: Australas. J. Combin. 63 (2015), pp. 130–141. arXiv: 1501.07137.

[BDZ10]

N. Bergeron, F. Descouens, and M. Zabrocki. “A filtration of \((q,t)\)-Catalan numbers”. In: Adv. in Appl. Math. 44.1 (2010), pp. 16–36. arXiv: 0806.3046. url: http://dx.doi.org/10.1016/j.aam.2009.03.002.

[Bes03]

David Bessis. “The dual braid monoid”. In: Ann. Sci. École Norm. Sup. (4) 36.5 (2003), pp. 647–683. arXiv: math/0101158. url: http://dx.doi.org/10.1016/j.ansens.2003.01.001.

[BF]

Nicolas Borie and Justine Falque. Product-Coproduct Prographs and Triangulations of the Sphere. arXiv: 2202.05757.

[BH14]

Georgia Benkart and Tom Halverson. “Motzkin algebras”. In: European J. Combin. 36 (2014), pp. 473–502. arXiv: 1106.5277. url: https://doi.org/10.1016/j.ejc.2013.09.010.

[Bor17]

Nicolas Borie. “Three-dimensional Catalan numbers and product-coproduct prographs”. In: Sém. Lothar. Combin. 78B (2017), Art. 39, 12. arXiv: 1704.00212.

[BR19]

Arkady Berenstein and Vladimir Retakh. “Noncommutative Catalan numbers”. In: Ann. Comb. 23.3-4 (2019), pp. 527–547. arXiv: 1708.03316. url: https://doi.org/10.1007/s00026-019-00473-4.

[BS11]

Hoda Bidkhori and Seth Sullivant. “Eulerian-Catalan numbers”. In: Electron. J. Combin. 18.1 (2011), Paper 187, 10. arXiv: 1101.1108. url: https://doi.org/10.37236/674.

[Buc+]

Mitchell Buckley, Richard Garner, Stephen Lack, and Ross Street. Skew-monoidal categories and the Catalan simplicial set. arXiv: 1307.0265.

[Buc+15]

Mitchell Buckley, Richard Garner, Stephen Lack, and Ross Street. “The Catalan simplicial set”. In: Math. Proc. Cambridge Philos. Soc. 158.2 (2015), pp. 211–222. arXiv: 1309.6120. url: https://doi.org/10.1017/S0305004114000498.

[BY11]

Adriano Bruno and Dan Yasaki. “The arithmetic of trees”. In: Involve 4.1 (2011), pp. 1–11. arXiv: 0809 . 4448. url: http://dx.doi.org/10.2140/involve.2011.4.1.

[CLS]

Parth Chavan, Andrew Lee, and Karthik Seetharaman. Hypergraph Fuss-Catalan Numbers. arXiv: 2202.01111.

[DC19]

Rafael Díaz and Leonardo Cano. “Continous analogues for the binomial coefficients and the Catalan numbers”. In: Appl. Anal. Discrete Math. 13.2 (2019), pp. 542–568. arXiv: 1602.09132. url: https://doi.org/10.2298/AADM161015019D.

[For+13]

Stefan Forcey, Mohammadmehdi Kafashan, Mehdi Maleki, and Michael Strayer. “Recursive bijections for Catalan objects”. In: J. Integer Seq. 16.5 (2013), Article 13.5.3, 20. arXiv: 1212.1188.

[GG21]

Yibo Gao and Andrew Gu. “Arithmetic of weighted Catalan numbers”. In: J. Number Theory 226 (2021), pp. 213–242. arXiv: 1908.03914. url: https://doi.org/10.1016/j.jnt.2021.03.007.

[GH96]

A. M. Garsia and M. Haiman. “A remarkable \(q,t\)-Catalan sequence and \(q\)-Lagrange inversion”. In: J. Algebraic Combin. 5.3 (1996), pp. 191–244. url: http://dx.doi.org/10.1023/A:1022476211638.

[GL]

Pavel Galashin and Thomas Lam. Positroid Catalan numbers. arXiv: 2104.05701.

[GM11]

Olexandr Ganyushkin and Volodymyr Mazorchuk. “On Kiselman quotients of 0-Hecke monoids”. In: Int. Electron. J. Algebra 10 (2011), pp. 174–191. arXiv: 1006.0316.

[Gun21]

Paul E. Gunnells. “Generalized Catalan numbers from hypergraphs”. In: Electron. J. Combin. 28.1 (2021), Paper No. 1.52, 29. arXiv: 2102.05121. url: https://doi.org/10.37236/8733.

[HH17]

Nickolas Hein and Jia Huang. “Modular Catalan numbers”. In: European J. Combin. 61 (2017), pp. 197–218. arXiv: 1508.01688. url: https://doi.org/10.1016/j.ejc.2016.11.004.

[HH22]

Nickolas Hein and Jia Huang. “Variations of the Catalan numbers from some nonassociative binary operations”. In: Discrete Math. 345.3 (2022), Paper No. 112711, 18. arXiv: 1807.04623. url: https://doi.org/10.1016/j.disc.2021.112711.

[Lin22]

William Linz. “\(s\)-Catalan numbers and Littlewood-Richardson polynomials”. In: Enumer. Comb. Appl. 2.2 (2022), Paper No. S2R14, 5. arXiv: 2110.12095.

[Lod02]

Jean-Louis Loday. “Arithmetree”. In: J. Algebra 258.1 (2002). Special issue in celebration of Claudio Procesi’s 60th birthday, pp. 275–309. arXiv: math/0112034. url: http://dx.doi.org/10.1016/S0021-8693(02)00510-0.

[Pak]

Igor Pak. History of Catalan numbers. arXiv: 1408.5711.

[Ran60]

George N. Raney. “Functional composition patterns and power series reversion”. In: Trans. Amer. Math. Soc. 94 (1960), pp. 441–451.

[Rei97]

Victor Reiner. “Non-crossing partitions for classical reflection groups”. In: Discrete Math. 177.1-3 (1997), pp. 195–222. url: http://dx.doi.org/10.1016/S0012-365X(96)00365-2.

[Stu08]

Christian Stump. “\(q,t\)-\(\rm Fu\)ß-Catalan numbers for complex reflection groups”. In: 20th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2008). Discrete Math. Theor. Comput. Sci. Proc., AJ. Assoc. Discrete Math. Theor. Comput. Sci., Nancy, 2008, pp. 295–306. arXiv: 0806.2936.

[Stu10]

Christian Stump. “\(q\), \(t\)-Fuß-Catalan numbers for finite reflection groups”. In: J. Algebraic Combin. 32.1 (2010), pp. 67–97. arXiv: 0901.1574. url: https://doi.org/10.1007/s10801-009-0205-0.