|
%I M1661 N0652 #307 Feb 09 2024 14:24:33
%S 1,1,2,6,22,92,422,2074,10754,58202,326240,1882960,11140560,67329992,
%T 414499438,2593341586,16458756586,105791986682,687782586844,
%U 4517543071924,29949238543316,200234184620736,1349097425104912,9154276618636016,62522506583844272
%N Number of Baxter permutations of length n (also called Baxter numbers).
%C As shown by Dulucq and Guilbert (see for example "Baxter Permutations", Discrete Math., 1998), a(n) is also the number of possible paths for three vicious walkers of length n-1 (a.k.a. "vicious 3-watermelons") [Essam & Guttmann (1995), Eq. (63)], Jensen (2017), Eqs. (1), (2)]. The proof follows easily by comparing Ollerton's recurrence here and the recurrence in Eq. (60) of Essam & Guttmann. In fact, as discussed by Dulucq and Guilbert, this interpretation of the sequence has been known for a long time. - _N. J. A. Sloane_, Mar 19 2021; additional references provided by _Olivier Gerard_, Mar 22 2021.
%C From _Roger Ford_, Apr 11 2020: (Start)
%C a(n) is also the number of meanders with n top arches that as the number of arches is reduced by combining the first and last arches every even number of arches produces a meander.
%C Example: For n = 4, this meander has this trait.
%C /\ arches= 8
%C /\ / \
%C / \ --> /\ //\ \
%C Starting meander: /\ /\ / /\ \ Split and /\/\//\\ ///\\/\\
%C \ \/ \ \/ / / rotate
%C \ \ / / bottom arches /\
%C \ \/ / / \ arches= 7
%C \ / / /\\ /\
%C \ / Combine start //\//\\\ //\\/\
%C \ / first arch with
%C meander: \/ end of last arch
%C /\ /\
%C /\ / \ Combine arches /\ //\\ arches= 6
%C \ \ / /\ \ again then /\ //\\ ///\\\
%C \ \ \/ / / rotate and join
%C \ \ / / <-- /\
%C \ \/ / //\\ /\ arches= 5
%C \ / Combine ///\\\ //\\
%C \/ /\
%C meander: / \
%C / /\ \ Combine /\
%C \/ \/ <-- //\\ /\/\ arches= 4
%C /\
%C Combine /\ //\\ arches= 3
%C meander: /\ Combine
%C \/ <-- /\ /\ arches= 2
%C (End)
%D Arthur T. Benjamin and Naiomi T. Cameron, Counting on determinants, American Mathematical Monthly, 112.6 (2005): 481-492.
%D W. M. Boyce, Generation of a class of permutations associated with commuting functions, Math. Algorithms, 2 (1967), 19-26.
%D William M. Boyce, Commuting functions with no common fixed point, Transactions of the American Mathematical Society 137 (1969): 77-92.
%D T. Y. Chow, Review of "Bonichon, Nicolas; Bousquet-Mélou, Mireille; Fusy, Éric; Baxter permutations and plane bipolar orientations. Sem. Lothar. Combin. 61A (2009/10), Art. B61Ah, 29 pp.", MathSciNet Review MR2734180 (2011m:05023).
%D S. Dulucq and O. Guibert, Baxter permutations, Proceedings of the 7th Conference on Formal Power Series and Algebraic Combinatorics (Noisy-le-Grand, 1995).
%D J. W. Essam and A. J. Guttmann, Vicious walkers and directed polymer networks in general dimensions, Physical Review E, 52(6), 1995, pp. 5849ff. See (60) and (63).
%D Iwan Jensen, Three friendly walkers, Journal of Physics A: Mathematical and Theoretical, Volume 50:2 (2017), #24003, 14 pages; https://doi.org/10.1088/1751-8121/50/2/024003. See (1), (2).
%D S. Kitaev, Patterns in Permutations and Words, Springer-Verlag, 2011. See p. 399, Table A.7.
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 6.55.
%D Doron Zeilberger, The method of creative telescoping, J. Symb. Comput. 11.3 (1991): 195-204. See Section 7.8.
%H Alois P. Heinz, <a href="/A001181/b001181.txt">Table of n, a(n) for n = 0..1119</a> (first 101 terms from T. D. Noe)
%H E. Ackerman et al., <a href="http://sci.haifa.ac.il/~ackerman/publications/soda04.pdf">On the number of rectangular partitions</a>, SODA '04, 2004.
%H A. Asinowski, G. Barequet, M. Bousquet-Mélou, T. Mansour, and R. Pinter, <a href="https://doi.org/10.37236/2607">Orders induced by segments in floorplans and (2-14-3,3-41-2)-avoiding permutations</a>, Electronic Journal of Combinatorics, 20:2 (2013), Paper P35; also arXiv preprint <a href="https://arxiv.org/abs/1011.1889">arXiv:1011.1889 [math.CO]</a>, 2010-2012.
%H Andrei Asinowski, Jean Cardinal, Stefan Felsner, and Éric Fusy, <a href="https://arxiv.org/abs/2402.01483">Combinatorics of rectangulations: Old and new bijections</a>, arXiv:2402.01483 [math.CO], 2024. See p. 10.
%H Jean-Christophe Aval, Adrien Boussicault, Mathilde Bouvel, Olivier Guibert, and Matteo Silimbani, <a href="https://arxiv.org/abs/2108.06212">Baxter Tree-like Tableaux</a>, arXiv:2108.06212 [math.CO], 2021.
%H N. R. Beaton, M. Bouvel, V. Guerrini, and S. Rinaldi, <a href="http://arxiv.org/abs/1511.04864">Slicings of parallelogram polyominoes, or how Baxter and Schroeder can be reconciled</a>, arXiv preprint arXiv:1511.04864 [math.CO], 2015.
%H Nicolas Bonichon, Mireille Bousquet-Mélou, and Éric Fusy, <a href="http://www.mat.univie.ac.at/~slc/wpapers/s61Abobofu.html">Baxter permutations and plane bipolar orientations</a>, Sem. Lothar. Combin. 61A (2009/10), Art. B61Ah, 29 pp.
%H Nicolas Bonichon and Pierre-Jean Morel, <a href="https://arxiv.org/abs/2202.12677">Baxter d-permutations and other pattern avoiding classes</a>, arXiv:2202.12677 [math.CO], 2022.
%H Alin Bostan, Jordan Tirrell, Bruce W. Westbury, and Yi Zhang, <a href="https://arxiv.org/abs/1911.10288">On sequences associated to the invariant theory of rank two simple Lie algebras</a>, arXiv:1911.10288 [math.CO], 2019.
%H Alin Bostan, Jordan Tirrell, Bruce W. Westbury, and Yi Zhang, <a href="https://arxiv.org/abs/2110.13753">On some combinatorial sequences associated to invariant theory</a>, arXiv:2110.13753 [math.CO], 2021.
%H F. Bousquet-Mélou, <a href="https://doi.org/10.37236/1691">Four classes of pattern-avoiding permutations under one roof: generating trees with two labels</a>, Electron. J. Combin. 9 (2002/03), no. 2, Research paper 19, 31 pp.
%H Mathilde Bouvel, Veronica Guerrini, Andrew Rechnitzer, and Simone Rinaldi, <a href="https://arxiv.org/abs/1702.04529">Semi-Baxter and strong-Baxter: two relatives of the Baxter sequence</a>, arXiv:1702.04529 [math.CO], 2017.
%H W. M. Boyce, <a href="/A001181/a001181_1.pdf">Generation of a class of permutations associated with commuting functions</a>, 1967; annotated and corrected scanned copy.
%H W. M. Boyce, <a href="/A001181/a001181.jpg">Correction to page 25 (Part 1)</a>
%H W. M. Boyce, <a href="/A001181/a001181_1.jpg">Correction to Page 25 (Part 2)</a>
%H W. M. Boyce, <a href="/A001181/a001181.pdf">Baxter Permutations and Functional Composition</a>, Unpublished Memorandum, Jan 26 1978
%H S. Burrill, S. Melczer, and M. Mishna, <a href="http://arxiv.org/abs/1411.6606">A Baxter class of a different kind, and other bijective results using tableau sequences ending with a row shape</a>, arXiv preprint arXiv:1411.6606 [math.CO], 2014-2015.
%H H. Canary, <a href="http://arxiv.org/abs/math/0309135">Aztec diamonds and Baxter permutations</a>, arXiv:math/0309135 [math.CO], 2003-2004.
%H G. Chatel and V. Pilaud, <a href="http://arxiv.org/abs/1411.3704">Cambrian Hopf Algebras</a>, arXiv:1411.3704 [math.CO], 2014-2015. and <a href="https://doi.org/10.1016/j.aim.2017.02.027">[DOI]</a>
%H T. Y. Chow, H. Eriksson, and C. K. Fan, <a href="https://doi.org/10.37236/1895">Chess tableaux</a>, Elect. J. Combin., 11 (2) (2005), #A3.
%H F. R. K. Chung, R. L. Graham, V. E. Hoggatt Jr., and M. Kleiman, <a href="https://doi.org/10.1016/0097-3165(78)90068-7">The number of Baxter permutations</a> J. Combin. Theory Ser. A 24 (1978), no. 3, 382-394.
%H J. Cranch, <a href="http://jdc41.user.srcf.net/research/pasting/Pasting.pdf">Representing and Enumerating Two-Dimensional Pasting Diagrams</a>, 2014.
%H CombOS - Combinatorial Object Server, <a href="http://combos.org/rect">Generate diagonal rectangulations</a>
%H Colin Defant, <a href="https://arxiv.org/abs/1809.03123">Stack-Sorting Preimages of Permutation Classes</a>, arXiv:1809.03123 [math.CO], 2018.
%H Anand Deopurkar, Eduard Duryev, and Anand Patel, <a href="https://arxiv.org/abs/1901.01513">Ramification divisors of general projections</a>, arXiv:1901.01513 [math.AG], 2019.
%H Tomislav Došlic and Darko Veljan, <a href="http://dx.doi.org/10.1016/j.disc.2007.04.066">Logarithmic behavior of some combinatorial sequences</a>, Discrete Math. 308 (2008), no. 11, 2182--2212. MR2404544 (2009j:05019).
%H S. Dulucq and O. Guibert, <a href="http://www.mat.univie.ac.at/~slc/opapers/s33dulgui.html">Permutations de Baxter</a>, Séminaire Lotharingien de Combinatoire, B33c (1994), 9 pp.
%H S. Dulucq and O. Guibert, <a href="http://dx.doi.org/10.1016/S0012-365X(96)83009-3">Stack words, standard tableaux and Baxter permutations</a>, Disc. Math. 157 (1996), 91-106.
%H S. Dulucq and O. Guibert, <a href="https://doi.org/10.1016/S0012-365X(97)00112-X">Baxter permutations</a>, Discrete Math. 180 (1998), no. 1-3, 143--156. MR1603713 (99c:05004).
%H Stefan Felsner, Eric Fusy, Marc Noy, and David Orden, <a href="https://doi.org/10.1016/j.jcta.2010.03.017">Bijections for Baxter families and related objects</a>, J. Combin. Theory Ser. A, 118(3):993-1020, 2011.
%H D. C. Fielder and C. O. Alford, <a href="/A000108/a000108_19.pdf">An investigation of sequences derived from Hoggatt Sums and Hoggatt Triangles</a>, Application of Fibonacci Numbers, 3 (1990) 77-88. Proceedings of 'The Third Annual Conference on Fibonacci Numbers and Their Applications,' Pisa, Italy, July 25-29, 1988. (Annotated scanned copy)
%H D. C. Fielder and C. O. Alford, <a href="http://www.fq.math.ca/Scanned/27-2/fielder.pdf">On a conjecture by Hoggatt with extensions to Hoggatt sums and Hoggatt triangles</a>, Fib. Quart., 27 (1989), 160-168.
%H P. Gawrychowski and P. K. Nicholson, <a href="https://arxiv.org/abs/1411.6581">Optimal Encodings for Range Top-k, Selection, and Min-Max</a>, arXiv:1411.6581 [cs.DS], 2014-2015.
%H P. Gawrychowski and P. K. Nicholson, <a href="https://doi.org/10.1007/978-3-662-47672-7_48">Optimal Encodings for Range Top-k, Selection, and Min-Max</a>, in Automata, Languages, and Programming, Volume 9134 of the series Lecture Notes in Computer Science, 2015, pp. 593-604.
%H S. Giraudo, <a href="https://doi.org/10.46298/dmtcs.2919">Algebraic and combinatorial structures on Baxter permutations</a>, DMTCS proc. AO, FPSAC 2011 Rykjavik, (2011) 387-398.
%H S. Giraudo, <a href="http://arxiv.org/abs/1204.4776">Algebraic and combinatorial structures on pairs of twin binary trees</a>, arXiv:1204.4776 [math.CO], 2012.
%H S. Giraudo, <a href="http://dx.doi.org/10.1016/j.jalgebra.2012.03.020">Algebraic and combinatorial structures on pairs of twin binary trees</a>, Journal of Algebra, Volume 360, 15 June 2012, Pages 115-157.
%H O. Guibert and S. Linusson, <a href="https://doi.org/10.1016/S0012-365X(99)00261-7">Doubly alternating Baxter permutations are Catalan</a>, Discrete Math., 217 (2000), 157-166.
%H Elizabeth Hartung, Hung Phuc Hoang, Torsten Mütze, and Aaron Williams, <a href="https://arxiv.org/abs/1906.06069">Combinatorial generation via permutation languages. I. Fundamentals</a>, arXiv:1906.06069 [cs.DM], 2019.
%H V. E. Hoggatt, Jr., <a href="/A006542/a006542.pdf">Letter to N. J. A. Sloane, Apr 1977</a>
%H Don Knuth, <a href="https://www.youtube.com/watch?v=zg6YRqT4Duo">Twintrees, Baxter Permutations, and Floorplans</a>, Christmas Lecture, Stanford 2022 (YouTube video).
%H Laszlo Kozma and T. Saranurak, <a href="http://arxiv.org/abs/1603.08151">Binary search trees and rectangulations</a>, arXiv preprint arXiv:1603.08151 [cs.DS], 2016.
%H Megan A. Martinez and Carla D. Savage, <a href="https://arxiv.org/abs/1609.08106">Patterns in Inversion Sequences II: Inversion Sequences Avoiding Triples of Relations</a>, arXiv:1609.08106 [math.CO], 2016 [Section 2.25].
%H Arturo Merino and Torsten Mütze, <a href="https://arxiv.org/abs/2103.09333">Combinatorial generation via permutation languages. III. Rectangulations</a>, arXiv:2103.09333 [math.CO], 2021.
%H A. Peder and M. Tombak, <a href="https://doi.org/10.1007/978-3-642-18381-2_38">Finding the description of structure by counting method: a case study</a>, SOFSEM 2011, LNCS 6543 (2011) 455-466 doi:10.1007/978-3-642-18381-2_38.
%H Vincent Pilaud, <a href="http://arxiv.org/abs/1505.07665">Brick polytopes, lattice quotients, and Hopf algebras</a>, arXiv:1505.07665 [math.CO], 2015.
%H V. Reiner, D. Stanton, and V. Welker, <a href="https://www.emis.de/journals/SLC/wpapers/s50reistwel.html">The Charney-Davis quantity for certain graded posets</a>, Sem. Lothar. Combin. 50 (2003/04), Art. B50c, 13 pp.
%H Jannik Silvanus, <a href="http://hdl.handle.net/20.500.11811/7936">Improved Cardinality Bounds for Rectangle Packing Representations</a>, Doctoral Dissertation, University of Bonn (Rheinische Friedrich Wilhelms Universität, Germany 2019).
%H N. J. A. Sloane, <a href="/A001181/a001181_3.pdf">Three vicious walkers of lengths 1, 2, and 3</a>
%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Baxter_permutation">Baxter permutation</a>
%F a(n) = Sum_{k=1..n} C(n+1,k-1) * C(n+1,k) * C(n+1,k+1) / (C(n+1,1) * C(n+1,2)).
%F (n + 1)*(n + 2)*(n + 3)*(3*n - 2)*a(n) = 2*(n + 1)*(9*n^3 + 3*n^2 - 4*n + 4)*a(n - 1) + (3*n - 1)*(n - 2)*(15*n^2 - 5*n - 14)*a(n - 2) + 8*(3*n + 1)*(n - 2)^2*(n - 3)*a(n - 3), if n>1. [Stanley, 1999] - _Michael Somos_, Jul 19 2002
%F From _Richard L. Ollerton_, Sep 13 2006: (Start)
%F D-finite with recurrence (n + 2)*(n + 3)*a(n) = (7*n^2 + 7*n - 2)*a(n-1) + 8*(n - 1)*(n - 2)*a(n-2), a(0) = a(1) = 1.
%F a(n) = hypergeom([-1 - n, -n, 1 - n], [2, 3], -1). (End)
%F [The coefficients of the polynomials p(n, x) = hypergeom([-1-n, -n, 1-n], [2, 3], -x) are given by the triangular form of A056939. - _Peter Luschny_, Dec 28 2022]
%F G.f.: -1 + (1/(3*x^2)) * (x-1 + (1-2*x)*hypergeom([-2/3, 2/3],[1],27*x^2/(1-2*x)^3) - (8*x^3-11*x^2-x)*hypergeom([1/3, 2/3],[2],27*x^2/(1-2*x)^3)/(1-2*x)^2 ). - _Mark van Hoeij_, Oct 23 2011
%F a(n) ~ 2^(3*n+5)/(Pi*sqrt(3)*n^4). - _Vaclav Kotesovec_, Oct 01 2012
%F 0 = +a(n)*(+a(n+1)*(+512*a(n+2) + 2624*a(n+3) - 960*a(n+4)) +a(n+2)*(-1216*a(n+2) + 3368*a(n+3) - 1560*a(n+4)) + a(n+3)*(+600*a(n+3) + 120*a(n+4))) + a(n+1)*(+a(n+1)*(-64*a(n+2) - 1288*a(n+3) + 600*a(n+4)) +a(n+2)*(-136*a(n+2) + 295*a(n+3) - 421*a(n+4)) +a(n+3)*(+161*a(n+3) + 41*a(n+4))) + a(n+2)*(+a(n+2)*(+72*a(n+2) + 17*a(n+3) - 19*a(n+4)) + a(n+3)*(-a(n+3) - a(n+4))) if n>=0. - _Michael Somos_, Mar 09 2017
%F G.f.: ((x^3+3*x^2+3*x+1)/(1-8*x)^(3/4)*hypergeom([1/4, 5/4],[2],64*x*(1+x)^3/(8*x-1)^3) - 1 + x)/(3*x^2). - _Mark van Hoeij_, Nov 05 2023
%e G.f. = x + 2*x^2 + 6*x^3 + 22*x^4 + 92*x^5 + 422*x^6 + 2074*x^7 + ...
%e a(4) = 22 since all permutations of length 4 are Baxter except 2413 and 3142. - _Michael Somos_, Jul 19 2002
%p C := binomial; A001181 := proc(n) local k; add(C(n+1,k-1)*C(n+1,k)*C(n+1,k+1)/(C(n+1,1)*C(n+1,2)),k=1..n); end;
%p # second Maple program:
%p a:= proc(n) option remember; `if`(n<2, 1,
%p ((7*n^2+7*n-2)*a(n-1)+8*(n-1)*(n-2)*a(n-2))/((n+2)*(n+3)))
%p end:
%p seq(a(n), n=0..24); # _Alois P. Heinz_, Jul 29 2022
%t A001181[n_] := HypergeometricPFQ[{-1-n, -n, 1-n}, {2, 3}, -1] (* _Richard L. Ollerton_, Sep 13 2006 *)
%t a[0]=0; a[1]=1; a[n_] := a[n] = ((7n^2+7n-2)*a[n-1] + 8(n-1)(n-2)*a[n-2]) / ((n+2)(n+3)); Table[a[n], {n, 0, 30}] (* _Jean-François Alcover_, Oct 28 2015, from 3rd formula *)
%o (PARI) {a(n) = if( n<0, 0, sum( k=1, n, binomial(n+1, k-1) * binomial(n+1, k) * binomial(n+1, k+1) / (binomial(n+1, 1) * binomial(n+1, 2))))}; /* _Michael Somos_, Jul 19 2002 */
%o (Haskell)
%o a001181 0 = 0
%o a001181 n =
%o (sum $ map (\k -> product $ map (a007318 (n+1)) [k-1..k+1]) [1..n])
%o `div` (a006002 n)
%o -- _Reinhard Zumkeller_, Oct 23 2011
%o (Python)
%o from sympy import binomial as C
%o def a(n): return sum([(C(n + 1, k - 1)*C(n + 1, k)*C(n + 1, k + 1))/(C(n + 1, 1) * C(n + 1, 2)) for k in range(1, n + 1)]) # _Indranil Ghosh_, Apr 25 2017
%o (Magma) [0] cat [2*(&+[Binomial(n+1,k-1)*Binomial(n+1,k)* Binomial(n+1, k+1): k in [1..n]])/(n*(n+1)^2): n in [1..30]]; // _G. C. Greubel_, Jul 24 2019
%o (Sage) [0]+[2*sum(binomial(n+1,k-1)*binomial(n+1,k)*binomial(n+1, k+1) for k in (1..n))/(n*(n+1)^2) for n in (1..30)] # _G. C. Greubel_, Jul 24 2019
%o (GAP) Concatenation([0], List([1..30], n-> 2*Sum([1..n], k-> Binomial(n+1,k-1)*Binomial(n+1,k)* Binomial(n+1, k+1) )/(n*(n+1)^2) )); # _G. C. Greubel_, Jul 24 2019
%Y Cf. A001183, A001185, A046996, A006002, A007318, A056939, A359363.
%K nonn,nice,easy
%O 0,3
%A _N. J. A. Sloane_, _Simon Plouffe_
%E Changed initial term to a(0)=1 (it was a(0)=0, but there were compelling reasons to change it). - _N. J. A. Sloane_, Sep 14 2021
|
