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

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

Offset: 0

Author

Emeric Deutsch, Sep 01 2004

Keywords

• nonn
• easy

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

Examples

			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
		

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.

Crossrefs

Cf. A097229, A344559.

Programs

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

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

Python

from sympy import hyperexpand, S
from sympy.functions import hyper
def A097861(n): return hyperexpand(hyper(((1-n)*S.Half,-n*S.Half),(1,),4))-1>>1 # Chai Wah Wu, Jan 04 2024

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)

Extensions

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