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, 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, palindromic Motzkin paths of length 2n-2 or 2n-1). 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 S. Egge, 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. - 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

The shifted, signed array belongs to an interpolated family of arrays associated to the Catalan A000108 (t=1), and Riordan, or Motzkin sums A005043 (t=0), with the interpolating (here t=-2) o.g.f. G(x,t) = (1-sqrt(1-4x/(1+(1-t)x)))/2 and inverse o.g.f. Ginv(x,t) = x(1-x)/(1+(t-1)x(1-x)) (A057682). See A091867 for more info on this family. - Tom Copeland, Nov 09 2014

Alternatively, this sequence corresponds to the number of positive walks with n steps {-1,0,1} starting at the origin, ending at any altitude, and staying strictly above the x-axis. - David Nguyen, Dec 01 2016

Let N be a squarefree number with n prime factors: p_1 < p_2 < ... < p_n. Let D be its set of divisors, E the subset of D X D made of the (d_1, d_2) for which, provided that we know which p_i are in d_1, which p_i are in d_2, d_1 <= d_2 is provable without needing to know the numerical values of the p_i. It appears that a(n+1) is the number of (d_1, d_2) in E such that d_1 and d_2 are coprime. - Luc Rousseau, Aug 21 2017

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

T. Mansour, Combinatorics of Set Partitions, Discrete Mathematics and Its Applications, CRC Press, 2013, p. 377.

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.

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

A. Asinowski, G. Rote, Point sets with many non-crossing matchings, arXiv preprint arXiv:1502.04925 [cs.CG], 2015.

C. Banderier, C. Krattenthaler, A. Krinik, D. Kruchinin, V. Kruchinin, D. Nguyen, and M. Wallner, Explicit formulas for enumeration of lattice paths: basketball and the kernel method, arXiv:1609.06473 [math.CO], 2016.

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

Paul Barry, Riordan-Bernstein Polynomials, Hankel Transforms and Somos Sequences, Journal of Integer Sequences, Vol. 15 2012, #12.8.2.

P. Barry, Riordan arrays, generalized Narayana triangles, and series reversion, Linear Algebra and its Applications, 491 (2016) 343-385.

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

Alin Bostan and Manuel Kauers, Automatic Classification of Restricted Lattice Walks, arXiv:0811.2899 [math.CO], 2009.

H. Bottomley, Illustration of initial terms

M. Bousquet-Mélou, New enumerative results on two-dimensional directed animals

M. Bousquet-Mélou, New enumerative results on two-dimensional directed animals, Discr. Math., 180 (1998), 73-106.

Xiang-Ke Chang, X.-B. Hu, H. Lei, Y.-N. Yeh, Combinatorial proofs of addition formulas, The Electronic Journal of Combinatorics, 23(1) (2016), #P1.8.

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.

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 [cs.DM], 2013.

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 .

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

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

I. Dolinka, J. East, A. Evangelou, D. FitzGerald, N. Ham, Idempotent Statistics of the Motzkin and Jones Monoids, arXiv preprint arXiv:1507.04838 [math.CO], 2015.

Tomislav Došlic, Darko Veljan, 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

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

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.

T. Halverson and M. Reeks, Gelfand Models for Diagram Algebras, arXiv preprint arXiv:1302.6150 [math.RT], 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

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

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, arXiv:math/0110039 [math.CO], 2001.

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

T. Mansour and M. Shattuck, Restricted partitions and generalized Catalan numbers, PU. M. A., Vol. (2011), No. 2, pp. 239-251. - From N. J. A. Sloane, Oct 13 2012

T. Mansour, M. Shattuck and D. G. L. Wang, Counting subwords in flattened permutations, arXiv preprint arXiv:1307.3637 [math.CO], 2013.

Toufik Mansour, Mark Shattuck, and Stephen Wagner, Counting subwords in flattened permutations, Discrete Math., 338 (2015), pp. 1989-2005.

