cp's OEIS Frontend

A102407 Number of Dyck paths of semilength n having no ascents of length 1 that start at an odd level.

%I A102407 #46 Jan 18 2025 01:59:32
%S A102407 1,1,2,4,10,26,72,206,606,1820,5558,17206,53872,170298,542778,1742308,
%T A102407 5627698,18277698,59652952,195541494,643506310,2125255036,7041631854,
%U A102407 23400092142,77971706848,260458050034,872040564850,2925902656644,9836517749658,33130048199466
%N A102407 Number of Dyck paths of semilength n having no ascents of length 1 that start at an odd level.
%C A102407 Number of Łukasiewicz paths of length n having no level steps at an odd level. A Łukasiewicz path of length n is a path in the first quadrant from (0,0) to (n,0) using rise steps (1,k) for any positive integer k, level steps (1,0) and fall steps (1,-1) (see R. P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge Univ. Press, Cambridge, 1999, p. 223, Exercise 6.19w; the integers are the slopes of the steps). Example: a(2)=2 because we have HH and UD, where U=(1,1), H=(1,0) and D=(1,-1). Column 0 of A102405.
%C A102407 From _David Callan_, Sep 25 2006: (Start)
%C A102407 a(n) is the number of Dyck n-paths containing no DUDUs. For example, a(3) = 4 counts all five Dyck 3-paths except UDUDUD.
%C A102407 a(n) is the number of Dyck n-paths containing no subpath of the form UUPDD where P is a nonempty Dyck path. For example, a(3) = 4 counts all five Dyck 3-paths except UUUDDD. Deutsch's involution phi on Dyck paths interchanges #DUDUs and #UUPDDs with P a nonempty Dyck path. Phi is defined recursively by phi({})={}, phi(UPDQ)=U phi(Q) D phi(P) where P,Q are Dyck paths.
%C A102407 a(n) is the number of ordered trees on n edges in which each leaf is either the leftmost or rightmost child of its parent. For example, a(3) counts:
%C A102407   ..|....|...../\.../\
%C A102407   ./ \...|....|.......|
%C A102407   .......|
%C A102407 (End)
%H A102407 Alois P. Heinz, <a href="/A102407/b102407.txt">Table of n, a(n) for n = 0..1828</a>
%H A102407 Christopher Bao, Yunseo Choi, Katelyn Gan, and Owen Zhang, <a href="https://arxiv.org/abs/2308.09344">On a Conjecture by Baril, Cerbai, Khalil, and Vajnovszki on Two Restricted Stacks</a>, arXiv:2308.09344 [math.CO], 2023.
%H A102407 Paul Barry, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL26/Barry/barry601.html">On Motzkin-Schröder Paths, Riordan Arrays, and Somos-4 Sequences</a>, J. Int. Seq. (2023) Vol. 26, Art. 23.4.7.
%H A102407 Emeric Deutsch, <a href="http://dx.doi.org/10.1016/S0012-365X(98)00370-7">An involution on Dyck paths and its consequences</a>, Discrete Math., 204 (1999), no. 1-3, 163-166.
%H A102407 A. Sapounakis, I. Tasoulas and P. Tsikouras, <a href="http://dx.doi.org/10.1016/j.disc.2007.03.005">Counting strings in Dyck paths</a>, Discrete Math., 307 (2007), 2909-2924.
%H A102407 <a href="/index/Lu#Lukasiewicz">Index entries for sequences related to Łukasiewicz</a>
%F A102407 G.f.: (1+z-z^2 - sqrt(1-2*z-5*z^2-2*z^3+z^4))/(2*z).
%F A102407 a(n) = Sum_{j=0..floor(n/2)} Sum_{i=0..n-2*j} (1/(n-j))*binomial(n-j,j) * binomial(n-2*j,i)*binomial(j+i, n-2*j-i+1) (from Sapounakis et al.). - _N. J. A. Sloane_, Dec 06 2007
%F A102407 From _Gary W. Adamson_, Jul 11 2011: (Start)
%F A102407 Let M = the following infinite square production matrix (where the main diagonal is (1,0,1,0,1,0,...)):
%F A102407   1, 1, 0, 0, 0, 0, ...
%F A102407   1, 0, 1, 0, 0, 0, ...
%F A102407   1, 1, 1, 1, 0, 0, ...
%F A102407   1, 1, 1, 0, 1, 0, ...
%F A102407   1, 1, 1, 1, 1, 1, ...
%F A102407   1, 1, 1, 1, 1, 0, ...
%F A102407   ...
%F A102407 a(n) = top left term in M^n, a(n+1) = sum of top row terms in M^n. Example: top row of M^5 = (26, 19, 16, 7, 3, 1, 0, 0, 0, ...) where 26 = a(5) and 72 = a(6) = (26 + 19 + 16 + 7 + 3 + 1). (End)
%F A102407 (n+1)*a(n) -(2*n-1)*a(n-1) -5*(n-2)*a(n-2) -(2*n-7)*a(n-3) +(n-5)*a(n-4) = 0. - _R. J. Mathar_, Jan 04 2017
%e A102407 a(3)=4 because among the five Dyck paths of semilength 3 only UUDUDD has an ascent of length 1 that starts at an odd level; here U=(1,1) and D=(1,-1).
%p A102407 G:=(1+z-z^2-sqrt(1-2*z-5*z^2-2*z^3+z^4))/2/z: Gser:=series(G,z=0,31): 1,seq(coeff(Gser,z^n),n=1..29);
%p A102407 f:=proc(n) local i,j; add( (1/(n-j))*binomial(n-j,j)* add( binomial(n-2*j,i)*binomial(j+i, n-2*j-i+1), i=0..n-2*j), j=0..n/2 ); end; # _N. J. A. Sloane_, Dec 06 2007
%t A102407 CoefficientList[Series[(1+x-x^2 -Sqrt[1-2 x -5 x^2 -2 x^3 +x^4])/(2 x), {x, 0, 30}], x] (* _Vincenzo Librandi_, Mar 20 2015 *)
%o A102407 (Magma)
%o A102407 R<x>:=PowerSeriesRing(Rationals(), 30);
%o A102407 Coefficients(R!( (1+x-x^2 -Sqrt(1-2*x-5*x^2-2*x^3+x^4))/(2*x) )); // _G. C. Greubel_, Oct 31 2024
%o A102407 (SageMath)
%o A102407 def A102407_list(prec):
%o A102407     P.<x> = PowerSeriesRing(ZZ, prec)
%o A102407     return P( (1+x-x^2 -sqrt(1-2*x-5*x^2-2*x^3+x^4))/(2*x) ).list()
%o A102407 A102407_list(30) # _G. C. Greubel_, Oct 31 2024
%Y A102407 Cf. A102405, A102406.
%K A102407 nonn
%O A102407 0,3
%A A102407 _Emeric Deutsch_, Jan 06 2005