This site is supported by donations to The OEIS Foundation.

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

%I M1443

%S 1,1,2,5,13,35,96,267,750,2123,6046,17303,49721,143365,414584,1201917,

%T 3492117,10165779,29643870,86574831,253188111,741365049,2173243128,

%U 6377181825,18730782252,55062586341,161995031226,476941691177

%N Number of directed animals of size n (or directed n-ominoes in standard position).

%C 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

%C 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

%C 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

%C 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

%C 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

%C 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

%C 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

%C Equals row sums of triangle A136787 starting (1, 2, 5, 13, 35, ...). - _Gary W. Adamson_, Jan 21 2008

%C 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

%C 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

%C Hankel transform is A010892. - _Paul Barry_, Jan 19 2009

%C Starting (1, 2, 5, 13, ...) = row sums of triangle A158793. - _Gary W. Adamson_, Mar 26 2009

%C 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

%C Inverse binomial transform of A024718. - _Philippe Deléham_, Dec 13 2009

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

%C 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

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

%C a(n) = A025565(n+1) / 2 for n > 0. - _Reinhard Zumkeller_, Mar 30 2012

%C 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

%C 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

%C 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

%C 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

%C 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

%C 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

%C Number of ordered rooted trees with n non-root nodes and all non-root nodes having outdegrees 1 or 2. - _Andrew Howroyd_, Dec 04 2017

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

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

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

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

%H T. D. Noe, <a href="/A005773/b005773.txt">Table of n, a(n) for n = 0..200</a>

%H A. Asinowski, G. Rote, <a href="http://arxiv.org/abs/1502.04925">Point sets with many non-crossing matchings</a>, arXiv preprint arXiv:1502.04925 [cs.CG], 2015.

%H Axel Bacher, <a href="https://arxiv.org/abs/1802.06030">Improving the Florentine algorithms: recovering algorithms for Motzkin and Schröder paths</a>, arXiv:1802.06030 [cs.DS], 2018.

%H C. Banderier, P. Hitczenko, <a href="https://doi.org/10.1016/j.dam.2011.12.011">Enumeration and asymptotics of restricted compositions having the same number of parts</a>, Disc. Appl. Math. 160 (18) (2012) 2542-2554.

%H C. Banderier, C. Krattenthaler, A. Krinik, D. Kruchinin, V. Kruchinin, D. Nguyen, and M. Wallner, <a href="https://arxiv.org/abs/1609.06473">Explicit formulas for enumeration of lattice paths: basketball and the kernel method</a>, arXiv:1609.06473 [math.CO], 2016.

%H E. Barcucci et al., <a href="http://dx.doi.org/10.1016/S0012-365X(99)00254-X">From Motzkin to Catalan Permutations</a>, Discr. Math., 217 (2000), 33-49.

%H Elena Barcucci, Antonio Bernini, Renzo Pinzani, <a href="http://ceur-ws.org/Vol-2113/paper7.pdf">Exhaustive generation of positive lattice paths</a>, Semantic Sensor Networks Workshop 2018, CEUR Workshop Proceedings (2018) Vol. 2113.

%H Jean-Luc Baril, Sergey Kirgizov, Armen Petrossian, <a href="http://jl.baril.u-bourgogne.fr/forest.pdf">Forests and pattern-avoiding permutations modulo pure descents</a>, Permutation Patterns 2017, Reykjavik University, Iceland, June 26-30, 2017.

%H Paul Barry, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL15/Barry4/bern2.html">Riordan-Bernstein Polynomials, Hankel Transforms and Somos Sequences</a>, Journal of Integer Sequences, Vol. 15 2012, #12.8.2.

%H P. Barry, <a href="http://dx.doi.org/10.1016/j.laa.2015.10.032">Riordan arrays, generalized Narayana triangles, and series reversion</a>, Linear Algebra and its Applications, 491 (2016) 343-385.

%H Ange Bigeni, Evgeny Feigin, <a href="https://arxiv.org/abs/1804.10804">Poincaré polynomials of the degenerate flag varieties of type C</a>, arXiv:1804.10804 [math.CO], 2018.