Jan Němeček and Martin Klazar, A bijection between nonnegative words and sparse abba-free partitions, Discr. Math., 265 (2003), 411-416.

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

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

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

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

Mark Shattuck, Pattern Avoiding Set Partitions and Sequence A005773, Talk given at AMS Regional Meeting, Rutgers University, Nov 15 2015; Abstract 1115-05-211.

P. O. Vontobel, Counting balanced sequences w/o forbidden patterns via the Bethe approximation and loop calculus, Information Theory (ISIT), 2014 IEEE International Symposium on, June 29 2014-July 4 2014 Page(s): 1608-1612.

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

Also a(0)=1, a(n) = M(n) + Sum_{k=0..n-1} M(k)*a(n-k-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_{q=0..n} binomial(q, floor(q/2))*binomial(n-1, q) for n>0. - Emeric Deutsch, Aug 15 2002

From Paul Barry, Jun 22 2004: (Start)

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

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

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). - Paul Barry, Jan 19 2009

G.f.: 1+x/(1-2x-x^2/(1-x-x^2/(1-x-x^2/(1-x-x^2/(1-.... (continued fraction). - Paul Barry, Jan 19 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. - Thomas Wieder, Feb 25 2009

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. - Mark van Hoeij, Jul 02 2010

a(n) = Sum_{k=1..n} (k/n * Sum_{j=0..n} binomial(n,j)*binomial(j,2*j-n-k)). - Vladimir Kruchinin, Sep 06 2010

a(0) = 1; a(n+1) = Sum_{t=0..n} n!/((n-t)!*ceiling(t/2)!*floor(t/2)!. - 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

For n>0, a(n) = (-1)^(n+1) * hypergeom([3/2, 1-n], [2], 4). - Vladimir Reshetnikov, Apr 25 2016

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

0 = a(n)*(+9*a(n+1) + 18*a(n+2) - 9*a(n+3)) + a(n+1)*(-6*a(n+1) + 7*a(n+2) - 2*a(n+3)) + a(n+2)*(-2*a(n+2) + a(n+3)) for n>=0. - Michael Somos, Dec 01 2016

G.f. = 1 + x + 2*x^2 + 5*x^3 + 13*x^4 + 35*x^5 + 96*x^6 + 267*x^7 + ...

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)

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

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; # Thomas Wieder, Feb 22 2009:

# 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

A005773 := proc(n)

    option remember;

    if n <= 1 then

        1 ;

    else

        2*n*procname(n-1)+3*(n-2)*procname(n-2) ;

        %/n ;

    end if;

end proc:

seq(A005773(n), n=0..10) ; # R. J. Mathar, Jul 25 2017

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

a[0]=1; a[n_] := Sum[k/n*Sum[Binomial[n, j]*Binomial[j, 2*j-n-k], {j, 0, n}], {k, 1, n}]; Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Mar 31 2015, after Vladimir Kruchinin *)

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

(PARI) for(n=0, 27, print1(if(n==0, 1, sum(k=0, n-1, (-1)^(n - 1 + k)*binomial(n - 1, k)*binomial(2*k + 1, k + 1))), ", ")) \\ Indranil Ghosh, Mar 14 2017

(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

(Sage)

def da():

    a, b, c, d, n = 0, 1, 1, -1, 1

    yield 1

    yield 1

    while True:

        yield b + (-1)^n*d

        n += 1

        a, b = b, (3*(n-1)*n*a+(2*n-1)*n*b)/((n+1)*(n-1))

        c, d = d, (3*(n-1)*c-(2*n-1)*d)/n

A005773 = da()

print([A005773.next() for _ in range(28)]) # Peter Luschny, May 16 2016

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.

Cf. A005043, A057682, A091867.

Sequence in context: A063028 A085810 A235611 * A022855 A091190 A264228

Adjacent sequences:  A005770 A005771 A005772 * A005774 A005775 A005776

nonn,easy,nice

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

More terms from David W. Wilson

approved