login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
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.) 8
0, 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

0,4

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 = 0..1892

Jean-Luc Baril, Richard Genestier, and Sergey Kirgizov, Pattern distributions in Dyck paths with a first return decomposition constrained by height, arXiv:1911.03119 [math.CO], 2019.

Y. Din and 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)).

From Vladeta Jovovic, Jul 24 2005: (Start)

a(n) = (A002426(n) - 1)/2.

E.g.f.: exp(x)*(BesselI(0, 2*x) - 1)/2. (End)

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

From Peter Luschny, Jun 01 2021: (Start)

a(n) = (1/2)*(hypergeom([1/2 - n/2, -n/2], [1], 4) - 1).

a(n) = (1/2)*2^(-n)*n!*[x^n] Exp(2*x, 1)*(Exp(2*x, 2) - 1), where Exp(x, m) = Sum_{k>=0} (x^k / k!)^m. Cf. A344559.  (End)

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 = 0..32);

# Alternative:

a := n -> add(binomial(n, j)*binomial(n-j, j)/2, j=1..n):

seq(a(n), n = 0..27); # Zerinvary Lajos, Sep 24 2006

# Third program:

Exp := (x, m) -> sum((x^k / k!)^m, k = 0..infinity):

egf := Exp(2*x, 1)*(Exp(2*x, 2) - 1): ser := series(egf, x, 32):

seq((1/2)*2^(-n)*n!*simplify(coeff(ser, x, n)), n = 0..29); # Peter Luschny, Jun 01 2021

MATHEMATICA

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 *)

a[n_] := (1/2)*(HypergeometricPFQ[{1/2 - n/2, -n/2}, {1}, 4] - 1);

Table[a[n], {n, 0, 29}] (* Peter Luschny, Jun 01 2021 *)

PROG

(Magma) I := [0, 0, 1, 3]; [n le 4 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, A344559.

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

EXTENSIONS

a(0) = 0 prepended by Peter Luschny, Jun 01 2021

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 26 20:44 EDT 2022. Contains 357048 sequences. (Running on oeis4.)