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

 

Logo

Invitation: celebrating 50 years of OEIS, 250000 sequences, and Sloane's 75th, there will be a conference at DIMACS, Rutgers, Oct 9-10 2014.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A005773 Number of directed animals of size n (or directed n-ominoes in standard position).
(Formerly M1443)
60
1, 1, 2, 5, 13, 35, 96, 267, 750, 2123, 6046, 17303, 49721, 143365, 414584, 1201917, 3492117, 10165779, 29643870, 86574831, 253188111, 741365049, 2173243128, 6377181825, 18730782252, 55062586341, 161995031226, 476941691177 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

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, Jul 21 2000

Also the number of base 3 n-digit numbers (not starting with 0) with digit sum n. For the analogous sequence in base 10 see A071976, see example. - John W. Layman, 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, 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, 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, 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, Aug 18 2004

Hankel transform of a(n+1) = [1,2,5,13,35,96,...]gives A000012 = [1,1,1,1,1,1,...] . - Philippe Deléham, Oct 24 2007

Equals row sums of triangle A136787 starting (1, 2, 5, 13, 35,...). - Gary W. Adamson, 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, Jul 22 2008

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. - Eric Egge (eegge(AT)carleton.edu), Oct 21 2008

Hankel transform is A010892. [Paul Barry, Jan 19 2009]

Starting (1, 2, 5, 13,...) = row sums of triangle A158793 [Gary W. Adamson, 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 Rowland, Apr 21 2009]

Inverse binomial transform of A024718. [Philippe Deléham, Dec 13 2009]

Let w(i, j, n) denote walks in N^2 which satisfy the multivariate recurrence

w(i, j, n) = w(i - 1, j, n - 1) + w(i, j - 1, n - 1) + w(i + 1, j - 1,n - 1) with boundary conditions w(0,0,0) = 1 and w(i,j,n) = 0 if i or j or n is < 0. Let alpha(n) the number of such walks of length n, alpha(n) = Sum{i = 0..n, j=0..n} w(i, j, n). Then a(n+1) = alpha(n). - Peter Luschny, May 21 2011

a(n+1)/a(n) tends to 3.0 = lim_{N->inf}(1 + 2*Cos(Pi/N)). - Gary W. Adamson, Feb 10 2012

a(n) = A025565(n+1) / 2 for n > 0. [Reinhard Zumkeller, Mar 30 2012]

Number of length-n strings [d(0),d(1),d(2),...,d(n-1)] where 0<=d(k)<=k and abs(d(k)-d(k-1)) <= 1 (smooth factorial numbers, see example). [Joerg Arndt, Nov 10 2012]

a(n) is the number of n-multisets of {1,...,n} containing no pair of consecutive integers (e.g. 111, 113, 133, 222, 333 for n=3). [David Bevan, Jun 10 2013]

Number of minimax elements in the affine Weyl group of the Lie algebra so(2n+1) or the Lie algebra sp(2n). See Panyushev 2005. Cf. A245455. - Peter Bala, Jul 22 2014

REFERENCES

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

P. Barry, Riordan-Bernstein Polynomials, Hankel Transforms and Somos Sequences, Journal of Integer Sequences, Vol. 15 2012, #12.8.2. - From N. J. A. Sloane, Dec 29 2012

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

Gi-Sang Cheon, Hana Kim and Louis W. Shapiro, Combinatorics of Riordan arrays with identical A and Z sequences, Discrete Math., 312 (2012), 2040-2049.

D. E. Davenport, L. W. Shapiro and L. C. Woodson, The Double Riordan Group, The Electronic Journal of Combinatorics, 18(2) (2012), #P33. - From N. J. A. Sloane, May 11 2012

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

Doslic, Tomislav and Veljan, Darko. Logarithmic behavior of some combinatorial sequences. Discrete Math. 308 (2008), no. 11, 2182--2212. MR2404544 (2009j:05019) - From N. J. A. Sloane, May 01 2012

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 and M. Shattuck, Restricted partitions and generalized Catalan numbers, PU. M. A., Vol. (2011), No. 2, pp. 239-251; http://www.mat.unisi.it/newsito/puma/public_html/22_2/mansour_shattuck.pdf. - From N. J. A. Sloane, Oct 13 2012

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.

