login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo

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.

License Agreements, Terms of Use, Privacy Policy. .

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