A125187 -id:A125187 - cp's OEIS frontend

A224747 Number of lattice paths from (0,0) to (n,0) that do not go below the x-axis and consist of steps U=(1,1), D=(1,-1) and H=(1,0), where H-steps are only allowed if y=1.

1, 0, 1, 1, 3, 5, 12, 23, 52, 105, 232, 480, 1049, 2199, 4777, 10092, 21845, 46377, 100159, 213328, 460023, 981976, 2115350, 4522529, 9735205, 20836827, 44829766, 96030613, 206526972, 442675064, 951759621, 2040962281, 4387156587, 9411145925, 20226421380

Offset: 0

Alois P. Heinz, Apr 17 2013

nonn

Also the number of non-capturing (cf. A054391) set-partitions of {1..n} without singletons. - Christian Sievers, Oct 29 2024

			a(5) = 5: UHHHD, UDUHD, UUDHD, UHDUD, UHUDD.
a(6) = 12: UHHHHD, UDUHHD, UUDHHD, UHDUHD, UHUDHD, UHHDUD, UDUDUD, UUDDUD, UHHUDD, UDUUDD, UUDUDD, UUUDDD.
G.f. = 1 + x^2 + x^3 + 3*x^4 + 5*x^5 + 12*x^6 + 23*x^7 + 52*x^8 + 105*x^9 + ...

Alois P. Heinz, Table of n, a(n) for n = 0..1000
C. Banderier and M. Wallner, Lattice paths with catastrophes, SLC 77, Strobl - 12.09.2016, H(x).
Cyril Banderier and Michael Wallner, Lattice paths with catastrophes, arXiv:1707.01931 [math.CO], 2017.
Jean-Luc Baril and Sergey Kirgizov, Bijections from Dyck and Motzkin meanders with catastrophes to pattern avoiding Dyck paths, arXiv:2104.01186 [math.CO], 2021.
Jean-Luc Baril, Sergey Kirgizov, and Armen Petrossian, Dyck Paths with catastrophes modulo the positions of a given pattern, Australasian J. Comb. (2022) Vol. 84, No. 2, 398-418.

Cf. A000108 (without H-steps), A001006 (unrestricted H-steps), A057977 (<=1 H-step).
Cf. A000012, A101455, A125187, A001405 (invert transform).
Inverse binomial transform of A054391.

a:= proc(n) option remember; `if`(n<5, [1, 0, 1, 1, 3][n+1],
      a(n-1)+ (6*(n-3)*a(n-2) -3*(n-5)*a(n-3)
      -8*(n-4)*a(n-4) -4*(n-4)*a(n-5))/(n-1))
    end:
seq(a(n), n=0..40);

a[n_] := a[n] = If[n < 5, {1, 0, 1, 1, 3}[[n+1]], a[n-1] + (6*(n-3)*a[n-2] - 3*(n-5)*a[n-3] - 8*(n-4)*a[n-4] - 4*(n-4)*a[n-5])/(n-1)]; Table[a[n], {n, 0, 34}] (* Jean-François Alcover, Jun 20 2013, translated from Maple *)
a[ n_] := SeriesCoefficient[ (2 - 3 x - 2 x^2 + x Sqrt[1 - 4 x^2]) / (2 (1 - x - 2 x^2 - x^3)), {x, 0, n}] (* Michael Somos, Jan 14 2014 *)

{a(n) = if( n<0, 0, polcoeff( (2 - 3*x - 2*x^2 + x * sqrt(1 - 4*x^2 + x * O(x^n)) ) / (2 * (1 - x - 2*x^2 - x^3)), n))} /* Michael Somos, Jan 14 2014 */