M. Qin, E. Yaakobi, P. H. Siegel, Constrained Codes that Mitigate Inter-Cell Interference in Read/Write Cycles for Flash Memories, IEEE Jnl. Selected Areas in Communications, 2014. See Eq. (1). - N. J. A. Sloane, Jul 16 2014

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

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

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

LINKS

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

A. Bostan, Computer Algebra for Lattice Path Combinatorics, Seminaire de Combinatoire Ph. Flajolet, March 28 2013.

H. Bottomley, Illustration of initial terms

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

R. De Castro, A. L. Ramírez and J. L. Ramírez, Applications in Enumerative Combinatorics of Infinite Weighted Automata and Graphs, arXiv preprint arXiv:1310.2449, 2013

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

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

T. Halverson and M. Reeks, Gelfand Models for Diagram Algebras, arXiv preprint arXiv:1302.6150, 2013

Aoife Hennessy, A Study of Riordan Arrays with Applications to Continued Fractions, Orthogonal Polynomials and Lattice Paths, Ph. D. Thesis, Waterford Institute of Technology, Oct. 2011

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.

V. Jelinek, T. Mansour, M. Shattuck, On multiple pattern avoiding set partitions, Adv. Appl. Math. 50 (2) (2013) 292-326, Theorem 4.2

D. I. Panyushev, Ideals of Heisenberg type and minimax elements of affine Weyl groups, arXiv:math/0311347 [math.RT], Lie Groups and Invariant Theory, Amer. Math. Soc. Translations, Series 2, Volume 213, (2005), ed. E. Vinberg

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

L. Pudwell, Pattern avoidance in trees (slides from a talk, mentions many sequences), 2012. - From N. J. A. Sloane, Jan 03 2013

E. Rowland, R. Yassawi, Automatic congruences for diagonals of rational functions, arXiv preprint arXiv:1310.8635, 2013

FORMULA

