

A097861


Number of humps in all Motzkin paths of length n. (A hump is an upstep followed by 0 or more flatsteps followed by a downstep.)


6



0, 1, 3, 9, 25, 70, 196, 553, 1569, 4476, 12826, 36894, 106470, 308113, 893803, 2598313, 7567465, 22076404, 64498426, 188689684, 552675364, 1620567763, 4756614061, 13974168190, 41088418150, 120906613075, 356035078101, 1049120176953, 3093337815409
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,3


COMMENTS

If the independent variable x in the g.f. is subjected to the transformation x>x/(1+x+x^2), an inverse Motzkin transform, the 4periodic sequence 0,1,bar(2,3,2,2) (offset 0) results, where bar(...) denotes the period.  R. J. Mathar, Nov 10 2008
Also, a(n) is the number of combinations of two disjoint subsets of equal size from a set of n items, where k, the size of the subset, goes from 1 to floor(n/2) inclusive. For each k, k items are chosen from n. Then k items are chosen from the remaining (n  k) items. Since each pair "kSubSetkSubSet" is chosen twice, once as "AB", once as "BA", in order to remove repetitions, the number must be divided by 2. Since C(n, n + d) = 0 when d>0, the upper limit can be safely increased from floor(n/2) to n. Thus a(n) = Sum_{k=1..n} C(n,k)*C(nk,k)/2.  Viktar Karatchenia, Sep 09 2015


LINKS

Robert Israel, Table of n, a(n) for n = 1..1892
JeanLuc Baril, Richard Genestier, Sergey Kirgizov, Pattern distributions in Dyck paths with a first return decomposition constrained by height, arXiv:1911.03119 [math.CO], 2019.
Y. Din, R. R. X. Du, Counting Humps in Motzkin paths, arXiv:1109.2661 (2011) Eq. (2.2).
László Németh, The trinomial transform triangle, J. Int. Seqs., Vol. 21 (2018), Article 18.7.3. Also arXiv:1807.07109 [math.NT], 2018.


FORMULA

G.f.: (1zsqrt(12*z3*z^2))/(2*(1z)*sqrt(12*z3*z^2)).
a(n) = (A002426(n)1)/2. E.g.f.: exp(x)*(BesselI(0, 2*x)1)/2.  Vladeta Jovovic, Jul 24 2005
a(n) = Sum_{j=1..n} C(n,j)*C(nj,j)/2.  Zerinvary Lajos, Sep 24 2006
n*(n2)*a(n)  (3*n^27*n+3)*a(n1) (n1)*(n3)*a(n2) +3*(n1)*(n2)*a(n3) = 0.  R. J. Mathar, Feb 21 2010


EXAMPLE

a(3) = 3 because in all Motzkin paths of length 3 we have 3 humps, shown between parentheses: FFF, F(UD), (UD)F, (UFD) (here U=(1,1), F=(1,0), D=(1,1)).
a(5) = (10 + 15) = 25 combinations of two equal size distinct subsets, i.e. given 5 items, there are 10 distinct pairs of size 1: "12, 13, 14, 15, and 23, 24, 25, and 34, 35, 45". Plus 15 distinct pairs of size 2: "1234, 1235, 1245, and 1324, 1325, 1345, and 1423, 1425, 1435, and 1523, 1524, 1534, and 2345, 2435, 2534".  Viktar Karatchenia, Sep 09 2015


MAPLE

G:=(1zsqrt(12*z3*z^2))/2/(1z)/sqrt(12*z3*z^2): Gser:=series(G, z=0, 33): seq(coeff(Gser, z^n), n=1..32);
a:= n>sum(binomial(n, j)*binomial(nj, j)/2, j=1..n): seq(a(n), n=1..27); # Zerinvary Lajos, Sep 24 2006


MATHEMATICA

Rest[CoefficientList[Series[(1  z  Sqrt[1  2 z  3 z^2])/(2 (1  z) Sqrt[1  2 z  3 z^2]), {z, 0, 33}], z]] (* Vincenzo Librandi, Sep 14 2015 *)


PROG

(MAGMA) I:=[0, 1, 3]; [n le 3 select I[n] else ((3*n^27*n+3)*Self(n1)+(n1)*(n3)*Self(n2)3*(n1)*(n2)*Self(n3)) div (n*(n2)): n in [1..30]]; // Vincenzo Librandi, Sep 14 2015


CROSSREFS

Cf. A097229.
Sequence in context: A211286 A211285 A333498 * A211284 A211283 A333608
Adjacent sequences: A097858 A097859 A097860 * A097862 A097863 A097864


KEYWORD

nonn,easy


AUTHOR

Emeric Deutsch, Sep 01 2004


STATUS

approved



