|
|
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
|
|
|
FORMULA
|
G.f.: (1 - z - sqrt(1 - 2*z - 3*z^2))/(2*(1 - z)*sqrt(1 - 2*z - 3*z^2)).
E.g.f.: exp(x)*(BesselI(0, 2*x) - 1)/2. (End)
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
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):
# 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);
|
|
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
(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
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|