Mireille Bousquet-Mélou - cp's OEIS frontend

A260155 Number of walks of length 2n on the square lattice that start and end at (0,0) and avoid the negative quadrant.

1, 4, 32, 318, 3530, 41944, 522010, 6719018, 88726840, 1195527822, 16373466714, 227280520316, 3190715296368, 45226324937400, 646392346047930, 9305481272839662, 134815491199174476, 1964195875748858812, 28761433275110249932, 423052415434610432816

Offset: 0

Mireille Bousquet-Mélou, Nov 09 2015

			When n=1 the four walks are NS, EW, SN, WE.

Alois P. Heinz, Table of n, a(n) for n = 0..800
M. Bousquet-Mélou, Plane lattice walks avoiding a quadrant, arXiv:1511.02111 [math.CO], 2015.

Cf. A060898 for walks starting from (0,0) but in which the final point is not prescribed.

f[x_, n_] := x Pochhammer[x+1, n-1];
a[n_] := 4 16^n/3^5 (3^4 f[1/2, n] f[1/2, n + 1]/(f[2, n] f[2, n + 1]) + 4 (24n^2 + 60n + 29) f[1/2, n] f[7/6, n]/(f[2, n + 1] f[4/3, n + 1]) - 2 (12n^2 + 30n + 5) f[1/2, n] f[5/6, n]/(f[2, n + 1] f[5/3, n + 1]));
Table[a[n], {n, 0, 19}] (* Jean-François Alcover, Jul 25 2018 *)

a(n) = 4*16^n/ 3^5 * ( 3^4 *f(1/2,n)* f(1/2,n+1)/ (f(2,n) * f(2,n+1)) + 4 *(24*n^2+60*n +29)* f(1/2,n)* f(7/6,n) /(f(2,n+1) *f(4/3, n+1)) -2 *(12*n^2+30*n+5) * f(1/2,n)*f(5/6,n) /(f(2,n+1)*f(5/3,n+1)) ) where f(m,n) is the ascending factorial m*(m+1)*...*(m+n-1) (proved).

A260153 Number of walks of length n on the square lattice (with steps N, E, S, W) that start at (0,0) and avoid the West quadrant {(i,j): i < -|j|}.

Original entry on oeis.org

1, 3, 12, 41, 164, 590, 2360, 8715, 34860, 130776, 523104, 1983212, 7932848, 30303416, 121213664, 465673065, 1862692260, 7187760140, 28751040560, 111338982436, 445355929744, 1729672999418, 6918691997672, 26936111629934, 107744446519736, 420338301077100

Offset: 0

Mireille Bousquet-Mélou, Nov 09 2015

nonn

			For n=1, the three possible walks are N, E, S.

Alois P. Heinz, Table of n, a(n) for n = 0..1000
M. Bousquet-Mélou, Plane lattice walks avoiding a quadrant, arXiv:1511.02111 [math.CO], 2015.

Cf. A060898 for walks avoiding the negative quadrant rather than the West one, A260154.

b:= proc(n,i,j) option remember;
      if i < -abs(j) then 0
    elif n=0 then 1
    else b(n-1,i-1,j)+
         b(n-1,i+1,j)+
         b(n-1,i,j-1)+
         b(n-1,i,j+1)
      fi
    end:
a:= n-> b(n,0,0);
seq(a(n), n=0..30);  # Alois P. Heinz, Nov 09 2015
# second Maple program:
a:= proc(n) option remember; `if`(n<4, [1, 3, 12, 41][n+1],
      ((4*(2*n-5))*(12*n^4-16*n^3-6*n^2+10*n+3) *a(n-1)
      +(16*(2*n-5))*(2*n+1)*(6*n^4-24*n^3+28*n^2-8*n-3) *a(n-2)
      -(64*(2*n+1))*(12*n^4-80*n^3+186*n^2-178*n+63) *a(n-3)
      -(256*(n-1))*(2*n+1)*(2*n-1)*(3*n-7)*(n-3)^2 *a(n-4))/
      ((2*n-3)*(2*n-5)*(n-1)*(3*n+1)*(n+1)^2))
    end:
seq(a(n), n=0..30);  # Alois P. Heinz, Nov 09 2015

