|
| |
|
|
A001181
|
|
Number of Baxter permutations of length n.
(Formerly M1661 N0652)
|
|
11
|
|
|
|
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.
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.
H. Canary, Aztec diamonds and Baxter permutations, arXiv:math.CO/0309135.
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
T. Y. Chow, H. Eriksson and C. K. Fan, Chess tableaux, Elect. J. Combin., 11 (2) (2005), #A3.
S. Dulucq and O. Guibert, Permutations de Baxter
|
|
|
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,changed
|
|
|
AUTHOR
|
N. J. A. Sloane, Simon Plouffe
|
|
|
EXTENSIONS
|
Additional comments from Michael Somos, Jul 19 2002.
|
|
|
STATUS
|
approved
|
| |
|
|