%H A. Bostan, <a href="http://www-apr.lip6.fr/sem-comb-slides/IHP-bostan.pdf">Computer Algebra for Lattice Path Combinatorics</a>, Seminaire de Combinatoire Ph. Flajolet, March 28 2013.

%H Alin Bostan and Manuel Kauers, <a href="https://arxiv.org/abs/0811.2899">Automatic Classification of Restricted Lattice Walks</a>, arXiv:0811.2899 [math.CO], 2009.

%H H. Bottomley, <a href="/A001006/a001006.2.gif">Illustration of initial terms</a>

%H M. Bousquet-Mélou, <a href="http://www.labri.fr/Perso/~bousquet/Articles/Diriges/ani.ps.gz">New enumerative results on two-dimensional directed animals</a>

%H M. Bousquet-Mélou, <a href="http://dx.doi.org/10.1016/S0012-365X(97)00109-X">New enumerative results on two-dimensional directed animals</a>, Discr. Math., 180 (1998), 73-106.

%H Xiang-Ke Chang, X.-B. Hu, H. Lei, Y.-N. Yeh, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i1p8">Combinatorial proofs of addition formulas</a>, The Electronic Journal of Combinatorics, 23(1) (2016), #P1.8.

%H Gi-Sang Cheon, Hana Kim and Louis W. Shapiro, <a href="http://dx.doi.org/10.1016/j.disc.2012.03.023">Combinatorics of Riordan arrays with identical A and Z sequences</a>, Discrete Math., 312 (2012), 2040-2049.

%H R. De Castro, A. L. Ramírez and J. L. Ramírez, <a href="http://arxiv.org/abs/1310.2449">Applications in Enumerative Combinatorics of Infinite Weighted Automata and Graphs</a>, arXiv preprint arXiv:1310.2449 [cs.DM], 2013.

%H D. E. Davenport, L. W. Shapiro and L. C. Woodson, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v18i2p33">The Double Riordan Group</a>, The Electronic Journal of Combinatorics, 18(2) (2012), #P33. - From _N. J. A. Sloane_, May 11 2012

%H Patrick Dehornoy, Emilie Tesson, <a href="https://arxiv.org/abs/1803.02639">Garside combinatorics for Thompson's monoid F+ and a hybrid with the braid monoid B_oo+</a>, arXiv:1803.02639 [math.GR], 2018.

%H E. Deutsch and B. E. Sagan, <a href="https://arxiv.org/abs/math/0407326">Congruences for Catalan and Motzkin numbers and related sequences</a>, arXiv:math/0407326 [math.CO], 2004.

%H E. Deutsch and B. E. Sagan, <a href="https://doi.org/10.1016/j.jnt.2005.06.005">Congruences for Catalan and Motzkin numbers and related sequences</a>, J. Num. Theory 117 (2006), 191-215.

%H D. Dhar et al., <a href="http://dx.doi.org/10.1088/0305-4470/15/6/006">Enumeration of directed site animals on two-dimensional lattices</a>, J. Phys. A 15 (1982), L279-L284.

%H I. Dolinka, J. East, A. Evangelou, D. FitzGerald, N. Ham, <a href="http://arxiv.org/abs/1507.04838">Idempotent Statistics of the Motzkin and Jones Monoids</a>, arXiv preprint arXiv:1507.04838 [math.CO], 2015.

%H Tomislav Došlic, Darko Veljan, <a href="http://dx.doi.org/10.1016/j.disc.2007.04.066">Logarithmic behavior of some combinatorial sequences</a>, Discrete Math. 308 (2008), no. 11, 2182--2212. MR2404544 (2009j:05019) - From _N. J. A. Sloane_, May 01 2012

%H P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/books.html">Analytic Combinatorics</a>, 2009; see page 81.

%H D. Gouyou-Beauchamps, G. Viennot, <a href="http://dx.doi.org/10.1016/0196-8858(88)90017-6">Equivalence of the two-dimensional directed animal problem to a one-dimensional path problem</a>, Adv. in Appl. Math. 9 (1988), no. 3, 334-357.