b[n_, i_, j_] := b[n, i, j] = Which[i < -Abs[j], 0, n == 0, 1, True, b[n-1, i-1, j] + b[n-1, i+1, j] + b[n-1, i, j-1] + b[n-1, i, j+1]]; a[n_] := b[n, 0, 0]; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Feb 01 2016, after Alois P. Heinz *)
With[{n = 10}, CoefficientList[Series[
-1/(4*t) + (1+4*t)*((sc+Sqrt[1+sc^2])/Sqrt[3-48*t^2] - k/(2*Pi))/(3*t)
  /. sc -> Pi*Sqrt[3]*Normal[Sum[(-1)^p/(1 + q^(-2*p) + q^(2*p)), {p,-n,n}]  + O[q]^(2*n)]/(2*k*Sqrt[1-16*t^2])
  /. q -> EllipticNomeQ[16*t^2] /. k -> EllipticK[16*t^2],
{t,0,4*n}], t]] (* Timothy Budd, Oct 23 2016 *)

G.f.: -1/(4*t) + (1+4*t) * ((sc(K(4*t)/3;4*t)+nc(K(4*t)/3;4*t))/sqrt(3-48*t^2) - K(4*t)/(2*Pi)) / (3*t), where K(4*t) is the complete elliptic integral of modulus 4*t and sc(.;4*t), nc(.;4*t) are Jacobi elliptic functions again with modulus 4*t. - Timothy Budd, Oct 23 2016

a(n) ~ Gamma(1/3) * 2^(2*n+2) / (3*Pi*n^(1/3)). - Vaclav Kotesovec, Oct 06 2019

A260154 Number of square lattice walks of length 2n starting and ending at (0,0) and avoiding the West quadrant {(i,j): i < -|j|}.

Original entry on oeis.org

1, 3, 22, 209, 2256, 26296, 322696, 4109131, 53802868, 719967204, 9804170810, 135438150718, 1893565055948, 26744778067560, 381061505993160, 5470780479977505, 79066952734823832, 1149467155656304276, 16798622641884084940, 246654934301978877376

Offset: 0

Mireille Bousquet-Mélou, Nov 09 2015

			When n=1, only the walks NS, EW, SN contribute.

Alois P. Heinz, Table of n, a(n) for n = 0..830
M. Bousquet-Mélou, Plane lattice walks avoiding a quadrant, arXiv:1511.02111 [math.CO], 2015.

Cf. A260153.

a:= proc(n) option remember; `if`(n<3, [1, 3, 22][n+1],
     (4*n*(n-1)*(4*n-1)*(54*n^3-45*n^2-49*n-10)*(2*n-1)*
      (4*n-7)*a(n-1) -(16*(n-1))*(4*n-5)*(2*n-1)*(2*n-3)*
      (4*n+1)*(108*n^3-396*n^2+361*n+5)*a(n-2) +(64*(6*n-11))*
      (4*n-1)*(6*n-13)*(2*n-1)*(2*n-3)*(4*n+1)*(-5+2*n)^2*a(n-3))
      /((3*n+2)*(4*n-5)*(3*n+1)*(4*n-7)*n*(n-1)*(n+1)^2))
    end:
seq(a(n), n=0..25);  # Alois P. Heinz, Nov 10 2015

a[n_] := a[n] = If[n<3, {1, 3, 22}[[n+1]], (4(54n^3 - 45n^2 - 49n - 10)(4n - 7)(n-1)(2n - 1)(4n - 1) n a[n-1] - (16(n-1)(4n - 5)(2n - 1)(2n - 3)(4n + 1)(108n^3 - 396n^2 + 361n + 5) a[n-2]) + (6n - 13)(64(6n - 11))(2n - 3) (2n - 1)(4n - 1)(4n + 1)(2n - 5)^2 a[n-3])/((3n + 2)(4n - 5)(3n + 1)(4n - 7) n(n-1)(n+1)^2)]; Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Dec 04 2016 after Alois P. Heinz *)

