|
%I #73 Jan 04 2024 14:03:52
%S 0,0,1,3,9,25,70,196,553,1569,4476,12826,36894,106470,308113,893803,
%T 2598313,7567465,22076404,64498426,188689684,552675364,1620567763,
%U 4756614061,13974168190,41088418150,120906613075,356035078101,1049120176953,3093337815409
%N 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.)
%C 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
%C 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
%H Robert Israel, <a href="/A097861/b097861.txt">Table of n, a(n) for n = 0..1892</a>
%H Jean-Luc Baril, Richard Genestier, and Sergey Kirgizov, <a href="https://arxiv.org/abs/1911.03119">Pattern distributions in Dyck paths with a first return decomposition constrained by height</a>, arXiv:1911.03119 [math.CO], 2019.
%H Y. Din and R. R. X. Du, <a href="http://arxiv.org/abs/1109.2661">Counting Humps in Motzkin paths</a>, arXiv:1109.2661 (2011) Eq. (2.2).
%H László Németh, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL21/Nemeth/nemeth6.html">The trinomial transform triangle</a>, J. Int. Seqs., Vol. 21 (2018), Article 18.7.3. Also <a href="https://arxiv.org/abs/1807.07109">arXiv:1807.07109</a> [math.NT], 2018.
%F G.f.: (1 - z - sqrt(1 - 2*z - 3*z^2))/(2*(1 - z)*sqrt(1 - 2*z - 3*z^2)).
%F From _Vladeta Jovovic_, Jul 24 2005: (Start)
%F a(n) = (A002426(n) - 1)/2.
%F E.g.f.: exp(x)*(BesselI(0, 2*x) - 1)/2. (End)
%F a(n) = Sum_{j=1..n} C(n, j)*C(n-j, j)/2. - _Zerinvary Lajos_, Sep 24 2006
%F 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
%F From _Peter Luschny_, Jun 01 2021: (Start)
%F a(n) = (1/2)*(hypergeom([1/2 - n/2, -n/2], [1], 4) - 1).
%F 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)
%e 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)).
%e 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
%p G := (1-z-sqrt(1-2*z-3*z^2))/2/(1-z)/sqrt(1-2*z-3*z^2):
%p Gser := series(G, z=0, 33): seq(coeff(Gser, z^n), n = 0..32);
%p # Alternative:
%p a := n -> add(binomial(n,j)*binomial(n-j,j)/2, j=1..n):
%p seq(a(n), n = 0..27); # _Zerinvary Lajos_, Sep 24 2006
%p # Third program:
%p Exp := (x, m) -> sum((x^k / k!)^m, k = 0..infinity):
%p egf := Exp(2*x, 1)*(Exp(2*x, 2) - 1): ser := series(egf, x, 32):
%p seq((1/2)*2^(-n)*n!*simplify(coeff(ser, x, n)), n = 0..29); # _Peter Luschny_, Jun 01 2021
%t 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 *)
%t a[n_] := (1/2)*(HypergeometricPFQ[{1/2 - n/2, -n/2}, {1}, 4] - 1);
%t Table[a[n], {n, 0, 29}] (* _Peter Luschny_, Jun 01 2021 *)
%o (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
%o (Python)
%o from sympy import hyperexpand, S
%o from sympy.functions import hyper
%o def A097861(n): return hyperexpand(hyper(((1-n)*S.Half,-n*S.Half),(1,),4))-1>>1 # _Chai Wah Wu_, Jan 04 2024
%Y Cf. A097229, A344559.
%K nonn,easy
%O 0,4
%A _Emeric Deutsch_, Sep 01 2004
%E a(0) = 0 prepended by _Peter Luschny_, Jun 01 2021
|
