A001181 -id:A001181 - cp's OEIS frontend

A281784 Number of permutations of size n avoiding the three vincular patterns 2-41-3, 3-14-2 and 3-41-2.

1, 2, 6, 21, 82, 346, 1547, 7236, 35090, 175268, 897273, 4690392, 24961300, 134917123, 739213795, 4099067786, 22973964976, 129998127216, 741951610676, 4267733183951, 24722711348105, 144147076572858, 845460619537567, 4986014094568416, 29553202933497989, 175988793822561947, 1052569034807964425, 6320797287983675428, 38100643422386086309, 230476496238489596293, 1398812189780917895946, 8516159717810715750712, 51999675864641162206960, 318388601290603235387353, 1954555567303560704554767, 12028490623505389875097231, 74197729371621673254309374, 458706129189543207063584184, 2841808950641424998337843123

Offset: 1

Mathilde Bouvel, Mar 01 2017

a(n) is the number of permutations of size n that are both Baxter and twisted Baxter.

a(n) is also the number of excursions in the positive quarter-plane, using n steps, and with step (multi-)set {(-1,0),(0,-1),(1,-1),(1,0),(0,1),(0,0),(0,0)}.

			For n=4, there are a(4)=21 permutations that avoid 2-41-3, 3-14-2 and 3-41-2 (all permutations of size 4 except 2413, 3142 and 3412).

Vaclav Kotesovec, Table of n, a(n) for n = 1..1000
A. Bostan, K. Raschel, B. Salvy, Non D-finite excursions in the quarter plane, J. Comb. Theory A, 121:45-63, 2014.
Mathilde Bouvel, Veronica Guerrini, Andrew Rechnitzer and Simone Rinaldi, Semi-Baxter and strong-Baxter: two relatives of the Baxter sequence. Arxiv preprint, 2017.
Arturo Merino and Torsten Mütze, Combinatorial generation via permutation languages. III. Rectangulations, arXiv:2103.09333 [math.CO], 2021.

Baxter and twisted Baxter permutations are both enumerated by the Baxter numbers A001181.

S:=x*y*z:
s[1]:=1:
for en from 2 to 200 do
x*y/(1-y)*(subs(y=1,S))-x/(1-y)*S+x*z*S+x*y*z/(1-z)*(subs(z=1,S))-x*y*z/(1-z)*S;
S:=normal(%):
s[en]:=subs(x=1,z=1,y=1,S);
od:
# Veronica Guerrini, Mar 01 2017

The generating function for a(n) is A(x;1,1) where A(x;y,z) satisfies A(x;y,z) = x*y*z + (x/(1-y))*(y*A(x;1,z) - A(x;y,z)) + x*z*A(x;y,z) + (x*y*z/(1-z))*(A(x;y,1) - A(x;y,z)).

Consequently, neither A(x;1,1) nor A(x;y,z) are D-finite (see preprint of Bouvel et al.).

A342284 Number of friendly 3-watermelons of length n.

Original entry on oeis.org

1, 0, 2, 6, 24, 110, 550, 2922, 16242, 93520, 553980, 3359384, 20777588, 130696662, 834244830, 5393850898, 35272830054, 233016356788, 1553427829684, 10441803227652, 70715551631992, 482201548554776, 3308810614160224, 22836540660981088, 158458108961055864

Offset: 0

N. J. A. Sloane, Mar 19 2021

nonn

