|
| |
|
|
A102407
|
|
Number of Dyck paths of semilength n having no ascents of length 1 that start at an odd level.
|
|
4
|
|
|
|
1, 1, 2, 4, 10, 26, 72, 206, 606, 1820, 5558, 17206, 53872, 170298, 542778, 1742308, 5627698, 18277698, 59652952, 195541494, 643506310, 2125255036, 7041631854, 23400092142, 77971706848, 260458050034, 872040564850, 2925902656644, 9836517749658, 33130048199466
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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.
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
|
|
|
|
FORMULA
|
G.f.: (1+z-z^2-sqrt(1-2z-5z^2-2z^3+z^4))/(2z).
For an explicit formula (from Sapounakis et al.) see the Maple program.
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). - Gary W. Adamson, Jul 11 2011
Conjecture: (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 *)
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
