%I A005773 M1443
%S A005773 1,1,2,5,13,35,96,267,750,2123,6046,17303,49721,143365,414584,1201917,
%T A005773 3492117,10165779,29643870,86574831,253188111,741365049,2173243128,
%U A005773 6377181825,18730782252,55062586341,161995031226,476941691177
%N A005773 Number of directed animals of size n (or directed n-ominoes in standard 
               position).
%C A005773 Sequence, with first term a(0) deleted, appears to be determined by conditions 
               that diagonal and first superdiagonal of U are {1,1,1,1,...} and 
               {2,3,4,5,...,n+1,...}, where A=LU is LU factorization of Hankel matrix 
               A given by [{a(1),a(2),...},{a(2),a(3),...},...,{a(n),a(n+1),...},
               ...]- John W. Layman (layman(AT)math.vt.edu), Jul 21 2000
%C A005773 Also the number of base 3 n-digit numbers with digit sum n. For the analogous 
               sequence in base 10 see A071976. - John W. Layman (layman(AT)math.vt.edu), 
               Jun 22 2002
%C A005773 Also number of paths in an n X n grid from (0,0) to the line x=n-1, using 
               only steps U=(1,1), H=(1,0) and D=(1,-1) (i.e. left factors of length 
               n-1 of Motzkin paths). Example: a(3)=5, namely, HH, UD, HU, UH and 
               UU. Also number of ordered trees with n edges and having nonroot 
               nodes of outdegree at most 2. - Emeric Deutsch (deutsch(AT)duke.poly.edu), 
               Aug 01 2002
%C A005773 Number of symmetric Dyck paths of semilength 2n-1 with no peaks at even 
               level. Example: a(3)=5 because we have UDUDUDUDUD, UDUUUDDDUD, UUUUUDDDDD, 
               UUUDUDUDDD and UUUDDUUDDD, where U=(1,1) and D=(1,-1). Also number 
               of symmetric Dyck paths of semilength 2n with no peaks at even level. 
               Example: a(3)=5 because we have UDUDUDUDUDUD, UDUUUDUDDDUD, UUUDUDUDUDDD, 
               UUUUUDUDDDDD and UUUDDDUUUDDD. - Emeric Deutsch (deutsch(AT)duke.poly.edu), 
               Nov 21 2003
%C A005773 a(n)=sum of (n-1)-st central trinomial coefficient and its predecessor. 
               Example: a(4)=6+7 and (1+x+x^2)^3=...+ 6*x^2 + 7*x^3 +... . - David 
               Callan (callan(AT)stat.wisc.edu), Feb 07 2004
%C A005773 a(n)=number of UDU-free paths of n upsteps (U) and n downsteps (D) that 
               start U (n>=1). Example. a(2)=2 counts UUDD, UDDU. - David Callan 
               (callan(AT)stat.wisc.edu), Aug 18 2004
%C A005773 Hankel transform of a(n+1) = [1,2,5,13,35,96,...]gives A000012 = [1,1,
               1,1,1,1,...] . - Philippe DELEHAM (kolotoko(AT)wanadoo.fr), Oct 24 
               2007
%C A005773 Equals row sums of triangle A136787 starting (1, 2, 5, 13, 35,...). - 
               Gary W. Adamson (qntmpkt(AT)yahoo.com), Jan 21 2008
%C A005773 a(n) = number of permutations on [n] that avoid the patterns 1-23-4 and 
               1-3-2, where the omission of a dash in a pattern means the permutation 
               entries must be adjacent. Example: a(4) = 13 counts all 14 (Catalan 
               number) (1-3-2)-avoiding permutations on [4] except 1234. - David 
               Callan (callan(AT)stat.wisc.edu), Jul 22 2008
%C A005773 Contribution from Eric Egge (eegge(AT)carleton.edu), Oct 21 2008: (Start)
%C A005773 a(n) is also the number of involutions of length 2n-2 which are
%C A005773 invariant under the reverse-complement map and have no decreasing
%C A005773 subsequences of length 4. (End)
%C A005773 Hankel transform is A010892. [From Paul Barry (pbarry(AT)wit.ie), Jan 
               19 2009]
%C A005773 Starting (1, 2, 5, 13,...) = row sums of triangle A158793 [From Gary 
               W. Adamson (qntmpkt(AT)yahoo.com), Mar 26 2009]
%C A005773 a(n) = the number of Dyck words of semilength n with no DUUU. For example, 
               a(4) = 14-1 = 13 because there is only one Dyck 4-word containing 
               DUUU, namely UDUUUDDD. [From Eric S Rowland (erowland(AT)math.rutgers.edu), 
               Apr 21 2009]