Essam, J.W. and Guttmann, A.J., 1995. Vicious walkers and directed polymer networks in general dimensions. Physical Review E, 52(6), pp. 5849ff. See (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 F_3(x).

Cf. A001181, A342282.

G.f. = 1 - 2*x + G(x), where G(x) = 2*x+2*x^2+6*x^3+24*x^4+110*x^5+550*x^6+... is the g.f. for A342282.

A347678 Triangle read by rows: T(n,k) (1 <= k <= n) = number of n X k Baxter matrices in which all row sums are 1.

Original entry on oeis.org

1, 1, 2, 1, 6, 6, 1, 12, 32, 22, 1, 20, 100, 172, 92, 1, 30, 240, 744, 956, 422, 1, 42, 490, 2364, 5328, 5492, 2074, 1, 56, 896, 6174, 21236, 37618, 32490, 10754, 1, 72, 1512, 14056, 68030, 181140, 264612, 197144, 58202, 1, 90, 2400, 28896, 186462, 690444, 1497544, 1863222, 1222642, 326240

Offset: 1

N. J. A. Sloane, Sep 10 2021

Don Knuth, Baxter matrices, Preprint, Sep 05 2021.
George Spahn, Counting Baxter Matrices, arXiv:2110.09688 [math.CO], 2021.

The main diagonal is A001181.

Cf. A347679.

a(29)-a(55) from Michael S. Branicky, Sep 17 2021

A350265 a(n) = hypergeometric([-n - 1, 1 - n, -n], [1, 3], -1).

Original entry on oeis.org

1, 1, 3, 12, 55, 276, 1477, 8296, 48393, 291010, 1794320, 11297760, 72413640, 471309944, 3108745785, 20746732688, 139899430981, 952127880138, 6533934575018, 45175430719240, 314467004704818, 2202576030828096, 15514620388706488, 109851319423632192, 781531332298053400

Offset: 0

Peter Luschny, Dec 28 2021

nonn

T. Amdeberhan, A rather curious identity on sums over triple binomial terms, MathOverflow 2021.

Cf. A000217, A002378, A277188, A001181 (Baxter permutations).

a := proc(n) option remember; if n < 2 then 1 else ((n + 1)*((7*n^2 + 7*n - 2)*a(n - 1) + 8*(n - 2)*n*a(n - 2)))/(n*(n + 2)*(n + 3)) fi end:
seq(a(n), n = 0..24);

a[n_] := HypergeometricPFQ[{-n - 1, 1 - n, -n}, {1, 3}, -1];
Table[a[n], {n, 0, 24}]

from sympy import hyperexpand
from sympy.functions import hyper
def A350265(n): return hyperexpand(hyper((-n-1,1-n,-n),(1,3),-1)) # Chai Wah Wu, Dec 29 2021

a(n) * A000217(n) = Sum_{k=0..n-1} binomial(n + 1, k) * binomial(n, k) * binomial(n + 1, k + 2).
a(n) * A002378(n) = Sum_{k=0..n-1} binomial(n + 1, k) * binomial(n + 1, k + 1) * binomial(n + 1, k + 2).
For a recurrence see the Maple program.
a(n) ~ 2^(3*n+4) / (Pi*sqrt(3)*n^3). - Vaclav Kotesovec, Apr 27 2024

A368733 a(n) = hypergeom([-1 - n, -n, 1 - n], [2, 3], -3).

Original entry on oeis.org

1, 1, 4, 22, 148, 1132, 9484, 85066, 804556, 7939738, 81128800, 853424464, 9201391456, 101327618056, 1136518296892, 12954283592578, 149770265417692, 1753615603901818, 20766700361401336, 248449277456597908, 3000039734827403608, 36532024054221028576, 448294209318801516064

Offset: 0

Vaclav Kotesovec, Jan 04 2024

nonn

Cf. A001181, A368708.

Table[HypergeometricPFQ[{-1-n, -n, 1-n}, {2, 3}, -3], {n, 0, 30}]
a[0] := 1; a[n_] := 3^n*Sum[(1/3)^k*Binomial[n + 1, k - 1]*Binomial[n + 1, k]*Binomial[n + 1, k + 1]/(Binomial[n + 1, 1]*Binomial[n + 1, 2]), {k, 1, n}]; Table[a[n], {n, 0, 22}] (* Detlef Meya, May 28 2024 *)

from sympy import hyperexpand
from sympy.functions import hyper
def A368733(n): return hyperexpand(hyper((-1-n,-n,1-n),(2,3),-3)) # Chai Wah Wu, Jan 04 2024

a(n) ~ (4 + 3^(4/3) + 3^(5/3))^(n + 5/3) / (3^(11/6) * Pi * n^4).

a(0) = 1, a(n) = 3^n*Sum_{k=1..n} (1/3)^k*binomial(n + 1, k - 1)*binomial(n + 1, k)*binomial(n + 1, k + 1)/(binomial(n + 1, 1)*binomial(n + 1, 2)). - Detlef Meya, May 28 2024

A217216 Dimension of algebraic generators of the algebra "Baxter" of order n.

Original entry on oeis.org

0, 1, 1, 3, 11, 47, 221, 1113, 5903, 32607, 186143, 1092015, 6555515, 40137219, 249984481, 1580468321, 10125395007, 65639436955, 430048061915, 2844592155631, 18979693010495, 127641472658231, 864645413540671, 5896221199266519, 40455246946190079

Offset: 0

N. J. A. Sloane, Oct 03 2012

nonn

G. Chatel and V. Pilaud, Cambrian Hopf Algebras, arXiv:1411.3704 [math.CO], 2014-2015.
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.

Cf. A001181.

nmax = 25;
1-1/(1+Sum[HypergeometricPFQ[{-1-n, 1-n, -n}, {2, 3}, -1] x^n, {n, nmax}]) + O[x]^nmax // CoefficientList[#, x]& (* Jean-François Alcover, Sep 26 2018 *)

baxter(n) = 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)));
lista(m) = {u = t + t*O(t^m); b = 1 + sum(n=1, m, baxter(n)*u^n); gfbc = 1 - 1/b; for (n=0, m, print1(polcoeff(gfbc, n, t), ", "));}
\\ Michel Marcus, Feb 16 2013

