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

 

Logo

Invitation: celebrating 50 years of OEIS, 250000 sequences, and Sloane's 75th, there will be a conference at DIMACS, Rutgers, Oct 9-10 2014.

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-Melou, Mireille; Fusy, Eric; Baxter permutations and plane bipolar orientations. Sem. Lothar. Combin. 61A (2009/10), Art. B61Ah, 29 pp.

F. Bousquet-M\'{e}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-Melou, Mireille; Fusy, Eric; 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) - From N. J. A. Sloane, Jun 03 2012

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.

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] - From N. J. A. Sloane, Dec 27 2012

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

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 30 08:06 EDT 2014. Contains 247418 sequences.