|
| |
|
|
A001181
|
|
Number of Baxter permutations of length n.
(Formerly M1661 N0652)
|
|
6
| |
|
|
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; 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.
S. Dulucq and O. Guibert, Stack words, standard tableaux and Baxter permutations, Discr. Math., 157 (1996), 91-106.
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.
O. Guibert and S. Linusson, Doubly alternating Baxter permutations are Catalan, Discrete Math., 217 (2000), 157-166.
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
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
| Sum from {k=1} to {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.
(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
|
|
|
EXAMPLE
| a(4)=22 since all permutations of length 4 are Baxter except 2413 and 3142.
|
|
|
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)))
(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 (njas(AT)research.att.com), Simon Plouffe (simon.plouffe(AT)gmail.com)
|
|
|
EXTENSIONS
| Additional comments from Michael Somos, Jul 19 2002.
|
| |
|
|
