|
%I M1443 #444 Jan 26 2024 10:18:51
%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,1405155255055,4142457992363
%N Number of directed animals of size n (or directed n-ominoes in standard position).
%C This sequence, with first term a(0) deleted, appears to be determined by the conditions that the diagonal and first superdiagonal of U are {1,1,1,1,...} and {2,3,4,5,...,n+1,...} respectively, where A=LU is the LU factorization of the 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) is the sum of the (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) is the 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 a(n) is also the number of Grand-Dyck paths of semilength n starting with an up-step and avoiding the pattern DUD. - _David Bevan_, Nov 19 2019
%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) is the 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 a(n) is 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 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 a(n) is also the number of n-multisets of [n] in which no integer except n occurs exactly once (e.g., 111, 113, 222, 223, 333 for n=3). - _David Bevan_, Nov 19 2019
%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
%C a(n) is the number of compositions (ordered partitions) of n where there are A001006(k-1) sorts of part k (see formula by Andrew Howroyd, Dec 04 2017). - _Joerg Arndt_, Jan 26 2024
%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.
%D R. P. Stanley, Catalan Numbers, Cambridge, 2015, p. 132.
%H T. D. Noe, <a href="/A005773/b005773.txt">Table of n, a(n) for n = 0..200</a>
%H Kassie Archer and Christina Graves, <a href="https://arxiv.org/abs/2205.09686">A new statistic on Dyck paths for counting 3-dimensional Catalan words</a>, arXiv:2205.09686 [math.CO], 2022.
%H A. Asinowski and 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 Andrei Asinowski, Axel Bacher, Cyril Banderier and Bernhard Gittenberger, <a href="https://lipn.univ-paris13.fr/~banderier/Papers/patterns2019.pdf">Analytic combinatorics of lattice paths with forbidden patterns, the vectorial kernel method, and generating functions for pushdown automata</a>, Laboratoire d'Informatique de Paris Nord (LIPN 2019).
%H Andrei Asinowski, Cyril Banderier and Valerie Roitner, <a href="https://lipn.univ-paris13.fr/~banderier/Papers/several_patterns.pdf">Generating functions for lattice paths with several forbidden patterns</a>, (2019).
%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 and 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 and 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, David Bevan and Sergey Kirgizov, <a href="https://arxiv.org/abs/1906.11870">Bijections between directed animals, multisets and Grand-Dyck paths</a>, arXiv:1906.11870 [math.CO], 2019.
%H Jean-Luc Baril, Rigoberto Flórez, and José L. Ramírez, <a href="http://jl.baril.u-bourgogne.fr/symasympyramid.pdf">Counting symmetric and asymmetric peaks in motzkin paths with air pockets</a>, Univ. Bourgogne (France, 2023).
%H Jean-Luc Baril, Sergey Kirgizov and 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 Paul 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 and 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 Alin 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 Alin Bostan, Andrew Elvey Price, Anthony John Guttmann and Jean-Marie Maillard, <a href="https://arxiv.org/abs/2001.00393">Stieltjes moment sequences for pattern-avoiding permutations</a>, arXiv:2001.00393 [math.CO], 2020.
%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 and Y.-N. Yeh, <a href="https://doi.org/10.37236/4793">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 Hyunsoo Cho, JiSun Huh and Jaebum Sohn, <a href="https://arxiv.org/abs/1904.02313">Counting self-conjugate (s,s+1,s+2)-core partitions</a>, arXiv:1904.02313 [math.CO], 2019.
%H Ji Young Choi, <a href="https://www.emis.de/journals/JIS/VOL22/Choi/choi15.html">Digit Sums Generalizing Binomial Coefficients</a>, J. Int. Seq., Vol. 22 (2019), Article 19.8.3.
%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:1310.2449 [cs.DM], 2013.
%H D. E. Davenport, L. W. Shapiro and L. C. Woodson, <a href="https://doi.org/10.37236/2034">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 and 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 Isaac DeJager, Madeleine Naquin and Frank Seidl, <a href="https://www.valpo.edu/mathematics-statistics/files/2019/08/Drube2019.pdf">Colored Motzkin Paths of Higher Order</a>, VERUM 2019.
%H Emeric 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 Emeric 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 and N. Ham, <a href="http://arxiv.org/abs/1507.04838">Idempotent Statistics of the Motzkin and Jones Monoids</a>, arXiv:1507.04838 [math.CO], 2015.
%H Tomislav Došlic and 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 Juan B. Gil and Luiz E. Lopez, <a href="https://arxiv.org/abs/2203.10589">Enumeration of symmetric arc diagrams</a>, arXiv:2203.10589 [math.CO], 2022.
%H Samuele Giraudo, <a href="https://arxiv.org/abs/1903.00677">Tree series and pattern avoidance in syntax trees</a>, arXiv:1903.00677 [math.CO], 2019.
%H D. Gouyou-Beauchamps and 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 Taras Goy and Mark Shattuck, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL26/Shattuck/sh36.html">Determinants of Some Hessenberg-Toeplitz Matrices with Motzkin Number Entries</a>, J. Int. Seq., Vol. 26 (2023), Article 23.3.4.
%H Petr Gregor, Torsten Mütze, and Namrata, <a href="https://arxiv.org/abs/2306.08420">Combinatorial generation via permutation languages. VI. Binary trees</a>, arXiv:2306.08420 [cs.DM], 2023.
%H Petr Gregor, Torsten Mütze, and Namrata, <a href="https://doi.org/10.4230/LIPIcs.ISAAC.2023.33">Pattern-Avoiding Binary Trees-Generation, Counting, and Bijections</a>, Leibniz Int'l Proc. Informatics (LIPIcs), 34th Int'l Symp. Algor. Comp. (ISAAC 2023). See p. 33.13.
%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 and 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 Nickolas Hein and Jia Huang, <a href="https://arxiv.org/abs/1508.01688">Modular Catalan Numbers</a>, arXiv:1508.01688 [math.CO], 2015-2016. See Table 1.1 p. 2.
%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 and 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 and 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: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 and 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 and R. Yassawi, <a href="http://arxiv.org/abs/1310.8635">Automatic congruences for diagonals of rational functions</a>, 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 Sherry H. F. Yan, Yao Yu and Hao Zhou, <a href="https://arxiv.org/abs/1905.00570">On self-conjugate (s, s+1, .., s+k)-core partitions</a>, arXiv:1905.00570 [math.CO], 2019.
%H D. Yaqubi, M. Farrokhi D.G. and 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) = Sum_{k=0..n-1} M(k)*a(n-k-1), where M(n) are the Motzkin numbers (A001006).
%F D-finite with recurrence 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/2)*((1+x)/(1-3*x))^(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(2*k+1, k+1).
%F a(n) = 0^n + Sum_{k=0..n-1} (-1)^(n+k-1)*C(n-1, k)*C(2*k+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-2*x-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 From _Gary W. Adamson_, Jul 29 2011: (Start)
%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, ... (End)
%F Limit_{n->oo} a(n+1)/a(n) = 3.0 = lim_{n->oo} (1 + 2*cos(Pi/n)). - _Gary W. Adamson_, Feb 10 2012
%F a(n) = A025565(n+1) / 2 for n > 0. - _Reinhard Zumkeller_, Mar 30 2012
%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
%F a(n) = (-1)^(n + 1)*2*JacobiP(n - 1, 3, -n - 1/2, -7)/(n^2 + n). - _Peter Luschny_, May 25 2021
%F a(n+1) = A005043(n) + 2*A005717(n) for n >= 1. - _Peter Bala_, Feb 11 2022
%F a(n) = Sum_{k=0..n-1} A064189(n-1,k) for n>=1. - _Alois P. Heinz_, Aug 29 2022
%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 _Eric Rowland_, Sep 25 2021: (Start)
%e There are a(4) = 13 directed animals of size 4:
%e O
%e O O O OO O O
%e O O OO O OO O OO OOO O O OO O
%e O OO O O OO OOO O O OO OOO OO OOO OOOO
%e (End)
%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 [1,seq(add(add(W(i,j,m),i=0..m),j=0..m),m=0..n-1)] 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_ *)
%t A005773[n_] := 2 (-1)^(n+1) JacobiP[n - 1, 3, -n -1/2, -7] / (n^2 + n); A005773[0] := 1; Table[A005773[n], {n, 0, 27}] (* _Peter Luschny_, May 25 2021 *)
%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 (Haskell)
%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([next(A005773) for _ in range(28)]) # _Peter Luschny_, May 16 2016
%o (Sage) (2*x/(3*x-1+sqrt(1-2*x-3*x^2))).series(x, 30).coefficients(x, sparse=False) # _G. C. Greubel_, Apr 05 2019
%o (Magma) R<x>:=PowerSeriesRing(Rationals(), 30); Coefficients(R!( 2*x/(3*x-1+Sqrt(1-2*x-3*x^2)) )); // _G. C. Greubel_, Apr 05 2019
%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, A245455.
%Y Cf. A005043, A005717, A057682, A064189, A091867.
%K nonn,easy,nice
%O 0,3
%A _N. J. A. Sloane_, _Simon Plouffe_, _Clark Kimberling_
|