%D A005773 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, 
               Academic Press, 1995 (includes this sequence).
%D A005773 A. Sapounakis, I. Tasoulas and P. Tsikouras, Counting strings in Dyck 
               paths, Discrete Math., 307 (2007), 2909-2924.
%D A005773 E. Barcucci et al., From Motzkin to Catalan Permutations, Discr. Math., 
               217 (2000), 33-49.
%D A005773 M. Bousquet-M\'{e}lou, New enumerative results on two-dimensional directed 
               animals, Discr. Math., 180 (1998), 73-106.
%D A005773 D. Dhar et al., Enumeration of directed site animals on two-dimensional 
               lattices, J. Phys. A 15 (1982), L279-L284.
%D A005773 J. E. Goodman and J. O'Rourke, editors, Handbook of Discrete and Computational 
               Geometry, CRC Press, 1997, p. 237.
%D A005773 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.
%D A005773 T. Mansour, Restricted 1-3-2 permutations and generalized patterns, Annals 
               of Combin., 6 (2002), 65-76.
%D A005773 J. Nemecek and M. Klazar, A bijection between nonnegative words and sparse 
               abba-free partitions, Discr. Math., 265 (2003), 411-416.
%D A005773 R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see 
               Problem 6.46a.
%H A005773 T. D. Noe, <a href="b005773.txt">Table of n, a(n) for n=0..200</a>
%H A005773 H. Bottomley, <a href="a001006.2.gif">Illustration of initial terms</
               a>
%H A005773 M. Bousquet-M\'{e}lou, <a href="http://www.labri.fr/Perso/~bousquet/Articles/
               Diriges/ani.ps.gz">New enumerative results on two-dimensional directed 
               animals</a>
%H A005773 E. Deutsch and B. E. Sagan, <a href="http://arxiv.org/pdf/math.CO/0407326">
               Congruences for Catalan and Motzkin numbers and related sequences</
               a>, J. Num. Theory 117 (2006), 191-215.
%H A005773 J. W. Layman, <a href="http://www.cs.uwaterloo.ca/journals/JIS/index.html">
               The Hankel Transform and Some of its Properties</a>, J. Integer Sequences, 
               4 (2001), #01.1.5.
%H A005773 T. Mansour, <a href="http://arXiv.org/abs/math.CO/0110039">Restricted 
               1-3-2 permutations and generalized patterns</a>.
%H A005773 P. Peart and W.-J. Woan, <a href="http://www.cs.uwaterloo.ca/journals/
               JIS/index.html">Generating Functions via Hankel and Stieltjes Matrices</
               a>, J. Integer Seqs., Vol. 3 (2000), #00.2.1.
%H A005773 P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/
               Publications/books.html">Analytic Combinatorics</a>, 2009; see page 
               81
%F A005773 G.f.: 2x/(3x-1+sqrt(1-2x-3x^2)) - Len Smiley (smiley(AT)math.uaa.alaska.edu).
%F A005773 Also a(0)=1, a(n) = M(n) + Sum {M(k)*a(n-k-1), k=0..n-1}, where M(n) 
               are the Motzkin numbers (A001006).
%F A005773 na(n)=2na(n-1)+3(n-2)a(n-2), a(0)=a(1)=1. - Michael Somos, Feb 02, 2002.
%F A005773 G.f.: (1/2)((1+x)/(1-3x))^(1/2) + 1/2 . Related to Motzkin numbers A001006 
               by a(n+1, 0) = 3 a(n) - A001006(n).
%F A005773 a(n)=sum(binomial(q, floor(q/2))binomial(n-1, q), q=0..n) for n>0 - Emeric 
               Deutsch (deutsch(AT)duke.poly.edu), Aug 15 2002
%F A005773 a(n+1)=sum{k=0..n, (-1)^(n+k)C(n, k)C(2k+1, k+1)}; a(n)=0^n+sum{k=0..n-1, 
               (-1)^(n+k-1)C(n-1, k)C(2k+1, k+1)}. - Paul Barry (pbarry(AT)wit.ie), 
               Jun 22 2004
%F A005773 a(n+1)=sum{k=0..n, (-1)^k*3^(n-k)*binomial(n, k)A000108(k)} - Paul Barry 
               (pbarry(AT)wit.ie), Jan 27 2005
%F A005773 Starting (1, 2, 5, 13,...) gives binomial transform of A001405 and inverse 
               binomial transform of A001700. - Gary W. Adamson (qntmpkt(AT)yahoo.com), 
               Aug 31 2007