Giraudo gives a generating function.

a(n) ~ c * 8^n / n^4, where c = 4.21514033443045415032... - Vaclav Kotesovec, Apr 27 2024

More terms from Michel Marcus, Feb 16 2013

A217217 Dimension of totally primitive elements of the algebra "Baxter" of order n.

Original entry on oeis.org

0, 1, 0, 1, 4, 19, 96, 511, 2832, 16215, 95374, 573837, 3520228, 21961119, 139038824, 891817687, 5787091552, 37946582995, 251173847170, 1676831257693, 11282156358500, 76453813499219, 521508969157826, 3578990500062417, 24700214881378152, 171359711873508367

Offset: 0

N. J. A. Sloane, Oct 03 2012

nonn

S. Giraudo, Algebraic and combinatorial structures on pairs of twin binary trees, Journal of Algebra, Volume 360, 15 June 2012, Pages 115-157.

S. Giraudo, Algebraic and combinatorial structures on Baxter permutations, DMTCS proc. AO, FPSAC 2011 Rykjavik, (2011) 387-398.

Cf. A001181.

baxter(n) = 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)));
lista(m) = {u = t + t*O(t^m); b = 1 + sum(n=1, m, baxter(n)*u^n); gfbt = (b-1)/b^2; for (n=0, m, print1(polcoeff(gfbt, n, t), ", "));}
\\ Michel Marcus, Feb 16 2013

Giraudo gives a generating function.

More terms from Michel Marcus, Feb 16 2013

A347546 Number of involutions of doubly alternating Baxter permutations of length n.

Original entry on oeis.org

1, 1, 1, 1, 2, 2, 3, 5, 8, 12, 16, 32, 44, 84, 105, 231, 292, 636, 768, 1792, 2166, 5080, 6012, 14592, 17234, 42198, 49336, 123088, 143536, 361190, 418971, 1066497, 1234242, 3164870, 3651296, 9436968, 10866726, 28255468, 32469716, 84925632, 97443786, 256131058

Offset: 0

Sook Min, Sep 06 2021

