The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation. Please make a donation to keep the OEIS running. We are now in our 56th year. In the past year we added 10000 new sequences and reached almost 9000 citations (which often say "discovered thanks to the OEIS"). Other ways to donate

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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 4-periodic 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 "kSubSet|kSubSet" is chosen twice, once as "A|B", once as "B|A", 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(n-k,k)/2. - Viktar Karatchenia, Sep 09 2015 LINKS Robert Israel, Table of n, a(n) for n = 1..1892 Jean-Luc 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.: (1-z-sqrt(1-2*z-3*z^2))/(2*(1-z)*sqrt(1-2*z-3*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(n-j,j)/2. - Zerinvary Lajos, Sep 24 2006 n*(n-2)*a(n) - (3*n^2-7*n+3)*a(n-1) -(n-1)*(n-3)*a(n-2) +3*(n-1)*(n-2)*a(n-3) = 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: "1|2, 1|3, 1|4, 1|5, and 2|3, 2|4, 2|5, and 3|4, 3|5, 4|5". Plus 15 distinct pairs of size 2: "12|34, 12|35, 12|45, and 13|24, 13|25, 13|45, and 14|23, 14|25, 14|35, and 15|23, 15|24, 15|34, and 23|45, 24|35, 25|34". - Viktar Karatchenia, Sep 09 2015 MAPLE G:=(1-z-sqrt(1-2*z-3*z^2))/2/(1-z)/sqrt(1-2*z-3*z^2): Gser:=series(G, z=0, 33): seq(coeff(Gser, z^n), n=1..32); a:= n->sum(binomial(n, j)*binomial(n-j, 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^2-7*n+3)*Self(n-1)+(n-1)*(n-3)*Self(n-2)-3*(n-1)*(n-2)*Self(n-3))  div (n*(n-2)): 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified November 30 05:30 EST 2020. Contains 338781 sequences. (Running on oeis4.)