OFFSET
0,3
COMMENTS
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.
From David Callan, Sep 25 2006: (Start)
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.
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.
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:
..|....|...../\.../\
./ \...|....|.......|
.......|
(End)
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..1828
Christopher Bao, Yunseo Choi, Katelyn Gan, and Owen Zhang, On a Conjecture by Baril, Cerbai, Khalil, and Vajnovszki on Two Restricted Stacks, arXiv:2308.09344 [math.CO], 2023.
Paul Barry, On Motzkin-Schröder Paths, Riordan Arrays, and Somos-4 Sequences, J. Int. Seq. (2023) Vol. 26, Art. 23.4.7.
Emeric Deutsch, An involution on Dyck paths and its consequences, Discrete Math., 204 (1999), no. 1-3, 163-166.
A. Sapounakis, I. Tasoulas and P. Tsikouras, Counting strings in Dyck paths, Discrete Math., 307 (2007), 2909-2924.
FORMULA
G.f.: (1+z-z^2 - sqrt(1-2*z-5*z^2-2*z^3+z^4))/(2*z).
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
From Gary W. Adamson, Jul 11 2011: (Start)
Let M = the following infinite square production matrix (where the main diagonal is (1,0,1,0,1,0,...)):
1, 1, 0, 0, 0, 0, ...
1, 0, 1, 0, 0, 0, ...
1, 1, 1, 1, 0, 0, ...
1, 1, 1, 0, 1, 0, ...
1, 1, 1, 1, 1, 1, ...
1, 1, 1, 1, 1, 0, ...
...
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)
(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
EXAMPLE
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).
MAPLE
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);
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
MATHEMATICA
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 *)
PROG
(Magma)
R<x>:=PowerSeriesRing(Rationals(), 30);
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
(SageMath)
def A102407_list(prec):
P.<x> = PowerSeriesRing(ZZ, prec)
return P( (1+x-x^2 -sqrt(1-2*x-5*x^2-2*x^3+x^4))/(2*x) ).list()
A102407_list(30) # G. C. Greubel, Oct 31 2024
CROSSREFS
KEYWORD
nonn,changed
AUTHOR
Emeric Deutsch, Jan 06 2005
STATUS
approved