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

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

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, 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 pairs of twin binary trees, Journal of Algebra, Volume 360, Jun 15 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], 2010-2012.

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.CO/0309135.

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.

S. Dulucq and O. Guibert, Permutations de Baxter

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

P. Gawrychowski, P. K. Nicholson, Optimal Encodings for Range Top-k, Selection, and Min-Max, arXiv preprint arXiv:1411.6581 [cs.DS], 2014-2015.

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

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

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, A006002, A007318.

Sequence in context: A155866 A150273 A264868 * 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.

License Agreements, Terms of Use, Privacy Policy .

Last modified July 1 12:57 EDT 2016. Contains 274320 sequences.