nonn

Marilena Barnabei, Flavio Bonetti, Niccolò Castronuovo, and Matteo Silimbani, Pattern avoiding alternating involutions, arXiv:2206.13877 [math.CO], 2022.
Sook Min, The Enumeration of Involutions of Doubly Alternating Baxter Permutations, Journal of the Chungcheong Mathematical Society, 34(3) (2021), 253-257.

Cf. A001181.

def b(n):
    if (0<=n<=3):
        return 1
    if (n==4):
        return 2
    if (n%2==1):
      t=0
      for k in range(1, ((n+1)//2)):
          t+=b(2*k-2)*b(n-2*k)
      return t
    else:
        s=0
        for j in range(round(n/4), (n//2)):
            s+=b(4*j-n)*b(n-2*j-1)
        return b(n-1)+s
for i in range(30):
    print(str(i)+': '+str(b(i)))

A356197 Number of Baxter 3-permutations of length n.

Original entry on oeis.org

1, 1, 4, 28, 260, 2872, 35620, 479508

Offset: 0

Nicolas Bonichon, Jul 29 2022

Nicolas Bonichon and Pierre-Jean Morel, Baxter d-permutations and other pattern avoiding classes, arXiv:2202.12677 [math.CO], 2022.

Cf. A001181.

A363682 Number of plane bipolar posets (i.e., plane bipolar orientations with no transitive edge) with n edges.

Original entry on oeis.org

1, 1, 1, 2, 5, 12, 32, 93, 279, 872, 2830, 9433, 32223, 112527, 400370, 1448520, 5320023, 19802827, 74612164, 284238390, 1093757436, 4247742956, 16636921148, 65671960544, 261111950308, 1045172796381, 4209807155949, 17055625810984, 69476952146529, 284467866640048

Offset: 1

Éric Fusy, Jun 16 2023

nonn

a(n) is also the number of walks of length n-1 in the quadrant, starting and ending at the origin, with step-set {0,E,S,NW,SE} (where 0 is the stay-step).

Éric Fusy, Erkan Narmanli, and Gilles Schaeffer, On the enumeration of plane bipolar posets and transversal structures, arXiv:2105.06955 [math.CO], 2021-2022.

Cf. A001181, A296419, A117106, A151335.

A:=proc(n,i,j) option remember:
if n=0 and i=0 and j=0 then return 1:
elif n<=0 or j<0 or i<0 then return 0:
else
return A(n-1,i,j)+A(n-1,i-1,j)+A(n-1,i,j+1)+A(n-1,i+1,j-1)+A(n-1,i-1,j+1):
fi:
end proc:
seq(A(n-1,0,0),n=1..20);

cp's OEIS Frontend

A281784 Number of permutations of size n avoiding the three vincular patterns 2-41-3, 3-14-2 and 3-41-2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

A342284 Number of friendly 3-watermelons of length n.

Views

Author

Keywords

References

Crossrefs

Formula

A347678 Triangle read by rows: T(n,k) (1 <= k <= n) = number of n X k Baxter matrices in which all row sums are 1.

Views

Author

Keywords

Links

Crossrefs

Extensions

A350265 a(n) = hypergeometric([-n - 1, 1 - n, -n], [1, 3], -1).

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

A368733 a(n) = hypergeom([-1 - n, -n, 1 - n], [2, 3], -3).

Views

Author

Keywords

Crossrefs

Programs

Mathematica

Python

Formula

A217216 Dimension of algebraic generators of the algebra "Baxter" of order n.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A217217 Dimension of totally primitive elements of the algebra "Baxter" of order n.

Views

Author

Keywords

References

Links

Crossrefs

Programs

PARI

Formula

Extensions

A347546 Number of involutions of doubly alternating Baxter permutations of length n.

Views

Author

Keywords

Links

Crossrefs

Programs

Python

A356197 Number of Baxter 3-permutations of length n.

Views

Author

Keywords