A046996 -id:A046996 - cp's OEIS frontend

A001181 Number of Baxter permutations of length n (also called Baxter numbers).

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

Offset: 0

N. J. A. Sloane, Simon Plouffe

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.
From Roger Ford, Apr 11 2020: (Start)
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)

			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

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.

Alois P. Heinz, Table of n, a(n) for n = 0..1119 (first 101 terms from T. D. Noe)
E. Ackerman et al., On the number of rectangular partitions, SODA '04, 2004.
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.
Andrei Asinowski, Jean Cardinal, Stefan Felsner, and Éric Fusy, Combinatorics of rectangulations: Old and new bijections, arXiv:2402.01483 [math.CO], 2024. See p. 10.
Jean-Christophe Aval, Adrien Boussicault, Mathilde Bouvel, Olivier Guibert, and Matteo Silimbani, Baxter Tree-like Tableaux, arXiv:2108.06212 [math.CO], 2021.
N. R. Beaton, M. Bouvel, V. Guerrini, and S. Rinaldi, Slicings of parallelogram polyominoes, or how Baxter and Schroeder can be reconciled, arXiv preprint arXiv:1511.04864 [math.CO], 2015.
Nicolas Bonichon, Mireille Bousquet-Mélou, and Éric Fusy, Baxter permutations and plane bipolar orientations, Sem. Lothar. Combin. 61A (2009/10), Art. B61Ah, 29 pp.
Nicolas Bonichon and Pierre-Jean Morel, Baxter d-permutations and other pattern avoiding classes, arXiv:2202.12677 [math.CO], 2022.
Alin Bostan, Jordan Tirrell, Bruce W. Westbury, and Yi Zhang, On sequences associated to the invariant theory of rank two simple Lie algebras, arXiv:1911.10288 [math.CO], 2019.
Alin Bostan, Jordan Tirrell, Bruce W. Westbury, and Yi Zhang, On some combinatorial sequences associated to invariant theory, arXiv:2110.13753 [math.CO], 2021.
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.
Mathilde Bouvel, Veronica Guerrini, Andrew Rechnitzer, and Simone Rinaldi, Semi-Baxter and strong-Baxter: two relatives of the Baxter sequence, arXiv:1702.04529 [math.CO], 2017.
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, Houston Journal of Mathematics, Volume 7, No. 2, 1981
S. Burrill, S. Melczer, and 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/0309135 [math.CO], 2003-2004.
Jean Cardinal and Vincent Pilaud, Rectangulotopes, arXiv:2404.17349 [math.CO], 2024. See p. 14.
G. Chatel and V. Pilaud, Cambrian Hopf Algebras, arXiv:1411.3704 [math.CO], 2014-2015. and [DOI]
T. Y. Chow, H. Eriksson, and C. K. Fan, Chess tableaux, Elect. J. Combin., 11 (2) (2005), #A3.
F. R. K. Chung, R. L. Graham, V. E. Hoggatt Jr., and M. Kleiman, The number of Baxter permutations J. Combin. Theory Ser. A 24 (1978), no. 3, 382-394.
J. Cranch, Representing and Enumerating Two-Dimensional Pasting Diagrams, 2014.
CombOS - Combinatorial Object Server, Generate diagonal rectangulations
Colin Defant, Stack-Sorting Preimages of Permutation Classes, arXiv:1809.03123 [math.CO], 2018.
Anand Deopurkar, Eduard Duryev, and Anand Patel, Ramification divisors of general projections, arXiv:1901.01513 [math.AG], 2019.
Tomislav Došlic and Darko Veljan, Logarithmic behavior of some combinatorial sequences, Discrete Math. 308 (2008), no. 11, 2182--2212. MR2404544 (2009j:05019).
S. Dulucq and O. Guibert, Permutations de Baxter, Séminaire Lotharingien de Combinatoire, B33c (1994), 9 pp.
S. Dulucq and O. Guibert, Stack words, standard tableaux and Baxter permutations, Disc. Math. 157 (1996), 91-106.
S. Dulucq and O. Guibert, Baxter permutations, Discrete Math. 180 (1998), no. 1-3, 143--156. MR1603713 (99c:05004).
Hanqian Fang, Candice X. T. Zhang, and James J. Y. Zhao, Analytic properties arising from the Baxter numbers, arXiv:2505.05873 [math.CO], 2025. See pp. 2, 9.
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, An investigation of sequences derived from Hoggatt Sums and Hoggatt Triangles, Application of Fibonacci Numbers, 3 (1990) 77-88. Proceedings of 'The Third Annual Conference on Fibonacci Numbers and Their Applications,' Pisa, Italy, July 25-29, 1988. (Annotated scanned copy)
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 and P. K. Nicholson, Optimal Encodings for Range Top-k, Selection, and Min-Max, arXiv:1411.6581 [cs.DS], 2014-2015.
P. Gawrychowski and 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 Baxter permutations, DMTCS proc. AO, FPSAC 2011 Rykjavik, (2011) 387-398.
S. Giraudo, Algebraic and combinatorial structures on pairs of twin binary trees, arXiv:1204.4776 [math.CO], 2012.
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.
Elizabeth Hartung, Hung Phuc Hoang, Torsten Mütze, and Aaron Williams, Combinatorial generation via permutation languages. I. Fundamentals, arXiv:1906.06069 [cs.DM], 2019.
V. E. Hoggatt, Jr., Letter to N. J. A. Sloane, Apr 1977
Don Knuth, Twintrees, Baxter Permutations, and Floorplans, Christmas Lecture, Stanford 2022 (YouTube video).
Laszlo Kozma and T. Saranurak, Binary search trees and rectangulations, arXiv preprint arXiv:1603.08151 [cs.DS], 2016.
Megan A. Martinez and Carla D. Savage, Patterns in Inversion Sequences II: Inversion Sequences Avoiding Triples of Relations, arXiv:1609.08106 [math.CO], 2016 [Section 2.25].
Arturo Merino and Torsten Mütze, Combinatorial generation via permutation languages. III. Rectangulations, arXiv:2103.09333 [math.CO], 2021.
A. Peder and M. Tombak, Finding the description of structure by counting method: a case study, SOFSEM 2011, LNCS 6543 (2011) 455-466 doi:10.1007/978-3-642-18381-2_38.
Vincent Pilaud, Brick polytopes, lattice quotients, and Hopf algebras, arXiv:1505.07665 [math.CO], 2015.
V. Reiner, D. Stanton, and V. Welker, The Charney-Davis quantity for certain graded posets, Sem. Lothar. Combin. 50 (2003/04), Art. B50c, 13 pp.
Jannik Silvanus, Improved Cardinality Bounds for Rectangle Packing Representations, Doctoral Dissertation, University of Bonn (Rheinische Friedrich Wilhelms Universität, Germany 2019).
N. J. A. Sloane, Three vicious walkers of lengths 1, 2, and 3
Wikipedia, Baxter permutation

