|
| |
|
|
A001181
|
|
Number of Baxter permutations of length n (also called Baxter numbers).
(Formerly M1661 N0652)
|
|
40
|
|
|
|
1, 1, 2, 6, 22, 92, 422, 2074, 10754, 58202, 326240, 1882960, 11140560, 67329992, 414499438, 2593341586, 16458756586, 105791986682, 687782586844, 4517543071924, 29949238543316, 200234184620736, 1349097425104912, 9154276618636016, 62522506583844272
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,3
|
|
|
COMMENTS
|
As shown by Dulucq and Guilbert (see for example "Baxter Permutations", Discrete Math., 1998), a(n) is also the number of possible paths for three vicious walkers of length n-1 (a.k.a. "vicious 3-watermelons") [Essam & Guttmann (1995), Eq. (63)], Jensen (2017), Eqs. (1), (2)]. The proof follows easily by comparing Ollerton's recurrence here and the recurrence in Eq. (60) of Essam & Guttmann. In fact, as discussed by Dulucq and Guilbert, this interpretation of the sequence has been known for a long time. - N. J. A. Sloane, Mar 19 2021; additional references provided by Olivier Gerard, Mar 22 2021.
a(n) is also the number of meanders with n top arches that as the number of arches is reduced by combining the first and last arches every even number of arches produces a meander.
Example: For n = 4, this meander has this trait.
/\ arches= 8
/\ / \
/ \ --> /\ //\ \
Starting meander: /\ /\ / /\ \ Split and /\/\//\\ ///\\/\\
\ \/ \ \/ / / rotate
\ \ / / bottom arches /\
\ \/ / / \ arches= 7
\ / / /\\ /\
\ / Combine start //\//\\\ //\\/\
\ / first arch with
meander: \/ end of last arch
/\ /\
/\ / \ Combine arches /\ //\\ arches= 6
\ \ / /\ \ again then /\ //\\ ///\\\
\ \ \/ / / rotate and join
\ \ / / <-- /\
\ \/ / //\\ /\ arches= 5
\ / Combine ///\\\ //\\
\/ /\
meander: / \
/ /\ \ Combine /\
\/ \/ <-- //\\ /\/\ arches= 4
/\
Combine /\ //\\ arches= 3
meander: /\ Combine
\/ <-- /\ /\ arches= 2
(End)
|
|
|
REFERENCES
|
Arthur T. Benjamin and Naiomi T. Cameron, Counting on determinants, American Mathematical Monthly, 112.6 (2005): 481-492.
W. M. Boyce, Generation of a class of permutations associated with commuting functions, Math. Algorithms, 2 (1967), 19-26.
William M. Boyce, Commuting functions with no common fixed point, Transactions of the American Mathematical Society 137 (1969): 77-92.
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).
S. Dulucq and O. Guibert, Baxter permutations, Proceedings of the 7th Conference on Formal Power Series and Algebraic Combinatorics (Noisy-le-Grand, 1995).
J. W. Essam and A. J. Guttmann, Vicious walkers and directed polymer networks in general dimensions, Physical Review E, 52(6), 1995, pp. 5849ff. See (60) and (63).
Iwan Jensen, Three friendly walkers, Journal of Physics A: Mathematical and Theoretical, Volume 50:2 (2017), #24003, 14 pages; https://doi.org/10.1088/1751-8121/50/2/024003. See (1), (2).
S. Kitaev, Patterns in Permutations and Words, Springer-Verlag, 2011. See p. 399, Table A.7.
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.
Doron Zeilberger, The method of creative telescoping, J. Symb. Comput. 11.3 (1991): 195-204. See Section 7.8.
|
|
|
LINKS
|
A. Asinowski, G. Barequet, M. Bousquet-Mélou, T. Mansour, and R. Pinter, Orders induced by segments in floorplans and (2-14-3,3-41-2)-avoiding permutations, Electronic Journal of Combinatorics, 20:2 (2013), Paper P35; also arXiv preprint arXiv:1011.1889 [math.CO], 2010-2012.
Jean-Christophe Aval, Adrien Boussicault, Mathilde Bouvel, Olivier Guibert, and Matteo Silimbani, Baxter Tree-like Tableaux, arXiv:2108.06212 [math.CO], 2021.
T. Y. Chow, H. Eriksson, and C. K. Fan, Chess tableaux, Elect. J. Combin., 11 (2) (2005), #A3.
S. Dulucq and O. Guibert, Baxter permutations, Discrete Math. 180 (1998), no. 1-3, 143--156. MR1603713 (99c:05004).
|
|
|
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), if n>1. [Stanley, 1999] - Michael Somos, Jul 19 2002
D-finite with recurrence (n + 2)*(n + 3)*a(n) = (7*n^2 + 7*n - 2)*a(n-1) + 8*(n - 1)*(n - 2)*a(n-2), a(0) = a(1) = 1.
a(n) = hypergeom([-1 - n, -n, 1 - n], [2, 3], -1). (End)
[The coefficients of the polynomials p(n, x) = hypergeom([-1-n, -n, 1-n], [2, 3], -x) are given by the triangular form of A056939. - Peter Luschny, Dec 28 2022]
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
0 = +a(n)*(+a(n+1)*(+512*a(n+2) + 2624*a(n+3) - 960*a(n+4)) +a(n+2)*(-1216*a(n+2) + 3368*a(n+3) - 1560*a(n+4)) + a(n+3)*(+600*a(n+3) + 120*a(n+4))) + a(n+1)*(+a(n+1)*(-64*a(n+2) - 1288*a(n+3) + 600*a(n+4)) +a(n+2)*(-136*a(n+2) + 295*a(n+3) - 421*a(n+4)) +a(n+3)*(+161*a(n+3) + 41*a(n+4))) + a(n+2)*(+a(n+2)*(+72*a(n+2) + 17*a(n+3) - 19*a(n+4)) + a(n+3)*(-a(n+3) - a(n+4))) if n>=0. - Michael Somos, Mar 09 2017
G.f.: ((x^3+3*x^2+3*x+1)/(1-8*x)^(3/4)*hypergeom([1/4, 5/4],[2],64*x*(1+x)^3/(8*x-1)^3) - 1 + x)/(3*x^2). - Mark van Hoeij, Nov 05 2023
|
|
|
EXAMPLE
|
G.f. = x + 2*x^2 + 6*x^3 + 22*x^4 + 92*x^5 + 422*x^6 + 2074*x^7 + ...
a(4) = 22 since all permutations of length 4 are Baxter except 2413 and 3142. - Michael Somos, Jul 19 2002
|
|
|
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;
# second Maple program:
a:= proc(n) option remember; `if`(n<2, 1,
((7*n^2+7*n-2)*a(n-1)+8*(n-1)*(n-2)*a(n-2))/((n+2)*(n+3)))
end:
|
|
|
MATHEMATICA
|
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) {a(n) = if( n<0, 0, sum( k=1, n, binomial(n+1, k-1) * binomial(n+1, k) * binomial(n+1, k+1) / (binomial(n+1, 1) * binomial(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)
(Python)
from sympy import binomial as C
def a(n): return sum([(C(n + 1, k - 1)*C(n + 1, k)*C(n + 1, k + 1))/(C(n + 1, 1) * C(n + 1, 2)) for k in range(1, n + 1)]) # Indranil Ghosh, Apr 25 2017
(Magma) [0] cat [2*(&+[Binomial(n+1, k-1)*Binomial(n+1, k)* Binomial(n+1, k+1): k in [1..n]])/(n*(n+1)^2): n in [1..30]]; // G. C. Greubel, Jul 24 2019
(Sage) [0]+[2*sum(binomial(n+1, k-1)*binomial(n+1, k)*binomial(n+1, k+1) for k in (1..n))/(n*(n+1)^2) for n in (1..30)] # G. C. Greubel, Jul 24 2019
(GAP) Concatenation([0], List([1..30], n-> 2*Sum([1..n], k-> Binomial(n+1, k-1)*Binomial(n+1, k)* Binomial(n+1, k+1) )/(n*(n+1)^2) )); # G. C. Greubel, Jul 24 2019
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,nice,easy
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
Changed initial term to a(0)=1 (it was a(0)=0, but there were compelling reasons to change it). - N. J. A. Sloane, Sep 14 2021
|
|
|
STATUS
|
approved
|
| |
|
|
