0,3

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

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

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

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

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

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

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

Equals row sums of triangle A136787 starting (1, 2, 5, 13, 35,...). - Gary W. Adamson (qntmpkt(AT)yahoo.com), Jan 21 2008

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

Contribution from Eric Egge (eegge(AT)carleton.edu), Oct 21 2008: (Start)

a(n) is also the number of involutions of length 2n-2 which are

invariant under the reverse-complement map and have no decreasing

subsequences of length 4. (End)

Hankel transform is A010892. [From Paul Barry (pbarry(AT)wit.ie), Jan 19 2009]

Starting (1, 2, 5, 13,...) = row sums of triangle A158793 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Mar 26 2009]

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]

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

A. Sapounakis, I. Tasoulas and P. Tsikouras, Counting strings in Dyck paths, Discrete Math., 307 (2007), 2909-2924.

E. Barcucci et al., From Motzkin to Catalan Permutations, Discr. Math., 217 (2000), 33-49.

M. Bousquet-M\'{e}lou, New enumerative results on two-dimensional directed animals, Discr. Math., 180 (1998), 73-106.

D. Dhar et al., Enumeration of directed site animals on two-dimensional lattices, J. Phys. A 15 (1982), L279-L284.

J. E. Goodman and J. O'Rourke, editors, Handbook of Discrete and Computational Geometry, CRC Press, 1997, p. 237.

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.

T. Mansour, Restricted 1-3-2 permutations and generalized patterns, Annals of Combin., 6 (2002), 65-76.

J. Nemecek and M. Klazar, A bijection between nonnegative words and sparse abba-free partitions, Discr. Math., 265 (2003), 411-416.

R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 6.46a.

T. D. Noe, Table of n, a(n) for n=0..200

H. Bottomley, Illustration of initial terms

M. Bousquet-M\'{e}lou, New enumerative results on two-dimensional directed animals

E. Deutsch and B. E. Sagan, Congruences for Catalan and Motzkin numbers and related sequences, J. Num. Theory 117 (2006), 191-215.

J. W. Layman, The Hankel Transform and Some of its Properties, J. Integer Sequences, 4 (2001), #01.1.5.

T. Mansour, Restricted 1-3-2 permutations and generalized patterns.

P. Peart and W.-J. Woan, Generating Functions via Hankel and Stieltjes Matrices, J. Integer Seqs., Vol. 3 (2000), #00.2.1.

P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 81

G.f.: 2x/(3x-1+sqrt(1-2x-3x^2)) - Len Smiley (smiley(AT)math.uaa.alaska.edu).

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

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

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

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

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

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

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

Starting (1, 2, 5, 13, 35, 96,...) gives row sums of triangle A132814. - Gary W. Adamson (qntmpkt(AT)yahoo.com), Aug 31 2007

Contribution from Paul Barry (pbarry(AT)wit.ie), Jan 19 2009: (Start)

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

G.f.: 1+x/(1-2x-x^2/(1-x-x^2/(1-x-x^2/(1-x-x^2/(1-.... (continued fraction). (End)

Formula from Thomas Wieder (wieder.thomas(AT)t-online.de), Feb 25 2009:

a(n) = sum_{l_1=0}^{n+1} sum_{l_2=0}^{n}...sum_{l_i=0}^{n-i}...sum_{l_n=0}^{1}

delta(l_1,l_2,...,l_i,...,l_n)

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

and delta(l_1,l_2,...,l_i,...,l_n) = 1 otherwise.

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]

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

Contribution from Thomas Wieder (thomas.wieder(AT)t-online.de), Feb 22 2009: (Start)

A005773:=proc(n::integer)

local i, j, A, istart, iend, KartProd, Liste, Term, delta;

A:=0;

for i from 0 to n do

Liste[i]:=NULL;

istart[i]:=0;

iend[i]:=n-i+1:

for j from istart[i] to iend[i] do

Liste[i]:=Liste[i], j;

end do;

Liste[i]:=[Liste[i]]:

end do;

KartProd:=cartprod([seq(Liste[i], i=1..n)]);

while not KartProd[finished] do

Term:=KartProd[nextvalue]();

delta:=1;

for i from 1 to n-1 do

if (op(i, Term) - op(i+1, Term))^2 >= 2 then

delta:=0;

break;

end if;

end do;

A:=A+delta;

end do;

end proc;

(End)

(PARI) a(n)=if(n<2, n>=0, (2*n*a(n-1)+3*(n-2)*a(n-2))/n)

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.

The right edge of the triangle A062105.

Interpolates between Motzkin numbers (A001006) and Catalan numbers (A000108). Cf. A054391, A054392, A054393, A055898.

Except for the first term a(0), sequence is the binomial transform of A001405.

a(n) = A002426(n-1)+A005717(n-1) if n>0. - Emeric Deutsch (deutsch(AT)duke.poly.edu), Aug 14 2002

Cf. A001405, A001700, A132814.

Cf. A136787.

A158973 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Mar 26 2009]

Sequence in context: A000107 A063028 A085810 this_sequence A022855 A091190 A007689

Adjacent sequences: A005770 A005771 A005772 this_sequence A005774 A005775 A005776

nonn,easy,nice

N. J. A. Sloane (njas(AT)research.att.com), Simon Plouffe, Clark Kimberling (ck6(AT)evansville.edu)

More terms from David W. Wilson (davidwwilson(AT)comcast.net)