A005775 Number of compact-rooted directed animals of size n having 3 source points.

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

Offset: 3

Author

Simon Plouffe

Keywords

• nonn
• easy

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

Examples

			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 + ...
		

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
• Jean-Luc Baril and José Luis Ramírez, Descent distribution on Catalan words avoiding ordered pairs of Relations, arXiv:2302.12741 [math.CO], 2023.
• D. Gouyou-Beauchamps and 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.

Crossrefs

Cf. A005773.

k=2 column of array in A038622.

Cf. A005774, A066822.

Programs

Haskell

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

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 *)

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 */

Formula

D-finite with recurrence (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).

From Paul Barry, Dec 28 2006: (Start)

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). (End)

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

a(n) = A005773(n) - A001006(n) for n >= 3. - John Keith, Nov 20 2020

Extensions

More terms from Randall L Rathbun, Jan 19 2002

Edited by Michael Somos, Feb 02 2002