Cf. A001183, A001185, A046996, A006002, A007318, A056939, A359363.

Concatenation([1], 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

a001181 0 = 1
a001181 n =
   (sum $ map (\k -> product $ map (a007318 (n+1)) [k-1..k+1]) [1..n])
    `div` (a006002 n)
-- Reinhard Zumkeller, Oct 23 2011

[1] 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

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:
seq(a(n), n=0..24);  # Alois P. Heinz, Jul 29 2022

A001181[n_] := HypergeometricPFQ[{-1-n, -n, 1-n}, {2, 3}, -1] (* Richard L. Ollerton, Sep 13 2006 *)
a[0]=1; 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 *)

{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 */

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

[1]+[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
print([BaxterPermutations(n).cardinality() for n in range(25)])
# Peter Luschny, May 21 2024

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
From Richard L. Ollerton, Sep 13 2006: (Start)
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
a(n) ~ 2^(3*n+5)/(Pi*sqrt(3)*n^4). - Vaclav Kotesovec, Oct 01 2012
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

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

A359363 Triangle read by rows. The coefficients of the Baxter polynomials p(0, x) = 1 and p(n, x) = x*hypergeom([-1 - n, -n, 1 - n], [2, 3], -x) for n >= 1.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 1, 4, 1, 0, 1, 10, 10, 1, 0, 1, 20, 50, 20, 1, 0, 1, 35, 175, 175, 35, 1, 0, 1, 56, 490, 980, 490, 56, 1, 0, 1, 84, 1176, 4116, 4116, 1176, 84, 1, 0, 1, 120, 2520, 14112, 24696, 14112, 2520, 120, 1, 0, 1, 165, 4950, 41580, 116424, 116424, 41580, 4950, 165, 1

Offset: 0

Peter Luschny, Dec 28 2022

This triangle is a member of a family of Pascal-like triangles. Let T(n, k, m) = sf(m)*F(n - 1) / (F(k - 1)*F(n - k)) if k > 0 and otherwise k^n, where F(n) = Product_{j=0..m} (n + j)! and sf(m) are the superfactorials A000178. The case m = 2 gives this triangle, some other cases are given in the crossreferences. See also A342889 for a related representation of generalized binomial coefficients.

			Triangle T(n, k) starts:
[0] 1
[1] 0, 1
[2] 0, 1,   1
[3] 0, 1,   4,    1
[4] 0, 1,  10,   10,     1
[5] 0, 1,  20,   50,    20,     1
[6] 0, 1,  35,  175,   175,    35,     1
[7] 0, 1,  56,  490,   980,   490,    56,    1
[8] 0, 1,  84, 1176,  4116,  4116,  1176,   84,   1
[9] 0, 1, 120, 2520, 14112, 24696, 14112, 2520, 120, 1
.
Let p = (p1, p2,..., pn) denote a permutation of {1, 2,..., n}. The pair (p(i), p(i+1)) is a 'rise' if p(i) < p(i+1). Additionally a conventional rise is counted at the beginning of p.
T(n, k) is the number of Baxter permutations of {1,2,...,n} with k rises. For example for n = 4, [T(n, k) for k = 0..n] = [0, 1, 10, 10, 1]. The permutations, with preceding number of rises, are:
.
1 [4, 3, 2, 1],  3 [2, 3, 4, 1],  2 [3, 4, 2, 1],  3 [2, 3, 1, 4],
2 [3, 2, 4, 1],  3 [2, 1, 3, 4],  2 [3, 2, 1, 4],  3 [1, 3, 4, 2],
2 [2, 4, 3, 1],  3 [1, 3, 2, 4],  2 [4, 2, 3, 1],  3 [3, 4, 1, 2],
2 [2, 1, 4, 3],  3 [3, 1, 2, 4],  2 [4, 2, 1, 3],  3 [1, 2, 4, 3],
2 [1, 4, 3, 2],  3 [1, 4, 2, 3],  2 [4, 1, 3, 2],  3 [4, 1, 2, 3],
2 [4, 3, 1, 2],  4 [1, 2, 3, 4].

Special cases of the general formula: A097805 (m = 0), (0,1)-Pascal triangle; A090181 (m = 1), triangle of Narayana; this triangle (m = 2); A056940 (m = 3), with 1,0,0...; A056941 (m = 4), with 1,0,0...; A142465 (m = 5), with 1,0,0....
Variant: A056939. Diagonals: A000292, A006542, A047819.
Cf. A000178, A001181, A046996, A217800, A342889.

p := (n, x) -> ifelse(n = 0, 1, x*hypergeom([-1-n, -n, 1-n], [2, 3], -x)):
seq(seq(coeff(simplify(p(n, x)), x, k), k = 0..n), n = 0..10);
# Alternative:
T := proc(n, k) local F; F := n -> n!*(n+1)!*(n+2)!;
ifelse(k = 0, k^n, 2*F(n-1)/(F(k-1)*F(n-k))) end:
for n from 0 to 9 do seq(T(n, k), k = 0..n) od;

C=binomial;
T(n, k) = if(n==0 && k==0, 1, ( C(n+1,k-1) * C(n+1,k) * C(n+1,k+1) ) / ( C(n+1,1) * C(n+1,2) ) );
for(n=0,10,for(k=0,n,print1(T(n,k),", "));print());
\\ Joerg Arndt, Jan 04 2024

from functools import cache
from math import factorial
@cache
def A359363Row(n: int) -> list[int]:
    @cache
    def F(n: int): return factorial(n) ** 3 * ((n+1) * (n+1) * (n+2))
    if n == 0: return [1]
    return [0] + [(2*F(n-1))//(F(k-1) * F(n-k)) for k in range(1, n+1)]
for n in range(0, 10): print(A359363Row(n))
# Peter Luschny, Jan 04 2024

def A359363(n):
    if n == 0: return SR(1)
    h = x*hypergeometric([-1 - n, -n, 1 - n], [2, 3], -x)
    return h.series(x, n + 1).polynomial(SR)
for n in range(10): print(A359363(n).list())
def PolyA359363(n, t): return Integer(A359363(n)(x=t).n())
# Peter Luschny, Jan 04 2024

T(n, k) = [x^k] p(n, x).
T(n, k) = 2*F(n-1)/(F(k-1)*F(n-k)) for k > 0 where F(n) = n!*(n+1)!*(n+2)!.
p(n, 1) = A001181(n), i.e. the Baxter numbers are the values of the Baxter polynomials at x = 1.
(-1)^(n + 1)*p(2*n + 1, -1) = A217800(n) .

cp's OEIS Frontend

A001181 Number of Baxter permutations of length n (also called Baxter numbers).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Haskell

Magma

Maple

Mathematica

PARI

Python

Sage

Formula

Extensions

A359363 Triangle read by rows. The coefficients of the Baxter polynomials p(0, x) = 1 and p(n, x) = x*hypergeom([-1 - n, -n, 1 - n], [2, 3], -x) for n >= 1.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

PARI

Python

SageMath

Formula

A001183 Number of nontrivial Baxter permutations of length 2n-1.

Views

Author

Keywords

References

Links

Crossrefs