a(n) = Sum_{k=0..floor((n-2)/2)} A009766(2*n-3*k-3, k) for n >= 2. - Johannes W. Meijer, Jul 22 2013
a(2*n) = A125187(n) (bisection). - R. J. Mathar, Jul 27 2013
HANKEL transform is A000012. HANKEL transform omitting a(0) is a period 4 sequence [0, -1, 0, 1, ...] = -A101455. - Michael Somos, Jan 14 2014
Given g.f. A(x), then 0 = A(x)^2 * (x^3 + 2*x^2 + x - 1) + A(x) * (-2*x^2 - 3*x + 2) + (2*x - 1). - Michael Somos, Jan 14 2014
0 = a(n)*(a(n+1) +2*a(n+2) +a(n+3) -a(n+4)) +a(n+1)*(2*a(n+1) +5*a(n+2) +a(n+3) -2*a(n+4)) +a(n+2)*(2*a(n+2) -a(n+3) -a(n+4)) +a(n+3)*(-a(n+3) +a(n+4)). - Michael Somos, Jan 14 2014
G.f.: (2 - 3*x - 2*x^2 + x * sqrt(1 - 4*x^2)) / (2 * (1 - x - 2*x^2 - x^3)). - Michael Somos, Jan 14 2014
D-finite with recurrence (-n+1)*a(n) +(n-1)*a(n-1) +6*(n-3)*a(n-2) +3*(-n+5)*a(n-3) +8*(-n+4)*a(n-4) +4*(-n+4)*a(n-5)=0. - R. J. Mathar, Sep 15 2021

A125188 Number of Dumont permutations of the first kind of length 2n avoiding the patterns 2413 and 4132. Also number of Dumont permutations of the first kind of length 2n avoiding the patterns 1423 and 3142.

Original entry on oeis.org

1, 1, 3, 12, 54, 259, 1294, 6655, 34986, 187149, 1015407, 5574829, 30915904, 172933249, 974605751, 5528804444, 31546576802, 180931023589, 1042503934315, 6031773336043, 35030156585236, 204135876541762, 1193291688154639

Offset: 0

Emeric Deutsch, Dec 19 2006

nonn

A. Burstein, Restricted Dumont permutations, arXiv:math/0402378 [math.CO], 2004
A. Burstein, Restricted Dumont permutations, Annals of Combinatorics, 9, 2005, 269-280 (Theorem 3.13).
Matteo Cervetti and Luca Ferrari, Pattern avoidance in the matching pattern poset, arXiv:2009.01024 [math.CO], 2020.
Matteo Cervetti and Luca Ferrari, Enumeration of Some Classes of Pattern Avoiding Matchings, with a Glimpse into the Matching Pattern Poset, Annals of Combinatorics (2022).
Y. Sun and Z. Wang, Consecutive pattern avoidances in non-crossing trees, Graph. Combinat. 26 (2010) 815-832, G_{uud}

Cf. A125187.

C:=(1-sqrt(1-4*x))/2/x: G:=(1+x*C-sqrt(1-x*C-5*x))/2/x/(1+C): Gser:=series(G,x=0,30): seq(coeff(Gser,x,n),n=0..26);

CoefficientList[Series[(-3+Sqrt[2]*Sqrt[1+Sqrt[1-4*x]-10*x] + Sqrt[1-4*x])/(2*(-1+Sqrt[1-4*x]-2*x)), {x, 0, 20}], x] (* Vaclav Kotesovec, Feb 03 2014 *)

G.f.=[1+xC(x)-sqrt(1-xC(x)-5x)]/[2x(1+C(x))], where C(x)=(1-sqrt(1-4x))/(2x) is the Catalan function.
D-finite with recurrence 32*(n-1)*(2*n-1)*(n+1)*a(n) +8*(-148*n^3+461*n^2-367*n+14)*a(n-1) +4*(2197*n^3-13436*n^2+25653*n-14694)*a(n-2) +2*(-16868*n^3+159415*n^2-483427*n+468080)*a(n-3) +(66623*n^3-867526*n^2+3651197*n-4985254)*a(n-4) -20*(2*n-9)*(1027*n^2-13868*n+42561)*a(n-5) -10500*(n-5)*(2*n-9)*(2*n-11)*a(n-6)=0. - R. J. Mathar, Jul 27 2013
a(n) ~ 5^(2*n+3/2) / (9 * 4^n * n^(3/2) * sqrt(3*Pi)). - Vaclav Kotesovec, Feb 03 2014

cp's OEIS Frontend

A224747 Number of lattice paths from (0,0) to (n,0) that do not go below the x-axis and consist of steps U=(1,1), D=(1,-1) and H=(1,0), where H-steps are only allowed if y=1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula