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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A005775 Number of compact-rooted directed animals of size n having 3 source points.
(Formerly M3481)
5
1, 4, 14, 45, 140, 427, 1288, 3858, 11505, 34210, 101530, 300950, 891345, 2638650, 7809000, 23107488, 68375547, 202336092, 598817490, 1772479905, 5247421410, 15538054455, 46019183840, 136325212750, 403933918375, 1197131976846, 3548715207534, 10521965227669 (list; graph; refs; listen; history; text; internal format)
OFFSET

3,2

COMMENTS

Binomial transform of A037955. - Paul Barry, Dec 28 2006

Apparently, the number of Dyck paths of semilength n that contain at least one UUU but avoid UUU's starting above level 0. - David Scambler, Jul 02 2013

a(n) = number of paths in the half-plane x>=0 from (0,0) to (n-1,2) or (n-1,-3), and consisting of steps U=(1,1), D=(1,-1) and H=(1,0). For example, for n=5, we have the 14 paths: HHUU, UUHH, UHHU, HUUH, HUHU, UHUH, UDUU, UUDU, UUUD, DUUU, DDDH, HDDD, DHDD, DDHD. - José Luis Ramírez Ramírez, Apr 19 2015

REFERENCES

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

LINKS

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

D. Gouyou-Beauchamps, G. Viennot, Equivalence of the two-dimensional directed animal problem to a one-dimensional path problem, Adv. in Appl. Math. 9 (1988), no. 3, 334-357.

FORMULA

(n+2)*(n-3)*a(n) = 2*n*(n-1)*a(n-1) + 3*(n-1)*(n-2)*a(n-2), a(2)=0, a(3)=1. - Michael Somos, Feb 02 2002

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

E.g.f.: exp(x)*(Bessel_I(2,2*x) + Bessel_I(3,2*x)); a(n+1)=sum{k=0..n, C(n,k)*C(k,floor(k/2)-1)};. - Paul Barry, Dec 28 2006

a(n) ~ 3^(n-1/2) / sqrt(Pi*n). - Vaclav Kotesovec, Feb 25 2014

G.f.: (z^3*M(z)^2+z^4*M(z)^3)/(1-z-2*z^2*M(z)), where M(z) is the g.f. of Motzkin paths. - José Luis Ramírez Ramírez, Apr 19 2015

a(n) = GegenbauerC(n-4,-n+1,-1/2) + GegenbauerC(n-3,-n+1,-1/2). - Peter Luschny, May 12 2016

0 = a(n)*(+9*a(n+1) - 63*a(n+2) - 54*a(n+3) + 87*a(n+4) - 21*a(n+5))+ a(n+1)*(+21*a(n+1) + 79*a(n+2) + 13*a(n+3) - 118*a(n+4) + 35*a(n+5)) + a(n+2)*(-14*a(n+2) + 79*a(n+3) - 67*a(n+4) + 14*a(n+5)) + a(n+3)*(+6*a(n+3) + 19*a(n+4) - 11*a(n+5)) + a(n+4)*(+a(n+4) + a(n+5)) if n>=0. - Michael Somos, May 12 2016

EXAMPLE

G.f. = x^3 + 4*x^4 + 14*x^5 + 45*x^6 + 140*x^7 + 427*x^8 + 1288*x^9 + 3858*x^10 + ...

MAPLE

seq(simplify(GegenbauerC(n-4, -n+1, -1/2) + GegenbauerC(n-3, -n+1, -1/2)), n=3..28); # Peter Luschny, May 12 2016

MATHEMATICA

nmax = 28; t[n_ /; n > 0, k_ /; k >= 1] := t[n, k] = t[n-1, k-1] + t[n-1, k] + t[n-1, k+1]; t[0, 0] = 1; t[0, _] = 0; t[_?Negative, _?Negative] = 0; t[n_, 0] := 2*t[n-1, 0] + t[n-1, 1]; a[n_] := t[n-1, 2]; Table[a[n], {n, 3, nmax} ] (* Jean-François Alcover, Jul 03 2013, from A038622 *)

PROG

(PARI) {a(n) = polcoeff( (x^2 + x - 1 + (x^2 - 3*x + 1) * sqrt((1 + x) / (1 - 3*x) + x^3 * O(x^n))) / (2*x^2), n)};

(PARI) {a(n) = n--; sum(k=0, n, binomial(n, k) * binomial(k, k\2 -1))}; /* Michael Somos, May 12 2016 */

(Haskell)

a005775 = flip a038622 2 . (subtract 1)  -- Reinhard Zumkeller, Feb 26 2013

CROSSREFS

Cf. A005773.

k=2 column of array in A038622.

Cf. A005774, A066822.

Sequence in context: A182902 A108765 A304068 * A094688 A068092 A255678

Adjacent sequences:  A005772 A005773 A005774 * A005776 A005777 A005778

KEYWORD

nonn,easy

AUTHOR

Simon Plouffe

EXTENSIONS

More terms from Randall L. Rathbun, Jan 19 2002

Edited by Michael Somos, Feb 02 2002

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 October 19 20:05 EDT 2018. Contains 316378 sequences. (Running on oeis4.)