login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001181 Number of Baxter permutations of length n.
(Formerly M1661 N0652)
12
0, 1, 2, 6, 22, 92, 422, 2074, 10754, 58202, 326240, 1882960, 11140560, 67329992, 414499438, 2593341586, 16458756586, 105791986682, 687782586844, 4517543071924, 29949238543316, 200234184620736, 1349097425104912, 9154276618636016 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

REFERENCES

E. Ackerman et al., On the number of rectangular partitions, SODA '04, 2004.

Bonichon, Nicolas; Bousquet-Mélou, Mireille; Fusy, Éric; Baxter permutations and plane bipolar orientations. Sem. Lothar. Combin. 61A (2009/10), Art. B61Ah, 29 pp.

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.

W. M. Boyce, Generation of a class of permutations associated with commuting functions, Math. Algorithms, 2 (1967), 19-26.

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, 2014

G. Chatel, V. Pilaud, The Cambrian and Baxter-Cambrian Hopf Algebras, arXiv preprint arXiv:1411.3704, 2014

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).

Chung, F. R. K., Graham, R. L., Hoggatt, V. E., Jr. and Kleiman, M., The number of Baxter permutations. J. Combin. Theory Ser. A 24 (1978), no. 3, 382-394.

Doslic, Tomislav and Veljan, Darko. Logarithmic behavior of some combinatorial sequences. Discrete Math. 308 (2008), no. 11, 2182--2212. MR2404544 (2009j:05019) - From N. J. A. Sloane, May 01 2012

S. Dulucq and O. Guibert, Stack words, standard tableaux and Baxter permutations, Discr. Math., 157 (1996), 91-106.

Dulucq, S.; Guibert, O. Baxter permutations. Proceedings of the 7th Conference on Formal Power Series and Algebraic Combinatorics (Noisy-le-Grand, 1995). 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 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 preprint arXiv:1411.6581, 2014

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.

S. Kitaev, Patterns in Permutations and Words, Springer-Verlag, 2011. see p. 399 Table A.7

Reiner, V.; Stanton, D.; and Welker, V., The Charney-Davis quantity for certain graded posets. Sem. Lothar. Combin. 50 (2003/04), Art. B50c, 13 pp.

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

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, arXiv:1011.1889 [math.CO]

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

H. Canary, Aztec diamonds and Baxter permutations, arXiv:math.CO/0309135.

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.

S. Dulucq and O. Guibert, Permutations de Baxter

Vincent Pilaud, Brick polytopes, lattice quotients, and Hopf algebras, arXiv preprint, 2015.

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), n>1. - Michael Somos, Jul 19 2002

(n+2)(n+3)a(n) = (7n^2+7n-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],[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

a(n) ~ 2^(3*n+5)/(Pi*sqrt(3)*n^4). - Vaclav Kotesovec, Oct 01 2012

EXAMPLE

a(4) = 22 since all permutations of length 4 are Baxter except 2413 and 3142. - Michael Somos, Jul 19 2002

x + 2*x^2 + 6*x^3 + 22*x^4 + 92*x^5 + 422*x^6 + 2074*x^7 + 10754*x^8 + ...

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 *)

PROG

(PARI) alias(C, binomial); {a(n) = if( n<0, 0, 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))))} /* 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

CROSSREFS

Cf. A001183, A001185, A046996.

Cf. A006002, A007318.

Sequence in context: A107591 A155866 A150273 * A130579 A107945 A014330

Adjacent sequences:  A001178 A001179 A001180 * A001182 A001183 A001184

KEYWORD

nonn,nice,easy

AUTHOR

N. J. A. Sloane, Simon Plouffe

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 | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified September 4 18:04 EDT 2015. Contains 261338 sequences.