login
This site is supported by donations 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.) 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

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: A007046 A211286 A211285 * A211284 A211283 A058719

Adjacent sequences:  A097858 A097859 A097860 * A097862 A097863 A097864

KEYWORD

nonn

AUTHOR

Emeric Deutsch, Sep 01 2004

EXTENSIONS

a(28)-a(29) from Vincenzo Librandi, Sep 14 2015

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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified June 22 07:47 EDT 2017. Contains 288605 sequences.