%H T. Halverson and M. Reeks, <a href="http://arxiv.org/abs/1302.6150">Gelfand Models for Diagram Algebras</a>, arXiv preprint arXiv:1302.6150 [math.RT], 2013.

%H Nickolas Hein, Jia Huang, <a href="https://arxiv.org/abs/1807.04623">Variations of the Catalan numbers from some nonassociative binary operations</a>, arXiv:1807.04623 [math.CO], 2018.

%H Aoife Hennessy, <a href="http://repository.wit.ie/1693/1/AoifeThesis.pdf">A Study of Riordan Arrays with Applications to Continued Fractions, Orthogonal Polynomials and Lattice Paths</a>, Ph. D. Thesis, Waterford Institute of Technology, Oct. 2011

%H V. Jelinek, T. Mansour, M. Shattuck, <a href="http://dx.doi.org/10.1016/j.aam.2012.09.002">On multiple pattern avoiding set partitions</a>, Adv. Appl. Math. 50 (2) (2013) 292-326, Theorem 4.2.

%H Christian Krattenthaler, Daniel Yaqubi, <a href="https://arxiv.org/abs/1802.05990">Some determinants of path generating functions, II</a>, Adv. Appl. Math. 101 (2018), 232-265.

%H J. W. Layman, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL4/LAYMAN/hankel.html">The Hankel Transform and Some of its Properties</a>, J. Integer Sequences, 4 (2001), #01.1.5.

%H T. Mansour, <a href="https://arxiv.org/abs/math/0110039">Restricted 1-3-2 permutations and generalized patterns</a>, arXiv:math/0110039 [math.CO], 2001.

%H T. Mansour, <a href="http://dx.doi.org/10.1007/s00026-002-8031-2">Restricted 1-3-2 permutations and generalized patterns</a>, Annals of Combin., 6 (2002), 65-76.

%H T. Mansour and M. Shattuck, <a href="http://www.mat.unisi.it/newsito/puma/public_html/22_2/mansour_shattuck.pdf">Restricted partitions and generalized Catalan numbers</a>, PU. M. A., Vol. (2011), No. 2, pp. 239-251. - From _N. J. A. Sloane_, Oct 13 2012

%H T. Mansour, M. Shattuck and D. G. L. Wang, <a href="http://arxiv.org/abs/1307.3637">Counting subwords in flattened permutations</a>, arXiv preprint arXiv:1307.3637 [math.CO], 2013.

%H Toufik Mansour, Mark Shattuck, and Stephen Wagner, <a href="http://dx.doi.org/10.1016/j.disc.2015.04.023">Counting subwords in flattened permutations</a>, Discrete Math., 338 (2015), pp. 1989-2005.

%H Jan Němeček and Martin Klazar, <a href="http://dx.doi.org/10.1016/S0012-365X(02)00885-3">A bijection between nonnegative words and sparse abba-free partitions</a>, Discr. Math., 265 (2003), 411-416.

%H D. I. Panyushev, <a href="http://arxiv.org/abs/math/0311347">Ideals of Heisenberg type and minimax elements of affine Weyl groups</a>, arXiv:math/0311347 [math.RT], Lie Groups and Invariant Theory, Amer. Math. Soc. Translations, Series 2, Volume 213, (2005), ed. E. Vinberg.

%H P. Peart and W.-J. Woan, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL3/PEART/peart1.html">Generating Functions via Hankel and Stieltjes Matrices</a>, J. Integer Seqs., Vol. 3 (2000), #00.2.1.

%H L. Pudwell, <a href="http://faculty.valpo.edu/lpudwell/slides/notredame.pdf"> Pattern avoidance in trees (slides from a talk, mentions many sequences)</a>, 2012. - From _N. J. A. Sloane_, Jan 03 2013

%H M. Qin, E. Yaakobi, P. H. Siegel, <a href="http://dx.doi.org/10.1109/JSAC.2014.140504">Constrained Codes that Mitigate Inter-Cell Interference in Read/Write Cycles for Flash Memories</a>, IEEE Jnl. Selected Areas in Communications, 2014. See Eq. (1). - _N. J. A. Sloane_, Jul 16 2014