a(2n) = 16^n/9 * ( 3* (1/2)_n^2/ (2)_n^2 + 8 *(1/2)_n* (7/6)_n/ (2)_n/ (4/3)_n - 2 *(1/2)_n*(5/6)_n/ (2)_n/ (5/3)_n), where (a)_n is the ascending factorial (proved).
D-finite with recurrence n*(n-1)*(3*n+2)*(4*n-5)*(3*n+1)*(4*n-7)*(n+1)^2*a(n) -4*n*(n-1)*(4*n-1)*(2*n-1)*(4*n-7)*(54*n^3-45*n^2-49*n-10)*a(n-1) +16*(n-1)*(4*n-5)*(2*n-1)*(2*n-3)*(4*n+1)*(108*n^3-396*n^2+361*n+5)*a(n-2) -64*(6*n-11)*(4*n-1)*(6*n-13)*(2*n-1)*(2*n-3)*(4*n+1)*(-5+2*n)^2*a(n-3)=0. Alois P. Heinz, Nov 10 2015
D-finite with recurrence n*(n-1)*(3*n+2)*(3*n+1)*(n+1)^2*a(n) -4*n*(n-1)*(180*n^4-360*n^3+287*n^2-71*n+2)*a(n-1) +16*(n-1)*(1440*n^5-10080*n^4+29024*n^3-42768*n^2+31867*n-9465)*a(n-2) -64*(2*n-5)*(2880*n^5-30240*n^4+128608*n^3-277008*n^2+301706*n-132501)*a(n-3) +2048*(2*n-5)*(2*n-7)*(360*n^4-4320*n^3+19474*n^2-39156*n+29691)*a(n-4) -16384*(6*n-23)*(6*n-25)*(2*n-5)*(2*n-7)*(2*n-9)^2*a(n-5)=0. - R. J. Mathar, Apr 11 2022

A214358 Number of (2-14-3, 3-41-2)-avoiding permutations of size n.

Original entry on oeis.org

1, 1, 2, 6, 22, 88, 374, 1668, 7744, 37182, 183666, 929480, 4803018, 25274088, 135132886, 732779504, 4023875702, 22346542912, 125368768090, 709852110576, 4053103780006, 23320440656376, 135126739754922, 788061492048436, 4623591001082002, 27277772831911348

Offset: 0

Mireille Bousquet-Mélou, Jul 13 2012

a(n) is also the number of permutations obtained by retaining only the even entries in a complete Baxter permutation of length 2n+1.

			For n=4, the two permutations not in this class are 2143 and 3412.

W. M. Boyce, Generation of a class of permutations associated with commuting functions, Math. Algorithms, 2 (1967), 19-26.

Alois P. Heinz, Table of n, a(n) for n = 0..400
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, Electronic Journal of Combinatorics, 20:2 (2013), Paper P35; also arXiv preprint arXiv:1011.1889 [math.CO], 2010-2012.
W. M. Boyce, Baxter Permutations and Functional Composition, Houston Journal of Mathematics, Volume 7, No. 2, 1981
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.
CombOS - Combinatorial Object Server, Generate block-aligned rectangulations
Elizabeth Hartung, Hung Phuc Hoang, Torsten Mütze, Aaron Williams, Combinatorial generation via permutation languages. I. Fundamentals, arXiv:1906.06069 [cs.DM], 2019.
Arturo Merino, Torsten Mütze, Combinatorial generation via permutation languages. III. Rectangulations, arXiv:2103.09333 [math.CO], 2021.
Jannik Silvanus, Improved Cardinality Bounds for Rectangle Packing Representations, Doctoral Dissertation, University of Bonn (Rheinische Friedrich Wilhelms Universität, Germany 2019).

Cf. A001181.

a:= proc(n) option remember;
      `if`(n<6, [1, 1, 2, 6, 22, 88][n+1], ((8*n^3+240-8*n-48*n^2)*a(n-6)+
      (80*n-576-32*n^3+144*n^2)*a(n-5)+ (462+41*n^3-158*n^2-129*n)*a(n-4)+
      (-11*n^3-138+104*n^2+85*n)*a(n-3)+ (-14*n^3-80*n^2-92*n-30)*a(n-2)+
      (9*n^3+46*n^2+81*n+48)*a(n-1)) / ((n+4)*(n+3)*(n+1)))
    end:
seq(a(n), n=0..30);  # Alois P. Heinz, Jul 13 2012