%F A005773 Starting (1, 2, 5, 13, 35, 96,...) gives row sums of triangle A132814. 
               - Gary W. Adamson (qntmpkt(AT)yahoo.com), Aug 31 2007
%F A005773 Contribution from Paul Barry (pbarry(AT)wit.ie), Jan 19 2009: (Start)
%F A005773 G.f.: 1/(1-x/(1-x-x^2/(1-x-x^2/(1-x-x^2/(1-x-x^2/(1-x-x^2/(1-... (continued 
               fraction).
%F A005773 G.f.: 1+x/(1-2x-x^2/(1-x-x^2/(1-x-x^2/(1-x-x^2/(1-.... (continued fraction). 
               (End)
%F A005773 Formula from Thomas Wieder (wieder.thomas(AT)t-online.de), Feb 25 2009:
%F A005773 a(n) = sum_{l_1=0}^{n+1} sum_{l_2=0}^{n}...sum_{l_i=0}^{n-i}...sum_{l_n=0}^{1}
%F A005773 delta(l_1,l_2,...,l_i,...,l_n)
%F A005773 where delta(l_1,l_2,...,l_i,...,l_n) = 0 if any (l_i - l_(i+1))^2 >= 
               2 for i=1.. n-1
%F A005773 and delta(l_1,l_2,...,l_i,...,l_n) = 1 otherwise.
%F A005773 INVERT transform of offset Motzkin numbers (A001006): (a(n))_{n>=1}=(1,
               1,2,4,9,21,...). [From David Callan (callan(AT)stat.wisc.edu), Aug 
               27 2009]
%p A005773 seq( sum('binomial(i-1,k)*binomial(i-k,k)', 'k'=0..floor(i/2)), i=0..30 
               ); # Detlef Pauly (dettodet(AT)yahoo.de), Nov 09 2001
%p A005773 Contribution from Thomas Wieder (thomas.wieder(AT)t-online.de), Feb 22 
               2009: (Start)
%p A005773 A005773:=proc(n::integer)
%p A005773 local i,j,A,istart,iend,KartProd,Liste,Term,delta;
%p A005773 A:=0;
%p A005773 for i from 0 to n do
%p A005773 Liste[i]:=NULL;
%p A005773 istart[i]:=0;
%p A005773 iend[i]:=n-i+1:
%p A005773 for j from istart[i] to iend[i] do
%p A005773 Liste[i]:=Liste[i],j;
%p A005773 end do;
%p A005773 Liste[i]:=[Liste[i]]:
%p A005773 end do;
%p A005773 KartProd:=cartprod([seq(Liste[i],i=1..n)]);
%p A005773 while not KartProd[finished] do
%p A005773 Term:=KartProd[nextvalue]();
%p A005773 delta:=1;
%p A005773 for i from 1 to n-1 do
%p A005773 if (op(i,Term) - op(i+1,Term))^2 >= 2 then
%p A005773 delta:=0;
%p A005773 break;
%p A005773 end if;
%p A005773 end do;
%p A005773 A:=A+delta;
%p A005773 end do;
%p A005773 end proc;
%p A005773 (End)
%o A005773 (PARI) a(n)=if(n<2,n>=0,(2*n*a(n-1)+3*(n-2)*a(n-2))/n)
%Y A005773 See also A005775. Inverse of A001006. Also sum of numbers in row n+1 
               of array T in A026300. Leading column of array in A038622.
%Y A005773 The right edge of the triangle A062105.
%Y A005773 Interpolates between Motzkin numbers (A001006) and Catalan numbers (A000108). 
               Cf. A054391, A054392, A054393, A055898.
%Y A005773 Except for the first term a(0), sequence is the binomial transform of 
               A001405.
%Y A005773 a(n) = A002426(n-1)+A005717(n-1) if n>0. - Emeric Deutsch (deutsch(AT)duke.poly.edu), 
               Aug 14 2002
%Y A005773 Cf. A001405, A001700, A132814.
%Y A005773 Cf. A136787.
%Y A005773 A158973 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Mar 26 2009]
%Y A005773 Sequence in context: A000107 A063028 A085810 this_sequence A022855 A091190 
               A007689
%Y A005773 Adjacent sequences: A005770 A005771 A005772 this_sequence A005774 A005775 
               A005776
%K A005773 nonn,easy,nice
%O A005773 0,3
%A A005773 N. J. A. Sloane (njas(AT)research.att.com), Simon Plouffe, Clark Kimberling 
               (ck6(AT)evansville.edu)
%E A005773 More terms from David W. Wilson (davidwwilson(AT)comcast.net)