%H E. Rowland, R. Yassawi, <a href="http://arxiv.org/abs/1310.8635">Automatic congruences for diagonals of rational functions</a>, arXiv preprint arXiv:1310.8635 [math.NT], 2013.

%H A. Sapounakis, I. Tasoulas and P. Tsikouras, <a href="http://dx.doi.org/10.1016/j.disc.2007.03.005">Counting strings in Dyck paths</a>, Discrete Math., 307 (2007), 2909-2924.

%H Mark Shattuck, <a href="http://www.ams.org/amsmtgs/2227_abstracts/1115-05-211.pdf">Pattern Avoiding Set Partitions and Sequence A005773</a>, Talk given at AMS Regional Meeting, Rutgers University, Nov 15 2015; Abstract 1115-05-211.

%H P. O. Vontobel, <a href="http://dx.doi.org/10.1109/ISIT.2014.6875105">Counting balanced sequences w/o forbidden patterns via the Bethe approximation and loop calculus</a>, Information Theory (ISIT), 2014 IEEE International Symposium on, June 29 2014-July 4 2014 Page(s): 1608-1612.

%H D. Yaqubi, M. Farrokhi D.G., H. Gahsemian Zoeram, <a href="https://arxiv.org/abs/1612.08697">Lattice paths inside a table. I</a>, arXiv:1612.08697 [math.CO], 2016-2017.

%F G.f.: 2*x/(3*x-1+sqrt(1-2*x-3*x^2)). - _Len Smiley_

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

%F n*a(n) = 2*n*a(n-1) + 3*(n-2)*a(n-2), a(0)=a(1)=1. - _Michael Somos_, Feb 02 2002

%F G.f.: (1/2)((1+x)/(1-3x))^(1/2) + 1/2. Related to Motzkin numbers A001006 by a(n+1) = 3*a(n) - A001006(n-1) [see Yaqubi Lemma 2.6].

%F a(n) = Sum_{q=0..n} binomial(q, floor(q/2))*binomial(n-1, q) for n>0. - _Emeric Deutsch_, Aug 15 2002

%F From _Paul Barry_, Jun 22 2004: (Start)

%F a(n+1) = Sum_{k=0..n} (-1)^(n+k)C(n, k)C(2k+1, k+1).

%F a(n) = 0^n + Sum_{k=0..n-1} (-1)^(n+k-1)C(n-1, k)C(2k+1, k+1). (End)

%F a(n+1) = Sum_{k=0..n} (-1)^k*3^(n-k)*binomial(n, k)*A000108(k). - _Paul Barry_, Jan 27 2005

%F Starting (1, 2, 5, 13, ...) gives binomial transform of A001405 and inverse binomial transform of A001700. - _Gary W. Adamson_, Aug 31 2007

%F Starting (1, 2, 5, 13, 35, 96, ...) gives row sums of triangle A132814. - _Gary W. Adamson_, Aug 31 2007

%F 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

%F 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

%F 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

%F INVERT transform of offset Motzkin numbers (A001006): (a(n))_{n>=1}=(1,1,2,4,9,21,...). - _David Callan_, Aug 27 2009

%F A005773(n) = ((n+3)*A001006(n+1) + (n-3)*A001006(n)) * (n+2)/(18*n) for n > 0. - _Mark van Hoeij_, Jul 02 2010

%F 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

%F 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

%F 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

%F 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:

%F 1, 1, 0, 0, 0, 0, ...

%F 1, 1, 1, 0, 0, 0, ...

%F 1, 1, 0, 1, 0, 0, ...

%F 1, 1, 1, 0, 1, 0, ...

%F 1, 1, 1, 1, 0, 1, ...

%F 1, 1, 1, 1, 1, 0, ...

%F ... - _Gary W. Adamson_, Jul 29 2011

%F 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

%F 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