a[n_] := a[n] = If[n<6, {1, 1, 2, 6, 22, 88}[[n+1]], ((8*n^3 + 240 - 8*n - 48*n^2)* a[n-6] + (80*n - 576 - 32*n^3 + 144*n^2)*a[n-5] + (462 + 41*n^3 - 158*n^2 - 129*n) *a[n-4] + (-11*n^3 - 138 + 104*n^2 + 85*n)*a[n-3] + (-14*n^3 - 80*n^2 - 92*n - 30 )*a[n-2] + (9*n^3 + 46*n^2 + 81*n + 48)*a[n-1]) / ((n+4)*(n+3)*(n+1))]; Table[ a[n], {n, 0, 30}] (* Jean-François Alcover, Mar 30 2015, after Alois P. Heinz *)

The coefficients are P-recursive:
a(0) = 1, a(1) = 1, a(2) = 2, a(3) = 6, a(4) = 22, a(5) = 88 and
(-192-280*k-96*k^2-8*k^3)*a(k) +(1824+32*k^3+432*k^2+1648*k)*a(k+1)+ (-2856-41*k^3-580*k^2-2403*k)*a(k+2) +(-1740+11*k^3+94*k^2-145*k)*a(k+3)+ (6486+14*k^3+332*k^2+2564*k)*a(k+4) +(-4134-9*k^3-208*k^2-1605*k)*a(k+5)+(630+k^3+26*k^2+223*k)*a(k+6) = 0.
Equivalently, the GF is D-finite with recurrence:
12*(t-1)*(2*t-1)^3 +(104*t-338*t^2+512*t^3 -294*t^4-110*t^5 +192*t^6-48*t^7-12) * A(t) -2*t*(t-1)*(40*t^6-128*t^5+89*t^4+53*t^3-88*t^2+35*t-4) * (d/dt)A(t) -t^2*(2*t-1)*(8*t^2-8*t+1) * (t^2-t-1)*(t-1)^2 * (d^2/dt^2)A(t) = 0.
a(n) ~ 512*(3*sqrt(2)-4) * (4+2*sqrt(2))^n/(Pi*sqrt(3)*n^4). - Vaclav Kotesovec, Aug 15 2013

A108304 Number of set partitions of {1, ..., n} that avoid 3-crossings.

Original entry on oeis.org

1, 1, 2, 5, 15, 52, 202, 859, 3930, 19095, 97566, 520257, 2877834, 16434105, 96505490, 580864901, 3573876308, 22426075431, 143242527870, 929759705415, 6123822269373, 40877248201308, 276229252359846, 1887840181793185, 13037523684646810, 90913254352507057

Offset: 0

Mireille Bousquet-Mélou, Jun 29 2005

There is also a sum-formula for a(n). See Bousquet-Mélou and Xin.

Also partitions avoiding a certain pattern (see J. Bloom and S. Elizalde). - N. J. A. Sloane, Jan 02 2013

			There are 203 partitions of 6 elements, but a(6)=202 because the partition (1,4)(2,5)(3,6) has a 3-crossing.
G.f. = 1 + x + 2*x^2 + 5*x^3 + 15*x^4 + 52*x^5 + 202*x^6 + 859*x^7 + ...

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Jonathan Bloom and Sergi Elizalde, Pattern avoidance in matchings and partitions, arXiv preprint arXiv:1211.3442 [math.CO], 2012.
Alin Bostan, Jordan Tirrell, Bruce W. Westbury, 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.
M. Bousquet-Mélou and G. Xin, On partitions avoiding 3-crossings, arXiv:math/0506551 [math.CO], 2005-2006.
Sophie Burrill, Sergi Elizalde, Marni Mishna and Lily Yen, A generating tree approach to k-nonnesting partitions and permutations, arXiv preprint arXiv:1108.5615 [math.CO], 2011.
Wei Chen, Enumeration of Set Partitions Refined by Crossing and Nesting Numbers, MS Thesis, Department of Mathematics. Simon Fraser University, Fall 2014.
W. Chen, E. Deng, R. Du, R. Stanley, and C. Yan, Crossings and nestings of matchings and partitions, arXiv:math/0501230 [math.CO], 2005.
Andrew R. Conway, Miles Conway, Andrew Elvey Price and Anthony J. Guttmann, Pattern-avoiding ascent sequences of length 3, arXiv:2111.01279 [math.CO], Nov 01 2021.
P. Duncan and Einar Steingrimsson, Pattern avoidance in ascent sequences, arXiv preprint arXiv:1109.3641 [math.CO], 2011.
Juan B. Gil, Jordan O. Tirrell, A simple bijection for classical and enhanced k-noncrossing partitions, arXiv:1806.09065 [math.CO], 2018.
Zhicong Lin, Restricted inversion sequences and enhanced 3-noncrossing partitions, arXiv:1706.07213 [math.CO], 2017.
Zhicong Lin, Sherry H. F. Yan, Vincular patterns in inversion sequences, Applied Mathematics and Computation (2020), Vol. 364, 124672.
T. Mansour and M. Shattuck, Some enumerative results related to ascent sequences, arXiv preprint arXiv:1207.3755 [math.CO], 2012. - _N. J. A. Sloane_, Dec 22 2012
Marni Mishna and Lily Yen, Set partitions with no k-nesting, arXiv preprint arXiv:1106.5036 [math.CO], 2011.

