login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A082582 Expansion of (1 + x^2 - sqrt( 1 - 4*x + 2*x^2 + x^4)) / (2*x) in powers of x. 59
1, 1, 1, 2, 5, 13, 35, 97, 275, 794, 2327, 6905, 20705, 62642, 190987, 586219, 1810011, 5617914, 17518463, 54857506, 172431935, 543861219, 1720737981, 5459867166, 17369553427, 55391735455, 177040109419, 567019562429, 1819536774089 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,4

COMMENTS

a(n) = number of Dyck paths of semilength n with no UUDD. See A025242 for a bijection between paths avoiding DDUU versus UUDD.

Also number of lattice paths from (0,0) to (n,n) which do not go above the diagonal x=y using steps (1,k), (k,1) with k>=1. - Alois P. Heinz, Oct 07 2015

a(n) = number of bargraphs of semiperimeter n (n>=2). Example: a(4) = 5; the 5 bargraphs correspond to the compositions [1,1,1], [1,2], [2,1], [2,2], [3]. - Emeric Deutsch, May 20 2016

LINKS

Reinhard Zumkeller, Table of n, a(n) for n = 0..1000

A. Blecher, C. Brennan, and A. Knopfmacher, Peaks in bargraphs, Trans. Royal Soc. South Africa, 71, No. 1, 2016, 97-103.

M. Bousquet-Mélou and A. Rechnitzer, The site-perimeter of bargraphs, Adv. in Appl. Math. 31 (2003), 86-112.

Emeric Deutsch, Sergi Elizalde, Statistics on bargraphs viewed as cornerless Motzkin paths, arXiv:1609.00088 [math.CO], (September 2016)

FORMULA

G.f.: (1 + x^2 - sqrt( 1 - 4*x + 2*x^2 + x^4)) / (2*x) = 2 /(1 + x^2 + sqrt( 1 - 4*x + 2*x^2 + x^4)).

G.f. A(x) satisfies the equation 0 = 1 - (1 + x^2) * A(x) + x * A(x)^2. - Michael Somos, Jul 22 2003

G.f. A(x) satisfies A(x) = 1 / (1 + x^2 - x * A(x)). - Michael Somos, Mar 28 2011

G.f. A(x) = 1 / (1 + x^2 - x / (1 + x^2 - x / (1 + x^2 - ... ))) continued fraction. - Michael Somos, Jul 01 2011

Series reversion of x * A(x) is x * A007477(-x). - Michael Somos, Jul 22 2003

a(n+1) = a(n) + Sum(a(k)*a(n-k): k=2..n), a(0) = a(1) = 1. - Reinhard Zumkeller, Nov 13 2012

G.f.: 1 + x - x*G(0), where G(k)= 1 - 1/(1 - x/(1 - x/(1 - x/(1 - x/(x - 1/G(k+1) ))))); (continued fraction). - Sergei N. Gladkovskii, Jul 12 2013

(n-1)*a(n)+(2*n+4)*a(n+2)+(-14-4*n)*a(n+3)+(5+n)*a(n+4) = 0. - Robert Israel, May 20 2016

EXAMPLE

1 + x + x^2 + 2*x^3 + 5*x^4 + 13*x^5 + 35*x^6 + 97*x^7 + 275*x^8 + ...

a(3)=2 because the only Dyck paths of semilength 3 with no UUDD in them are UDUDUD and UUDUDD (the nonqualifying ones being UDUUDD, UUDDUD and UUUDDD). - Emeric Deutsch, Jan 27 2003

MAPLE

f:= gfun:-rectoproc({(n-1)*a(n)+(2*n+4)*a(n+2)+(-14-4*n)*a(n+3)+(5+n)*a(n+4), a(0) = 1, a(1) = 1, a(2) = 1, a(3) = 2}, a(n), remember):

map(f, [$0..100]); # Robert Israel, May 20 2016

MATHEMATICA

a[0]=1; a[n_Integer]:=a[n]=a[n-1]+Sum[a[k]*a[n-1-k], {k, 2, n-1}]; Table[a[n], {n, 0, 40}] (* Vladimir Joseph Stephan Orlovsky, Mar 30 2011 *)

a[ n_] := SeriesCoefficient[ 2 / (1 + x^2 + Sqrt[1 - 4 x + 2 x^2 + x^4]), {x, 0, n}] (* Michael Somos, Jul 01 2011 *)

PROG

(PARI) {a(n) = polcoeff( (1 + x^2 - sqrt( 1 - 4*x + 2*x^2 + x^4 + x^2 * O(x^n))) / 2, n+1)} /* Michael Somos, Jul 22 2003 */

(PARI) {a(n) = if( n<0, 0, polcoeff( 2 /(1 + x^2 + sqrt( 1 - 4*x + 2*x^2 + x^4 + x * O(x^n))), n))} /* Michael Somos, Jul 01 2011 */

(PARI) {a(n) = local(A); if( n<0, 0, A = O(x); for( k = 0, n, A = 1 / (1 + x^2 - x * A)); polcoeff( A, n))} /* Michael Somos, Mar 28 2011 */

(Haskell)

a082582 n = a082582_list !! n

a082582_list = 1 : 1 : f [1, 1] where

   f xs'@(x:_:xs) = y : f (y : xs') where

     y = x + sum (zipWith (*) xs' $ reverse xs)

-- Reinhard Zumkeller, Nov 13 2012

CROSSREFS

Apart from initial term, same as A025242.

See A086581 for Dyck paths avoiding DDUU.

Cf. A218321, A263316.

Sequence in context: A007689 A085281 * A086581 A059027 A025198 A221205

Adjacent sequences:  A082579 A082580 A082581 * A082583 A082584 A082585

KEYWORD

easy,nonn

AUTHOR

Emanuele Munarini, May 07 2003

EXTENSIONS

Example moved from A086581 to here.

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 March 26 10:42 EDT 2017. Contains 284111 sequences.