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.

%I A224747 #73 Jun 26 2025 18:30:03
%S A224747 1,0,1,1,3,5,12,23,52,105,232,480,1049,2199,4777,10092,21845,46377,
%T A224747 100159,213328,460023,981976,2115350,4522529,9735205,20836827,
%U A224747 44829766,96030613,206526972,442675064,951759621,2040962281,4387156587,9411145925,20226421380
%N 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.
%C A224747 Also the number of non-capturing (cf. A054391) set-partitions of {1..n} without singletons. - _Christian Sievers_, Oct 29 2024
%H A224747 Alois P. Heinz, <a href="/A224747/b224747.txt">Table of n, a(n) for n = 0..1000</a>
%H A224747 C. Banderier and M. Wallner, <a href="http://www.emis.de/journals/SLC/wpapers/s77vortrag/wallner.pdf">Lattice paths with catastrophes</a>, SLC 77, Strobl - 12.09.2016, H(x).
%H A224747 Cyril Banderier and Michael Wallner, <a href="https://arxiv.org/abs/1707.01931">Lattice paths with catastrophes</a>, arXiv:1707.01931 [math.CO], 2017.
%H A224747 Jean-Luc Baril and Sergey Kirgizov, <a href="https://arxiv.org/abs/2104.01186">Bijections from Dyck and Motzkin meanders with catastrophes to pattern avoiding Dyck paths</a>, arXiv:2104.01186 [math.CO], 2021.
%H A224747 Jean-Luc Baril, Sergey Kirgizov, and Armen Petrossian, <a href="https://ajc.maths.uq.edu.au/pdf/84/ajc_v84_p398.pdf">Dyck Paths with catastrophes modulo the positions of a given pattern</a>, Australasian J. Comb. (2022) Vol. 84, No. 2, 398-418.
%F A224747 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
%F A224747 a(2*n) = A125187(n) (bisection). - _R. J. Mathar_, Jul 27 2013
%F A224747 HANKEL transform is A000012. HANKEL transform omitting a(0) is a period 4 sequence [0, -1, 0, 1, ...] = -A101455. - _Michael Somos_, Jan 14 2014
%F A224747 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
%F A224747 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
%F A224747 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
%F A224747 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
%e A224747 a(5) = 5: UHHHD, UDUHD, UUDHD, UHDUD, UHUDD.
%e A224747 a(6) = 12: UHHHHD, UDUHHD, UUDHHD, UHDUHD, UHUDHD, UHHDUD, UDUDUD, UUDDUD, UHHUDD, UDUUDD, UUDUDD, UUUDDD.
%e A224747 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 + ...
%p A224747 a:= proc(n) option remember; `if`(n<5, [1, 0, 1, 1, 3][n+1],
%p A224747       a(n-1)+ (6*(n-3)*a(n-2) -3*(n-5)*a(n-3)
%p A224747       -8*(n-4)*a(n-4) -4*(n-4)*a(n-5))/(n-1))
%p A224747     end:
%p A224747 seq(a(n), n=0..40);
%t A224747 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 *)
%t A224747 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 *)
%o A224747 (PARI) {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 */
%Y A224747 Cf. A000108 (without H-steps), A001006 (unrestricted H-steps), A057977 (<=1 H-step).
%Y A224747 Cf. A000012, A101455, A125187, A001405 (invert transform).
%Y A224747 Inverse binomial transform of A054391.
%K A224747 nonn
%O A224747 0,5
%A A224747 _Alois P. Heinz_, Apr 17 2013