a[0] = a[1] = 1; a[n_] := a[n] = (2*(5*n^2 + 12*n - 2)*a[n-1] + 9*(-n^2 + n + 2)*a[n-2])/((n+4)*(n+5)); Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Mar 30 2015 *)

v = vector(66,n,n);
for (n=1, #v-2, v[n+2] = ((10*n^2+64*n+84)*v[n+1]-(9*n^2+27*n)*v[n]) / (n^2+13*n+42) );
vector(#v+1,n, if(n==1,1,v[n-1])) \\ Joerg Arndt, Sep 01 2012

Recurrence: (9*n^2+27*n) * a(n) + (-10*n^2-64*n-84) * a(n+1) + (n^2+13*n+42) * a(n+2) = 0.
a(n) = (-18*(n+1)*(4*n^5+73*n^4+530*n^3+1928*n^2+3654*n+2916)*A002893(n)+(8*n^6+17156*n^2+6084*n^3+17496+27612*n+1358*n^4+162*n^5) *A002893(n+1))/ (3*n*(n+2)^2*(n+3)^2*(n+4)^2*(n+5)). - Mark van Hoeij, Nov 05 2011
G.f.: (1+7*x-20*x^2+30*x^3-18*x^4-(3*x+1)^2*(x-1)^2*hypergeom([-2/3, -1/3],[2],27*x*(x-1)^2/(3*x+1)^3))/(6*x^4). - Mark van Hoeij, Nov 05 2011
a(n) ~ 5 * sqrt(3) * 3^(2*n+9) / (32*Pi*n^7), Bousquet-Mélou and Xin, 2006. - Vaclav Kotesovec, Aug 23 2014

More terms added by Joerg Arndt, Sep 01 2012

A108307 Number of set partitions of {1, ..., n} that avoid enhanced 3-crossings (or enhanced 3-nestings).

Original entry on oeis.org

1, 1, 2, 5, 15, 51, 191, 772, 3320, 15032, 71084, 348889, 1768483, 9220655, 49286863, 269346822, 1501400222, 8519796094, 49133373040, 287544553912, 1705548000296, 10241669069576, 62201517142632, 381749896129920, 2365758616886432, 14793705539872672

Offset: 0

Mireille Bousquet-Mélou, Jun 29 2005

Also the number of 2-regular 3-noncrossing partitions. There is a bijection from 2-regular 3-noncrossing partitions of n to enhanced partition of n-1. - Jing Qin (qj(AT)cfc.nankai.edu.cn), Oct 30 2007
It appears that this is the number of sequences of length n, starting with a(1) = 1 and 1 <= a(2) <= 2, with 1 <= a(n) <= max(a(n-1),a(n-2)) + 1 for n > 2. - Franklin T. Adams-Watters, May 27 2008
From Eric M. Schmidt, Jul 17 2017: (Start)
Conjecturally, the number of sequences (e(1), ..., e(n)), 0 <= e(i) < i, such that there is no triple i < j < k with e(j) <= e(k) and e(i) >= e(k). [Martinez and Savage, 2.16]
Conjecturally, the number of sequences (e(1), ..., e(n)), 0 <= e(i) < i, such that there is no triple i < j < k with e(i) >= e(j) >= e(k). [Martinez and Savage, 2.16]
(End)
The second of the above-mentioned conjectures is proved in Zhicong Lin's paper. - Eric M. Schmidt, Nov 25 2017

			There are 52 partitions of 5 elements, but a(5)=51 because the partition (1,5)(2,4)(3) has an enhanced 3-nesting.

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Nicholas R. Beaton, Mathilde Bouvel, Veronica Guerrini and Simone Rinaldi, Enumerating five families of pattern-avoiding inversion sequences; and introducing the powered Catalan numbers, arXiv:1808.04114 [math.CO], 2018.
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.
M. Bousquet-Mélou and G. Xin, On partitions avoiding 3-crossings, arXiv:math/0506551 [math.CO], 2005-2006.
Sophie Burrill, Sergi Elizalde, Marni Mishna and Lily Yen, A generating tree approach to k-nonnesting partitions and permutations, arXiv preprint arXiv:1108.5615 [math.CO], 2011.
W. Chen, E. Deng, R. Du, R. Stanley, and C. Yan, Crossings and nestings of matchings and partitions, arXiv:math/0501230 [math.CO], 2005.
Emma Y. Jin, Jing Qin and Christian M. Reidys, On 2-regular k-noncrossing partitions, arXiv:0710.5014 [math.CO], 2007.
Juan B. Gil and Jordan O. Tirrell, A simple bijection for classical and enhanced k-noncrossing partitions, arXiv:1806.09065 [math.CO], 2018.
Zhicong Lin, Restricted inversion sequences and enhanced 3-noncrossing partitions, arXiv:1706.07213 [math.CO], 2017.
Megan A. Martinez and Carla D. Savage, Patterns in Inversion Sequences II: Inversion Sequences Avoiding Triples of Relations, arXiv:1609.08106 [math.CO], 2016.
Sherry H. F. Yan, Ascent sequences and 3-nonnesting set partitions, Eur. J. Comb. 39, 80-94 (2014), remark 3.6.

Cf. A124303, A073525, A007317.

Cf. A000110, A000108.

a:= proc(n) option remember; if n<=1 then 1 elif n=2 then 2 else (8*(n+1) *(n-1) *a(n-2)+ (7*(n-2)^2 +53*(n-2) +88) *a(n-1))/(n+6)/(n+5) fi end: seq(a(n), n=0..20);  # Alois P. Heinz, Sep 05 2008

a[n_] := a[n] = If[n <= 1, 1, If[n==2, 2, (8*(n+1)*(n-1)*a[n-2]+(7*(n-2)^2+53*(n-2)+88)*a[n-1])/(n+6)/(n+5)]]; Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Mar 30 2015, after Alois P. Heinz *)

D-finite with recurrence: 8*(n+3)*(n+1)*a(n)+(7*n^2+53*n+88)*a(n+1)-(n+8)*(n+7)*a(n+2)=0. - Jing Qin (qj(AT)cfc.nankai.edu.cn), Oct 26 2007
G.f.: -(6*x^4-15*x^3-7*x^2-11*x-1)/(6*x^5)+(224*x^3-60*x^2+45*x+5) * hypergeom([1/3, 2/3],[2],27*x^2/(1-2*x)^3) / (30*x^5*(2*x-1))+(32*x^2+64*x+5) * hypergeom([2/3, 4/3],[3],27*x^2/(1-2*x)^3)/(5*x^3*(2*x-1)^2). - Mark van Hoeij, Oct 24 2011
a(n) ~ 5*sqrt(3)*2^(3*n+16)/(27*Pi*n^7). - Vaclav Kotesovec, Aug 16 2013
G.f.: (-6*x^4+15*x^3+7*x^2+11*x+1)/(6*x^5)-(1-8*x)^(4/3)*(1+x)^(2/3)*hypergeom([-2/3, 7/3],[2],-27*x/((1+x)*(-1+8*x)^2))/(6*x^5). - Mark van Hoeij, Jul 26 2021

Edited by N. J. A. Sloane at the suggestion of Franklin T. Adams-Watters, Apr 27 2008

A108305 Number of set partitions of {1, ..., n} that avoid 4-crossings.

Original entry on oeis.org

1, 1, 2, 5, 15, 52, 203, 877, 4139, 21119, 115495, 671969, 4132936, 26723063, 180775027, 1274056792, 9320514343, 70548979894, 550945607475, 4427978077331, 36544023687590, 309088822019071

Offset: 0

Mireille Bousquet-Mélou, Jun 29 2005

			There are 4140 partitions of 8 elements, but a(8) = 4139 because the partition (1,5)(2,6)(3,7)(4,8) has a 4-crossing.

M. Bousquet-Mélou and G. Xin, On partitions avoiding 3-crossings, arXiv:math/0506551 [math.CO], 2005-2006.
Sophie Burrill, Sergi Elizalde, Marni Mishna and Lily Yen, A generating tree approach to k-nonnesting partitions and permutations, arXiv preprint arXiv:1108.5615 [math.CO], 2011.
W. Chen, E. Deng, R. Du, R. Stanley, and C. Yan, Crossings and nestings of matchings and partitions, arXiv:math/0501230 [math.CO], 2005.
Juan B. Gil and Jordan O. Tirrell, A simple bijection for classical and enhanced k-noncrossing partitions, arXiv:1806.09065 [math.CO], 2018. Also Discrete Mathematics (2019) Article 111705. doi:10.1016/j.disc.2019.111705
M. Mishna and L. Yen, Set partitions with no k-nesting, arXiv:1106.5036 [math.CO], 2011-2012.

Cf. A108304 (k = 3), (this: k = 4), A192126 (k = 5), A192127 (k = 6), A192128 (k = 7).

Cf. A192855.

One more value from Burrill et al (2011). - R. J. Mathar, May 25 2025

A059713 Number of multi-directed animals on the square lattice.

Original entry on oeis.org

1, 2, 6, 19, 63, 214, 738, 2571, 9020, 31806, 112572, 399548, 1421145, 5063254, 18062902, 64505148, 230547424, 824547052, 2950565215, 10562978104

Offset: 1

Mireille Bousquet-Mélou, Feb 08 2001

nonn

This class of animals is in bijection with a simple class of heaps of dimers. It generalizes directed animals.

M. Bousquet-Mélou and A. Rechnitzer, Lattice animals and heaps of dimers, Discrete Math. 258 (2002), no. 1-3, 235-274.

M. Bousquet-Mélou and A. Rechnitzer, Lattice animals and heaps of dimers

Directed animals: A005773.

The generating function is known in closed form. Closed, but big. It is proved to be non-D-finite.

A059715 Number of multi-directed animals on the triangular lattice.

Original entry on oeis.org

1, 3, 11, 44, 184, 790, 3450, 15242, 67895, 304267, 1369761, 6188002, 28031111, 127253141, 578694237, 2635356807, 12015117401, 54831125131, 250418753498, 1144434017309

Offset: 1

Mireille Bousquet-Mélou, Feb 08 2001

Counts certain animals that generalize directed animals. They are also equinumerous with a class of n-ominoes studied by Klarner in 1967.

M. Bousquet-Mélou and A. Rechnitzer, Lattice animals and heaps of dimers
M. Bousquet-Mélou and A. Rechnitzer, Lattice animals and heaps of dimers, Discrete Math. 258 (2002), no. 1-3, 235-274.
J.-P. Bultel and S. Giraudo, Combinatorial Hopf algebras from PROs, arXiv preprint arXiv:1406.6903 [math.CO], 2014.
D. A. Klarner, Cell growth problems, Canad. J. Math. 19 (1967) 851-863.

Cf. A000108, A005773.

terms = 12;
c[g_, t_] := c[g, t] = Sum[c[g, n, t], {n, 0, 2 terms}];
c[g_, n_, t_] := c[g, n, t] = P[g, n, t] - Sum[c[g, k, t] P[g, n-k-1, t], {k, 0, n-1}];
P[g_, n_, t_] := 1/F[g, n, t];
F[g_, n_, t_] := F[g, n, t] = If[n<=g, 1, F[g, n-1, t] - t F[g, n-g-1, t]];
Rest[CoefficientList[1-1/c[1, t] + O[t]^(terms+1), t]][[1 ;; terms]] (* Jean-François Alcover, Jul 25 2018 *)

The generating function is known in closed form. It is big and non-D-finite.
Bultel-Giraudo (2014), Prop. 3.2, give a g.f. - N. J. A. Sloane, Sep 21 2014
Conjecture: a(n) = Sum_{j=0..n-1} R(n-1, j) for n > 0 where R(n, j) = Sum_{p=0..n - j - 1} binomial(j + p + 2, p + 1)*R(n - j - 1, p) for 0 <= j < n with R(n, n) = 1. - Mikhail Kurkov, Aug 09 2023
a(n) ~ c * d^n, where d = 4.5878943629412631496341355193804435266001072071... and  c = 0.0653089423402623226212483954648487116904937... - Vaclav Kotesovec, Aug 13 2023

A059712 Number of stacked directed animals on the square lattice.

Original entry on oeis.org

1, 2, 6, 19, 63, 213, 729, 2513, 8703, 30232, 105236, 366849, 1280131, 4470354, 15619386, 54595869, 190891131, 667590414, 2335121082, 8168950665, 28580354769, 100000811433, 349918126509, 1224476796543, 4285005630969

Offset: 1

Mireille Bousquet-Mélou, Feb 08 2001

nonn

The generating function is simply derived from the generating function for directed animals. A triangular lattice version exists.

			x + 2*x^2 + 6*x^3 + 19*x^4 + 63*x^5 + 213*x^6 + 729*x^7 + ...

M. Bousquet-Mélou and A. Rechnitzer, Lattice animals and heaps of dimers
M. Bousquet-Mélou and A. Rechnitzer, Lattice animals and heaps of dimers, Discrete Math. 258 (2002), no. 1-3, 235-274.
Florian Schager and Michael Wallner, A Bijection between Stacked Directed Polyominoes and Motzkin Paths with Alternative Catastrophes, arXiv:2406.16417 [math.CO], 2024. See p. 5.

Directed animals: A005773.

Cf. A001519, A059714.

gf := ((1-2*x)*(1-3*x)-(1-4*x)*sqrt((1-3*x)*(1+x)))/(2*x*(2-7*x)): s := series(gf, x, 50): for i from 1 to 100 do printf(`%d,`,coeff(s,x,i)) od:

CoefficientList[ ((1-2*x)*(1-3*x)-(1-4*x)*Sqrt[(1-3*x)*(1+x)])/(2*x*(2-7*x)) + O[x]^30, x] // Rest (* Jean-François Alcover, Jun 19 2015 *)

{a(n) = local(A); if( n<1, 0, A = O(x); for( k=1, ceil(n/2), A = 1/( 1/x - 2 - (2 - 7*x) / (1 - 3*x) * A)); polcoeff(A, n))} /* Michael Somos, Apr 17 2012 */

G.f.: ((1-2x)(1-3x)-(1-4x)sqrt((1-3x)(1+x)))/(2x(2-7x)).
G.f. A(x) satisfies 0 = f(x, A(x)) where f(x ,y) = (7*x^2 - 2*x) * y^2 + (6*x^2 - 5*x + 1) * y + (3*x^2 - x). - Michael Somos, Apr 17 2012
0 = (105*n^2 + 861*n) * a(n) + (40*n^2 + 433*n + 672) * a(n+1) - (55*n^2 + 586*n + 1200) * a(n+2) + (10*n^2 + 112*n + 288) * a(n+3). - Michael Somos, Apr 17 2012
BINOMIAL transform is A059714. HANKEL transform is A001519(n+1). - Michael Somos, Apr 17 2012

More terms from James Sellers, Feb 09 2001

cp's OEIS Frontend

User: Mireille Bousquet-Mélou

A260155 Number of walks of length 2n on the square lattice that start and end at (0,0) and avoid the negative quadrant.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A260153 Number of walks of length n on the square lattice (with steps N, E, S, W) that start at (0,0) and avoid the West quadrant {(i,j): i < -|j|}.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A260154 Number of square lattice walks of length 2n starting and ending at (0,0) and avoiding the West quadrant {(i,j): i < -|j|}.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A214358 Number of (2-14-3, 3-41-2)-avoiding permutations of size n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A108304 Number of set partitions of {1, ..., n} that avoid 3-crossings.

Views

Author

Keywords

Comments

Examples

Links

Programs

Mathematica

PARI

Formula

Extensions

A108307 Number of set partitions of {1, ..., n} that avoid enhanced 3-crossings (or enhanced 3-nestings).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A108305 Number of set partitions of {1, ..., n} that avoid 4-crossings.

Views

Author

Keywords

Examples

Links

Crossrefs

Extensions