G.f.: 2*x/(3*x-1+sqrt(1-2*x-3*x^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).

n*a(n) = 2*n*a(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, 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, Jun 22 2004

a(n+1)=sum{k=0..n, (-1)^k*3^(n-k)*binomial(n, k)A000108(k)} - Paul Barry, Jan 27 2005

Starting (1, 2, 5, 13,...) gives binomial transform of A001405 and inverse binomial transform of A001700. - Gary W. Adamson, Aug 31 2007

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

From Paul Barry, 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)

From Thomas Wieder, Feb 25 2009: (Start)

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

INVERT transform of offset Motzkin numbers (A001006): (a(n))_{n>=1}=(1,1,2,4,9,21,...). [David Callan, Aug 27 2009]

A005773(n) = ((n+3)*A001006(n+1) + (n-3)*A001006(n)) * (n+2)/(18*n) for n > 0. [From Mark van Hoeij, Jul 02 2010]

a(n)=sum(k/n*sum(binomial(n,j)*binomial(j,2*j-n-k),j,0,n),k,1,n); [Vladimir Kruchinin, Sep 06 2010]

a(0) = 1; a(n+1)=sum((n!)/((n-t)!*ceil(t/2)!*floor(t/2)!),t,0,n); [Andrew S. Hays, Feb 02 2011]

a(n) = leftmost column term of M^n*V, where M = an infinite quadradiagonal matrix with all 1's in the main, super and subdiagonals, [1,0,0,0,...] in the diagonal starting at position (2,0); and rest zeros. V = vector [1,0,0,0,...]. - Gary W. Adamson, Jun 16 2011

a(n) = upper left term of M^n, a(n+1) = sum of top row terms of M^n; M = an infinite square production matrix in which the main diagonal is (1,1,0,0,0,...) as follows:

1, 1, 0, 0, 0, 0,...

1, 1, 1, 0, 0, 0,...

1, 1, 0, 1, 0, 0,...

1, 1, 1, 0, 1, 0,...

1, 1, 1, 1, 0, 1,...

1, 1, 1, 1, 1, 0,...

... - Gary W. Adamson, Jul 29, 2011

With first term deleted: E.g.f.: a(n) = n! * [x^n] exp(x)*(BesselI(0, 2*x) + BesselI(1, 2*x)). - Peter Luschny, Aug 25 2012

G.f.: G(0)/2 + 1/2, where G(k)= 1 + 2*x*(4*k+1)/( (2*k+1)*(1+x) - x*(1+x)*(2*k+1)*(4*k+3)/(x*(4*k+3) + (1+x)*(k+1)/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, Jun 24 2013

a(n) ~ 3^(n-1/2)/sqrt(Pi*n). - Vaclav Kotesovec, Jul 30 2013

EXAMPLE

a(3) = 5, a(4) = 13; since the top row of M^3 = (5, 5, 2, 1,...)

From Joerg Arndt, Nov 10 2012: (Start)

There are a(4)=13 smooth factorial numbers of length 4 (dots for zeros):

[ 1]   [ . . . . ]

[ 2]   [ . . . 1 ]

[ 3]   [ . . 1 . ]

[ 4]   [ . . 1 1 ]

[ 5]   [ . . 1 2 ]

[ 6]   [ . 1 . . ]

[ 7]   [ . 1 . 1 ]

[ 8]   [ . 1 1 . ]

[ 9]   [ . 1 1 1 ]

[10]   [ . 1 1 2 ]

[11]   [ . 1 2 1 ]

[12]   [ . 1 2 2 ]

[13]   [ . 1 2 3 ]

(End)

From Joerg Arndt, Nov 22 2012: (Start)

There are a(4)=13 base 3 4-digit numbers (not starting with 0) with digit sum 4:

[ 1]   [ 2 2 . . ]

[ 2]   [ 2 1 1 . ]

[ 3]   [ 1 2 1 . ]

[ 4]   [ 2 . 2 . ]

[ 5]   [ 1 1 2 . ]

[ 6]   [ 2 1 . 1 ]

[ 7]   [ 1 2 . 1 ]

[ 8]   [ 2 . 1 1 ]

[ 9]   [ 1 1 1 1 ]

[10]   [ 1 . 2 1 ]

[11]   [ 2 . . 2 ]

[12]   [ 1 1 . 2 ]

[13]   [ 1 . 1 2 ]

(End)

MAPLE

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

# From Thomas Wieder, 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)

# n -> [a(0), a(1), .., a(n)]

A005773_list := proc(n) local W, m, j, i;

W := proc(i, j, n) option remember;

if min(i, j, n) < 0 or max(i, j) > n then 0

elif n = 0 then if i = 0 and j = 0 then 1 else 0 fi

else W(i-1, j, n-1)+W(i, j-1, n-1)+W(i+1, j-1, n-1) fi end:

[1, seq(add(add(W(i, j, m), i=0..m), j=0..m), m=0..n-1)] end:

A005773_list(27); # Peter Luschny, May 21 2011

MATHEMATICA

CoefficientList[Series[(2x)/(3x-1+Sqrt[1-2x-3x^2]), {x, 0, 40}], x]  (* Harvey P. Dale, Apr 03 2011 *)

PROG

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

(Haskell)

a005773 n = a005773_list !! n

a005773_list = 1 : f a001006_list [] where

   f (x:xs) ys = y : f xs (y : ys) where

     y = x + sum (zipWith (*) a001006_list ys)

-- Reinhard Zumkeller, Mar 30 2012

CROSSREFS

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, Aug 14 2002

Cf. A001405, A001700, A132814, A136787, A158973, A245455.

Sequence in context: A063028 A085810 A235611 * A022855 A091190 A007689

Adjacent sequences:  A005770 A005771 A005772 * A005774 A005775 A005776

KEYWORD

nonn,easy,nice,changed

AUTHOR

N. J. A. Sloane , Simon Plouffe, Clark Kimberling

EXTENSIONS

More terms from David W. Wilson

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified August 1 19:36 EDT 2014. Contains 245137 sequences.