The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation. Please make a donation to keep the OEIS running. We are now in our 56th year. In the past year we added 10000 new sequences and reached almost 9000 citations (which often say "discovered thanks to the OEIS"). Other ways to donate

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A001181 Number of Baxter permutations of length n. (Formerly M1661 N0652) 14
 0, 1, 2, 6, 22, 92, 422, 2074, 10754, 58202, 326240, 1882960, 11140560, 67329992, 414499438, 2593341586, 16458756586, 105791986682, 687782586844, 4517543071924, 29949238543316, 200234184620736, 1349097425104912, 9154276618636016, 62522506583844272 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,3 COMMENTS From Roger Ford, Apr 11 2020: (Start) a(n) is 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. Example: For n = 4, this meander has this trait.                                                                   /\    arches= 8                                   /\                             /  \                                  /  \    -->               /\   //\  \      Starting meander:  /\  /\  / /\ \   Split and    /\/\//\\ ///\\/\\                         \ \/  \ \/ / /   rotate                          \     \  / /    bottom arches    /\                           \     \/ /                     /  \           arches= 7                            \      /                     /  /\\   /\                             \    /    Combine start    //\//\\\ //\\/\                              \  /     first arch with       meander:                \/      end of last arch           /\                                                       /\    /\    /  \                         Combine arches        /\    //\\  arches= 6    \ \  / /\ \                        again then        /\ //\\  ///\\\     \ \ \/ / /                        rotate and join      \ \  / /                         <--                  /\       \ \/ /                                              //\\   /\     arches= 5        \  /                           Combine            ///\\\ //\\         \/         /\        meander:   /  \                  / /\ \               Combine              /\                  \/  \/               <--                 //\\ /\/\     arches= 4                                                                /\                                       Combine              /\ //\\      arches= 3       meander:  /\                    Combine                 \/                    <--                   /\ /\ arches= 2 (End) REFERENCES W. M. Boyce, Generation of a class of permutations associated with commuting functions, Math. Algorithms, 2 (1967), 19-26. 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). Dulucq, S.; Guibert, O. Baxter permutations. Proceedings of the 7th Conference on Formal Power Series and Algebraic Combinatorics (Noisy-le-Grand, 1995). S. Kitaev, Patterns in Permutations and Words, Springer-Verlag, 2011. see p. 399 Table A.7 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence). N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence). R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 6.55. LINKS T. D. Noe, Table of n, a(n) for n = 0..100 E. Ackerman et al., On the number of rectangular partitions, SODA '04, 2004. A. Asinowski, G. Barequet, M. Bousquet-Mélou, T. Mansour, R. Pinter, Orders induced by segments in floorplans and (2-14-3,3-41-2)-avoiding permutations, Electronic Journal of Combinatorics, 20:2 (2013), Paper P35; also arXiv preprint arXiv:1011.1889 [math.CO], 2010-2012. N. R. Beaton, M. Bouvel, V. Guerrini, S. Rinaldi, Slicings of parallelogram polyominoes, or how Baxter and Schroeder can be reconciled, arXiv preprint arXiv:1511.04864 [math.CO], 2015. Nicolas Bonichon, Mireille Bousquet-Mélou, Éric Fusy, Baxter permutations and plane bipolar orientations, Sem. Lothar. Combin. 61A (2009/10), Art. B61Ah, 29 pp. Alin Bostan, Jordan Tirrell, Bruce W. Westbury, Yi Zhang, On sequences associated to the invariant theory of rank two simple Lie algebras, arXiv:1911.10288 [math.CO], 2019. F. Bousquet-Mélou, Four classes of pattern-avoiding permutations under one roof: generating trees with two labels, Electron. J. Combin. 9 (2002/03), no. 2, Research paper 19, 31 pp. Mathilde Bouvel, Veronica Guerrini, Andrew Rechnitzer, Simone Rinaldi, Semi-Baxter and strong-Baxter: two relatives of the Baxter sequence, arXiv:1702.04529 [math.CO], 2017. W. M. Boyce, Generation of a class of permutations associated with commuting functions, 1967; annotated and corrected scanned copy. W. M. Boyce, Correction to page 25 (Part 1) W. M. Boyce, Correction to Page 25 (Part 2) W. M. Boyce, Baxter Permutations and Functional Composition, Unpublished Memorandum, Jan 26 1978 S. Burrill, S. Melczer, M. Mishna, A Baxter class of a different kind, and other bijective results using tableau sequences ending with a row shape, arXiv preprint arXiv:1411.6606 [math.CO], 2014-2015. H. Canary, Aztec diamonds and Baxter permutations, arXiv:math/0309135 [math.CO], 2003-2004. G. Chatel, V. Pilaud, Cambrian Hopf Algebras, arXiv:1411.3704 [math.CO], 2014-2015. T. Y. Chow, H. Eriksson and C. K. Fan, Chess tableaux, Elect. J. Combin., 11 (2) (2005), #A3. J. Cranch, Representing and Enumerating Two-Dimensional Pasting Diagrams, 2014. F. R. K. Chung, R. L. Graham, V. E. Hoggatt Jr. and M. Kleiman, The number of Baxter permutations J. Combin. Theory Ser. A 24 (1978), no. 3, 382-394. Colin Defant, Stack-Sorting Preimages of Permutation Classes, arXiv:1809.03123 [math.CO], 2018. Anand Deopurkar, Eduard Duryev, Anand Patel, Ramification divisors of general projections, arXiv:1901.01513 [math.AG], 2019. Tomislav Došlic, Darko Veljan, Logarithmic behavior of some combinatorial sequences, Discrete Math. 308 (2008), no. 11, 2182--2212. MR2404544 (2009j:05019). S. Dulucq and O. Guibert, Permutations de Baxter, Séminaire Lotharingien de Combinatoire, B33c (1994), 9 pp. S. Dulucq and O. Guibert, Stack words, standard tableaux and Baxter permutations, Disc. Math. 157 (1996), 91-106. S. Dulucq, O. Guibert, Baxter permutations, Discrete Math. 180 (1998), no. 1-3, 143--156. MR1603713 (99c:05004). Stefan Felsner, Eric Fusy, Marc Noy, and David Orden, Bijections for Baxter families and related objects, J. Combin. Theory Ser. A, 118(3):993-1020, 2011. D. C. Fielder & C. O. Alford, An investigation of sequences derived from Hoggatt Sums and Hoggatt Triangles, 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) D. C. Fielder and C. O. Alford, On a conjecture by Hoggatt with extensions to Hoggatt sums and Hoggatt triangles, Fib. Quart., 27 (1989), 160-168. P. Gawrychowski, P. K. Nicholson, Optimal Encodings for Range Top-k, Selection, and Min-Max, arXiv:1411.6581 [cs.DS], 2014-2015. P. Gawrychowski, P. K. Nicholson, Optimal Encodings for Range Top-k, Selection, and Min-Max, in Automata, Languages, and Programming, Volume 9134 of the series Lecture Notes in Computer Science, 2015, pp. 593-604. S. Giraudo, Algebraic and combinatorial structures on Baxter permutations, DMCTS proc. AO, FPSAC 2011 Rykjavik, (2011) 387-398. S. Giraudo, Algebraic and combinatorial structures on pairs of twin binary trees, arXiv:1204.4776 [math.CO], 2012. S. Giraudo, Algebraic and combinatorial structures on pairs of twin binary trees, Journal of Algebra, Volume 360, 15 June 2012, Pages 115-157. O. Guibert and S. Linusson, Doubly alternating Baxter permutations are Catalan, Discrete Math., 217 (2000), 157-166. Elizabeth Hartung, Hung Phuc Hoang, Torsten Mütze, Aaron Williams, Combinatorial generation via permutation languages. I. Fundamentals, arXiv:1906.06069 [cs.DM], 2019. V. E. Hoggatt, Jr., Letter to N. J. A. Sloane, Apr 1977 Laszlo Kozma, T. Saranurak, Binary search trees and rectangulations, arXiv preprint arXiv:1603.08151 [cs.DS], 2016. Megan A. Martinez and Carla D. Savage, Patterns in Inversion Sequences II: Inversion Sequences Avoiding Triples of Relations, arXiv:1609.08106 [math.CO], 2016 [Section 2.25]. A. Peder, M. Tombak, Finding the description of structure by counting method: a case study, SOFSEM 2011, LNCS 6543 (2011) 455-466 doi:10.1007/978-3-642-18381-2_38. Vincent Pilaud, Brick polytopes, lattice quotients, and Hopf algebras, arXiv:1505.07665 [math.CO], 2015. Jannik Silvanus, Improved Cardinality Bounds for Rectangle Packing Representations, Doctoral Dissertation, University of Bonn (Rheinische Friedrich Wilhelms Universität, Germany 2019). V. Reiner, D. Stanton, and V. Welker, The Charney-Davis quantity for certain graded posets, Sem. Lothar. Combin. 50 (2003/04), Art. B50c, 13 pp. Wikipedia, Baxter permutation FORMULA 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)). (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 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. - Richard L. Ollerton (r.ollerton(AT)uws.edu.au), Sep 13 2006 G.f.: -1 + (1/(3*x^2)) * (x-1 + (1-2*x)*hypergeom([-2/3, 2/3],,27*x^2/(1-2*x)^3) - (8*x^3-11*x^2-x)*hypergeom([1/3,  2/3],,27*x^2/(1-2*x)^3)/(1-2*x)^2 ). - Mark van Hoeij, Oct 23 2011 a(n) ~ 2^(3*n+5)/(Pi*sqrt(3)*n^4). - Vaclav Kotesovec, Oct 01 2012 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 EXAMPLE G.f. = x + 2*x^2 + 6*x^3 + 22*x^4 + 92*x^5 + 422*x^6 + 2074*x^7 + ... a(4) = 22 since all permutations of length 4 are Baxter except 2413 and 3142. - Michael Somos, Jul 19 2002 MAPLE 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; MATHEMATICA A001181[n_]:=HypergeometricPFQ[{-1-n, -n, 1-n}, {2, 3}, -1] (* n>0 *) (* Richard L. Ollerton (r.ollerton(AT)uws.edu.au), Sep 13 2006 *) a=0; a=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 *) PROG (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 */ (Haskell) a001181 0 = 0 a001181 n =    (sum \$ map (\k -> product \$ map (a007318 (n+1)) [k-1..k+1]) [1..n])     `div` (a006002 n) -- Reinhard Zumkeller, Oct 23 2011 (Python) from sympy import binomial as C 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 (MAGMA)  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 (Sage) +[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 (GAP) Concatenation(, 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 CROSSREFS Cf. A001183, A001185, A046996, A006002, A007318. Sequence in context: A150273 A303923 A264868 * A130579 A279570 A338748 Adjacent sequences:  A001178 A001179 A001180 * A001182 A001183 A001184 KEYWORD nonn,nice,easy AUTHOR EXTENSIONS Additional comments from Michael Somos, Jul 19 2002 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified December 5 00:34 EST 2020. Contains 338943 sequences. (Running on oeis4.)