%F a(n) ~ 3^(n-1/2)/sqrt(Pi*n). - _Vaclav Kotesovec_, Jul 30 2013

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

%F a(n) = GegenbauerC(n-2,-n+1,-1/2) + GegenbauerC(n-1,-n+1,-1/2) for n>=1. - _Peter Luschny_, May 12 2016

%F 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

%F G.f.: 1/(1-x*G(x)) where G(x) is g.f. of A001006. - _Andrew Howroyd_, Dec 04 2017

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

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

%e From _Joerg Arndt_, Nov 10 2012: (Start)

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

%e [ 1] [ . . . . ]

%e [ 2] [ . . . 1 ]

%e [ 3] [ . . 1 . ]

%e [ 4] [ . . 1 1 ]

%e [ 5] [ . . 1 2 ]

%e [ 6] [ . 1 . . ]

%e [ 7] [ . 1 . 1 ]

%e [ 8] [ . 1 1 . ]

%e [ 9] [ . 1 1 1 ]

%e [10] [ . 1 1 2 ]

%e [11] [ . 1 2 1 ]

%e [12] [ . 1 2 2 ]

%e [13] [ . 1 2 3 ]

%e (End)

%e From _Joerg Arndt_, Nov 22 2012: (Start)

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

%e [ 1] [ 2 2 . . ]

%e [ 2] [ 2 1 1 . ]

%e [ 3] [ 1 2 1 . ]

%e [ 4] [ 2 . 2 . ]

%e [ 5] [ 1 1 2 . ]

%e [ 6] [ 2 1 . 1 ]

%e [ 7] [ 1 2 . 1 ]

%e [ 8] [ 2 . 1 1 ]

%e [ 9] [ 1 1 1 1 ]

%e [10] [ 1 . 2 1 ]

%e [11] [ 2 . . 2 ]

%e [12] [ 1 1 . 2 ]

%e [13] [ 1 . 1 2 ]

%e (End)

%p 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:=proc(n::integer)

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

%p A:=0;

%p for i from 0 to n do

%p Liste[i]:=NULL;

%p istart[i]:=0;

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

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

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

%p end do;

%p Liste[i]:=[Liste[i]]:

%p end do;

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

%p while not KartProd[finished] do

%p Term:=KartProd[nextvalue]();

%p delta:=1;

%p for i from 1 to n-1 do

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

%p delta:=0;

%p break;

%p end if;

%p end do;

%p A:=A+delta;

%p end do;

%p end proc; # _Thomas Wieder_, Feb 22 2009:

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

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

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

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

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

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

%p A005773_list(27); # _Peter Luschny_, May 21 2011

%p A005773 := proc(n)

%p option remember;

%p if n <= 1 then

%p 1 ;

%p else

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

%p %/n ;

%p end if;

%p end proc:

%p seq(A005773(n),n=0..10) ; # _R. J. Mathar_, Jul 25 2017

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

%t 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_ *)

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

%o (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

%o (PARI) Vec(1/(1-serreverse(x*(1-x)/(1-x^3) + O(x*x^25)))) \\ _Andrew Howroyd_, Dec 04 2017

%o a005773 n = a005773_list !! n

%o a005773_list = 1 : f a001006_list [] where

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

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

%o -- _Reinhard Zumkeller_, Mar 30 2012

%o (Sage)

%o def da():

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

%o yield 1

%o yield 1

%o while True:

%o yield b + (-1)^n*d

%o n += 1

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

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

%o A005773 = da()

%o print([A005773.next() for _ in range(28)]) # _Peter Luschny_, May 16 2016

%Y 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 The right edge of the triangle A062105.

%Y Column k=3 of A295679.

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

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

%Y a(n) = A002426(n-1) + A005717(n-1) if n>0. - _Emeric Deutsch_, Aug 14 2002

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

%Y Cf. A005043, A057682, A091867.

%K nonn,easy,nice

%O 0,3

%A _N. J. A. Sloane_, _Simon Plouffe_, _Clark Kimberling_

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

Last modified November 17 00:14 EST 2018. Contains 317275 sequences. (Running on oeis4.)