A245455 -id:A245455 - cp's OEIS frontend

A002426 Central trinomial coefficients: largest coefficient of (1 + x + x^2)^n.

1, 1, 3, 7, 19, 51, 141, 393, 1107, 3139, 8953, 25653, 73789, 212941, 616227, 1787607, 5196627, 15134931, 44152809, 128996853, 377379369, 1105350729, 3241135527, 9513228123, 27948336381, 82176836301, 241813226151, 712070156203, 2098240353907, 6186675630819

Offset: 0

N. J. A. Sloane, Simon Plouffe

Number of ordered trees with n + 1 edges, having root of odd degree and nonroot nodes of outdegree at most 2. - Emeric Deutsch, Aug 02 2002
Number of paths of length n with steps U = (1,1), D = (1,-1) and H = (1,0), running from (0,0) to (n,0) (i.e., grand Motzkin paths of length n). For example, a(3) = 7 because we have HHH, HUD, HDU, UDH, DUH, UHD and DHU. - Emeric Deutsch, May 31 2003
Number of lattice paths from (0,0) to (n,n) using steps (2,0), (0,2), (1,1). It appears that 1/sqrt((1 - x)^2 - 4*x^s) is the g.f. for lattice paths from (0,0) to (n,n) using steps (s,0), (0,s), (1,1). - Joerg Arndt, Jul 01 2011
Number of lattice paths from (0,0) to (n,n) using steps (1,0), (1,1), (1,2). - Joerg Arndt, Jul 05 2011
Binomial transform of A000984, with interpolated zeros. - Paul Barry, Jul 01 2003
Number of leaves in all 0-1-2 trees with n edges, n > 0. (A 0-1-2 tree is an ordered tree in which every vertex has at most two children.) - Emeric Deutsch, Nov 30 2003
a(n) is the number of UDU-free paths of n + 1 upsteps (U) and n downsteps (D) that start U. For example, a(2) = 3 counts UUUDD, UUDDU, UDDUU. - David Callan, Aug 18 2004
Diagonal sums of triangle A063007. - Paul Barry, Aug 31 2004
Number of ordered ballots from n voters that result in an equal number of votes for candidates A and B in a three candidate election. Ties are counted even when candidates A and B lose the election. For example, a(3) = 7 because ballots of the form (voter-1 choice, voter-2 choice, voter-3 choice) that result in equal votes for candidates A and B are the following: (A,B,C), (A,C,B), (B,A,C), (B,C,A), (C,A,B), (C,B,A) and (C,C,C). - Dennis P. Walsh, Oct 08 2004
a(n) is the number of weakly increasing sequences (a_1,a_2,...,a_n) with each a_i in [n]={1,2,...,n} and no element of [n] occurring more than twice. For n = 3, the sequences are 112, 113, 122, 123, 133, 223, 233. - David Callan, Oct 24 2004
Note that n divides a(n+1) - a(n). In fact, (a(n+1) - a(n))/n = A007971(n+1). - T. D. Noe, Mar 16 2005
Row sums of triangle A105868. - Paul Barry, Apr 23 2005
Number of paths of length n with steps U = (1,1), D = (1,-1) and H = (1,0), starting at (0,0), staying weakly above the x-axis (i.e., left factors of Motzkin paths) and having no H steps on the x-axis. Example: a(3) = 7 because we have UDU, UHD, UHH, UHU, UUD, UUH and UUU. - Emeric Deutsch, Oct 07 2007
Equals right border of triangle A152227; starting with offset 1, the row sums of triangle A152227. - Gary W. Adamson, Nov 29 2008
Starting with offset 1 = iterates of M * [1,1,1,...] where M = a tridiagonal matrix with [0,1,1,1,...] in the main diagonal and [1,1,1,...] in the super and subdiagonals. - Gary W. Adamson, Jan 07 2009
Hankel transform is 2^n. - Paul Barry, Aug 05 2009
a(n) is prime for n = 2, 3 and 4, with no others for n <= 10^5 (E. W. Weisstein, Mar 14 2005). It has apparently not been proved that no [other] prime central trinomials exist. - Jonathan Vos Post, Mar 19 2010
a(n) is not divisible by 3 for n whose base-3 representation contains no 2 (A005836).
a(n) = number of (n-1)-lettered words in the alphabet {1,2,3} with as many occurrences of the substring (consecutive subword) [1,2] as those of [2,1]. See the papers by Ekhad-Zeilberger and Zeilberger. - N. J. A. Sloane, Jul 05 2012
a(n) = coefficient of x^n in (1 + x + x^2)^n. - L. Edson Jeffery, Mar 23 2013
a(n) is the number of ordered pairs (A,B) of subsets of {1,2,...,n} such that (i.) A and B are disjoint and (ii.) A and B contain the same number of elements. For example, a(2) = 3 because we have: ({},{}) ; ({1},{2}) ; ({2},{1}). - Geoffrey Critzer, Sep 04 2013
Also central terms of A082601. - Reinhard Zumkeller, Apr 13 2014
a(n) is the number of n-tuples with entries 0, 1, or 2 and with the sum of entries equal to n. For n=3, the seven 3-tuples are (1,1,1), (0,1,2), (0,2,1), (1,0,2), (1,2,0), (2,0,1), and (2,1,0). - Dennis P. Walsh, May 08 2015
The series 2*a(n) + 3*a(n+1) + a(n+2) = 2*A245455(n+3) has Hankel transform of L(2n+1)*2^n, offset n = 1, L being a Lucas number, see A002878 (empirical observation). - Tony Foster III, Sep 05 2016
The series (2*a(n) + 3*a(n+1) + a(n+2))/2 = A245455(n+3) has Hankel transform of L(2n+1), offset n=1, L being a Lucas number, see A002878 (empirical observation). - Tony Foster III, Sep 05 2016
Conjecture: An integer n > 3 is prime if and only if a(n) == 1 (mod n^2). We have verified this for n up to 8*10^5, and proved that a(p) == 1 (mod p^2) for any prime p > 3 (cf. A277640). - Zhi-Wei Sun, Nov 30 2016
This is the analog for Coxeter type B of Motzkin numbers (A001006) for Coxeter type A. - F. Chapoton, Jul 19 2017
a(n) is also the number of solutions to the equation x(1) + x(2) + ... + x(n) = 0, where x(1), ..., x(n) are in the set {-1,0,1}. Indeed, the terms in (1 + x + x^2)^n that produce x^n are of the form x^i(1)*x^i(2)*...*x^i(n) where i(1), i(2), ..., i(n) are in {0,1,2} and i(1) + i(2) + ... + i(n) = n. By setting j(t) = i(t) - 1 we obtain that j(1), ..., j(n) satisfy j(1) + ... + j(n) =0 and j(t) in {-1,0,1} for all t = 1..n. - Lucien Haddad, Mar 10 2018
If n is a prime greater than 3 then a(n)-1 is divisible by n^2. - Ira M. Gessel, Aug 08 2021
Let f(m) = ceiling((q+log(q))/log(9)), where q = -log(log(27)/(2*m^2*Pi)) then f(a(n)) = n, for n > 0. - Miko Labalan, Oct 07 2024
Diagonal of the rational function 1 / (1 - x^2 - y^2 - x*y). - Ilya Gutkovskiy, Apr 23 2025

			For n = 2, (x^2 + x + 1)^2 = x^4 + 2*x^3 + 3*x^2 + 2*x + 1, so a(2) = 3. - _Michael B. Porter_, Sep 06 2016

L. Comtet, Advanced Combinatorics, Reidel, 1974, pp. 78 and 163, #19.
L. Euler, Exemplum Memorabile Inductionis Fallacis, Opera Omnia. Teubner, Leipzig, 1911, Series (1), Vol. 15, p. 59.
R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 575.
P. Henrici, Applied and Computational Complex Analysis. Wiley, NY, 3 vols., 1974-1986. (Vol. 1, p. 42.)
Shara Lalo and Zagros Lalo, Polynomial Expansion Theorems and Number Triangles, Zana Publishing, 2018, ISBN: 978-1-9995914-0-3, pp. 579.
J. Riordan, Combinatorial Identities, Wiley, 1968, p. 74.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
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 Example 6.3.8.
James J. Tattersall, Elementary Number Theory in Nine Chapters, Cambridge University Press, 1999, page 22.
Lin Yang and S.-L. Yang, The parametric Pascal rhombus. Fib. Q., 57:4 (2019), 337-346. See p. 341.

Seiichi Manyama, Table of n, a(n) for n = 0..1000 (first 201 terms from T. D. Noe)
Katharine A. Ahrens, Combinatorial Applications of the k-Fibonacci Numbers: A Cryptographically Motivated Analysis, Ph. D. thesis, North Carolina State University (2020).
George E. Andrews, Three aspects of partitions, Séminaire Lotharingien de Combinatoire, B25f (1990), 1 p.
George E. Andrews, Euler's 'exemplum memorabile inductionis fallacis' and q-trinomial coefficients, J. Amer. Math. Soc. 3 (1990) 653-669.
Armen G. Bagdasaryan and Ovidiu Bagdasar, On some results concerning generalized arithmetic triangles, Electronic Notes in Discrete Mathematics (2018) Vol. 67, 71-77.
E. Barcucci, R. Pinzani and R. Sprugnoli, The Motzkin family, P.U.M.A. Ser. A, Vol. 2, 1991, No. 3-4, pp. 249-279.
Paul Barry, A Catalan Transform and Related Transformations on Integer Sequences, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.5.
Paul Barry, Continued fractions and transformations of integer sequences, JIS 12 (2009) 09.7.6.
Paul Barry, Jacobsthal Decompositions of Pascal's Triangle, Ternary Trees, and Alternating Sign Matrices, Journal of Integer Sequences, 19, 2016, #16.3.5.
Paul Barry, On the Central Antecedents of Integer (and Other) Sequences, J. Int. Seq., Vol. 23 (2020), Article 20.8.3.
Frank R. Bernhart, Catalan, Motzkin and Riordan numbers, Discr. Math., 204 (1999) 73-112.
N. M. Bogoliubov, Enumerative combinatorics of XX0 Heisenberg chain, Scientific Notes, POMI Workshops, Russian Academy of Sciences (St. Petersburg, Russia, 2019), Vol. 487.
Jan Bok, Graph-indexed random walks on special classes of graphs, arXiv:1801.05498 [math.CO], 2018.
Johann Cigler, Some nice Hankel determinants. arXiv preprint arXiv:1109.1449 [math.CO], 2011.
Johann Cigler and Christian Krattenthaler, Hankel determinants of linear combinations of moments of orthogonal polynomials, arXiv:2003.01676 [math.CO], 2020.
Isaac DeJager, Madeleine Naquin and Frank Seidl, Colored Motzkin Paths of Higher Order, VERUM 2019.
Emeric Deutsch and B. E. Sagan, Congruences for Catalan and Motzkin numbers and related sequences, arXiv:math/0407326 [math.CO], 2004; J. Num. Theory 117 (2006), 191-215.
Steffen Eger, Restricted Weighted Integer Compositions and Extended Binomial Coefficients, J. Integer. Seq., Vol. 16 (2013), #13.1.3. - From _N. J. A. Sloane_, Feb 03 2013
Steffen Eger, Stirling's Approximation for Central Extended Binomial Coefficients, American Mathematical Monthly, 121 (2014), 344-349.
Shalosh B. Ekhad and Doron Zeilberger, Automatic Solution of Richard Stanley's Amer. Math. Monthly Problem #11610 and ANY Problem of That Type, arXiv preprint arXiv:1112.6207 [math.CO], 2011.
Luca Ferrari and Emanuele Munarini, Enumeration of edges in some lattices of paths, arXiv preprint arXiv:1203.6792 [math.CO], 2012 and J. Int. Seq. 17 (2014) #14.1.5
Francesc Fite, Kiran S. Kedlaya, Victor Rotger and Andrew V. Sutherland, Sato-Tate distributions and Galois endomorphism modules in genus 2, arXiv preprint arXiv:1110.6638 [math.NT], 2011.
Francesc Fite and Andrew V. Sutherland, Sato-Tate distributions of twists of y^2=x^5-x and y^2=x^6+1, arXiv preprint arXiv:1203.1476 [math.NT], 2012. - From _N. J. A. Sloane_, Sep 14 2012
Rigoberto Flórez, Leandro Junes and José L. Ramírez, Further Results on Paths in an n-Dimensional Cubic Lattice, Journal of Integer Sequences, Vol. 21 (2018), Article 18.1.2.
R. K. Guy, editor, Western Number Theory Problems, 1985-12-21 & 23, Typescript, Jul 13 1986, Dept. of Math. and Stat., Univ. Calgary, 11 pages. Annotated scan of pages 1, 3, 7, 9, with permission. See Problem 85:03.
R. K. Guy, Letter to N. J. A. Sloane, 1987
R. K. Guy, The Second Strong Law of Small Numbers, Math. Mag, 63 (1990) 3-20, esp. 18-19.
R. K. Guy, The Second Strong Law of Small Numbers, Math. Mag, 63 (1990), no. 1, 3-20. [Annotated scanned copy]
V. E. Hoggatt, Jr. and M. Bicknell, Diagonal sums of generalized Pascal triangles, Fib. Quart., 7 (1969), 341-358, 393.
Po-Yi Huang, Shu-Chung Liu, and Yeong-Nan Yeh, Congruences of Finite Summations of the Coefficients in certain Generating Functions, The Electronic Journal of Combinatorics, 21 (2014), #P2.45.
Cynthia Huffman, Analytical Observations (Translation of E326), Euleriana (2023) Vol. 3, Issue 1.
Anders Hyllengren, Four integer sequences, Oct 04 1985. Observes essentially that A000984 and A002426 are inverse binomial transforms of each other, as are A000108 and A001006.
Veronika Irvine, Stephen Melczer and Frank Ruskey, Vertically constrained Motzkin-like paths inspired by bobbin lace, arXiv:1804.08725 [math.CO], 2018.
L. Kleinrock, Uniform permutation of sequences, JPL Space Programs Summary, Vol. 37-64-III, Apr 30, 1970, pp. 32-43. [Annotated scanned copy]
Nadav Kohen, Density and Symmetry in the Generalized Motzkin Numbers mod p, arXiv:2411.03681 [math.CO], 2024. See p. 2.
Dmitry Kruchinin and Vladimir Kruchinin, A Generating Function for the Diagonal T2n,n in Triangles, Journal of Integer Sequence, Vol. 18 (2015), article 15.4.6.
Shara Lalo and Zagros Lalo, Formula for the Central terms in triangle A027907 ((1 + x + x^2)^n).
John W. Layman, The Hankel Transform and Some of its Properties, J. Integer Sequences, 4 (2001), #01.1.5.
Andrew Lohr, Several Topics in Experimental Mathematics, arXiv:1805.00076 [math.CO], 2018.
Toufik Mansour and Mark Shattuck, Enumeration of Catalan and smooth words according to capacity, Integers (2025) Vol. 25, Art. No. A5. See pp. 28, 32.
Romeo Meštrović, Lucas' theorem: its generalizations, extensions and applications (1878--2014), arXiv preprint arXiv:1409.3820 [math.NT], 2014.
Thorsten Neuschel, A Note on Extended Binomial Coefficients, J. Int. Seq. 17 (2014) # 14.10.4.
Tony D. Noe, On the Divisibility of Generalized Central Trinomial Coefficients, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.7.
Paul Peart and Wen-Jin Woan, Generating Functions via Hankel and Stieltjes Matrices, J. Integer Seqs., Vol. 3 (2000), #00.2.1.
Ed. Pegg, Jr., Number of combinations of n coins when have 3 kinds of coin
E. Pergola, R. Pinzani, S. Rinaldi and R. A. Sulanke, A bijective approach to the area of generalized Motzkin paths, Adv. Appl. Math., 28, 2002, 580-591.
José L. Ramírez, The Pascal Rhombus and the Generalized Grand Motzkin Paths, arXiv:1511.04577 [math.CO], 2015.
José L. Ramírez and Víctor F. Sirvent, A Generalization of the k-Bonacci Sequence from Riordan Arrays, The Electronic Journal of Combinatorics, 22(1) (2015), #P1.38.
Dan Romik, Some formulas for the central trinomial and Motzkin numbers, J. Integer Seqs., Vol. 6, 2003.
Eric Rowland and Reem Yassawi, Automatic congruences for diagonals of rational functions, arXiv preprint arXiv:1310.8635 [math.NT], 2013.
Michelle Rudolph-Lilith and Lyle E. Muller, On an explicit representation of central (2k+1)-nomial coefficients, arXiv preprint arXiv:1403.5942 [math.CO], 2014.
Michelle Rudolph-Lilith and Lyle E. Muller, On a link between Dirichlet kernels and central multinomial coefficients, Discrete Mathematics, Volume 338, Issue 9, Sep 06 2015, Pages 1567-1572.
Jesus Salas and Alan D. Sokal, Transfer Matrices and Partition-Function Zeros for Antiferromagnetic Potts Models. V. Further Results for the Square-Lattice Chromatic Polynomial, arXiv:0711.1738 [cond-mat.stat-mech], 2007-2009; J. Stat. Phys. 135 (2009) 279-373, arXiv:0711.1738 [cond-mat.stat-mech]. Mentions this sequence.
Louis W. Shapiro, Seyoum Getu, Wen-Jin Woan, and Leon C. Woodson, The Riordan group, Discrete Applied Math., 34 (1991), 229-239.
T. Sillke, Middle Trinomial Coefficient
Michael Z. Spivey and Laura L. Steil, The k-Binomial Transforms and the Hankel Transform, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.1.
Robert A. Sulanke, Moments of generalized Motzkin paths, J. Integer Sequences, Vol. 3 (2000), #00.1.
Zhi-Wei Sun, Conjectures involving combinatorial sequences, arXiv preprint arXiv:1208.2683 [math.CO], 2012. - _N. J. A. Sloane_, Dec 25 2012
Zhi-Wei Sun, Conjectures involving arithmetical sequences, Number Theory: Arithmetic in Shangri-La (eds., S. Kanemitsu, H.-Z. Li and J.-Y. Liu), Proc. the 6th China-Japan Sem. Number Theory (Shanghai, August 15-17, 2011), World Sci., Singapore, 2013, pp. 244-258. - _N. J. A. Sloane_, Dec 28 2012
Zhi-Wei Sun, On central trinomial coefficients, Question 491563 at MathOverflow, April 23, 2025.
Paveł Szabłowski, Beta distributions whose moment sequences are related to integer sequences listed in the OEIS, Contrib. Disc. Math. (2024) Vol. 19, No. 4, 85-109. See p. 96.
Dennis P. Walsh, The Probability of a Tie in a Three Candidate Election.
Yi Wang and Bao-Xuan Zhu, Proofs of some conjectures on monotonicity of number-theoretic and combinatorial sequences, arXiv preprint arXiv:1303.5595 [math.CO], 2013.
Chenying Wang, Piotr Miska, and István Mező, The r-derangement numbers, Discrete Mathematics 340.7 (2017): 1681-1692.
Chen Wang, Supercongruences and hypergeometric transformations, arXiv:2003.09888 [math.NT], 2020.
Chen Wang and Zhi-Wei Sun, Congruences involving central trinomial coefficients, arXiv:1910.06850 [math.NT], 2019.
Eric Weisstein's World of Mathematics, Central Trinomial Coefficient and Trinomial Coefficient.
Doron Zeilberger, Analogs of the Richard Stanley Amer. Math. Monthly Problem 11610 for ALL pairs of words of length, 2, in an alphabet of, 3 letters. See Proposition 5.
Doron Zeilberger, Analogs of the Richard Stanley Amer. Math. Monthly Problem 11610 for ALL pairs of words of length, 2, in an alphabet of, 3 letters. [Local copy]
Index entries for sequences of k-nomial coefficients
Index entries for "core" sequences

INVERT transform is A007971. Partial sums are A097893. Squares are A168597.
Main column of A027907. Column k=2 of A305161. Column k=0 of A328347. Column 1 of A201552(?).
Cf. A001006, A002878, A005043, A005717, A082758 (bisection), A273055 (bisection), A102445, A113302, A113303, A113304, A113305 (divisibility of central trinomial coefficients), A152227, A277640.

a002426 n = a027907 n n  -- Reinhard Zumkeller, Jan 22 2013

P:=PolynomialRing(Integers()); [Max(Coefficients((1+x+x^2)^n)): n in [0..26]]; // Bruno Berselli, Jul 05 2011

A002426 := proc(n) local k;
    sum(binomial(n, k)*binomial(n-k, k), k=0..floor(n/2));
end proc: # Detlef Pauly (dettodet(AT)yahoo.de), Nov 09 2001
# Alternatively:
a := n -> simplify(GegenbauerC(n,-n,-1/2)):
seq(a(n), n=0..29); # Peter Luschny, May 07 2016

Table[ CoefficientList[ Series[(1 + x + x^2)^n, {x, 0, n}], x][[ -1]], {n, 0, 27}] (* Robert G. Wilson v *)
a=b=1; Join[{a,b}, Table[c=((2n-1)b + 3(n-1)a)/n; a=b; b=c; c, {n,2,100}]]; Table[Sqrt[-3]^n LegendreP[n,1/Sqrt[-3]],{n,0,26}] (* Wouter Meeussen, Feb 16 2013 *)
a[ n_] := If[ n < 0, 0, 3^n Hypergeometric2F1[ 1/2, -n, 1, 4/3]]; (* Michael Somos, Jul 08 2014 *)
Table[4^n *JacobiP[n,-n-1/2,-n-1/2,-1/2], {n,0,29}] (* Peter Luschny, May 13 2016 *)
a[n_] := a[n] = Sum[n!/((n - 2*i)!*(i!)^2), {i, 0, n/2}]; Table[a[n], {n, 0, 29}] (* Shara Lalo and Zagros Lalo, Oct 03 2018 *)

trinomial(n,k):=coeff(expand((1+x+x^2)^n),x,k);
makelist(trinomial(n,n),n,0,12); /* Emanuele Munarini, Mar 15 2011 */

makelist(ultraspherical(n,-n,-1/2),n,0,12); /* Emanuele Munarini, Dec 20 2016 */

{a(n) = if( n<0, 0, polcoeff( (1 + x + x^2)^n, n))};

/* as lattice paths: same as in A092566 but use */
steps=[[2, 0], [0, 2], [1, 1]];
/* Joerg Arndt, Jul 01 2011 */

a(n)=polcoeff(sum(m=0, n, (2*m)!/m!^2 * x^(2*m) / (1-x+x*O(x^n))^(2*m+1)), n) \\ Paul D. Hanna, Sep 21 2013

from math import comb
def A002426(n): return sum(comb(n,k)*comb(k,n-k) for k in range(n+1)) # Chai Wah Wu, Nov 15 2022

A002426 = lambda n: hypergeometric([-n/2, (1-n)/2], [1], 4)
[simplify(A002426(n)) for n in (0..29)]
# Peter Luschny, Sep 17 2014

def A():
    a, b, n = 1, 1, 1
    yield a
    while True:
        yield b
        n += 1
        a, b = b, ((3 * (n - 1)) * a + (2 * n - 1) * b) // n
A002426 = A()
print([next(A002426) for  in range(30)])  # _Peter Luschny, May 16 2016

G.f.: 1/sqrt(1 - 2*x - 3*x^2).
E.g.f.: exp(x)*I_0(2x), where I_0 is a Bessel function. - Michael Somos, Sep 09 2002
a(n) = 2*A027914(n) - 3^n. - Benoit Cloitre, Sep 28 2002
a(n) is asymptotic to d*3^n/sqrt(n) with d around 0.5.. - Benoit Cloitre, Nov 02 2002, d = sqrt(3/Pi)/2 = 0.4886025119... - Alec Mihailovs (alec(AT)mihailovs.com), Feb 24 2005
D-finite with recurrence: a(n) = ((2*n - 1)*a(n-1) + 3*(n - 1)*a(n-2))/n; a(0) = a(1) = 1; see paper by Barcucci, Pinzani and Sprugnoli.
Inverse binomial transform of A000984. - Vladeta Jovovic, Apr 28 2003
a(n) = Sum_{k=0..n} binomial(n, k)*binomial(k, k/2)*(1 + (-1)^k)/2; a(n) = Sum_{k=0..n} (-1)^(n-k)*binomial(n, k)*binomial(2*k, k). - Paul Barry, Jul 01 2003
a(n) = Sum_{k>=0} binomial(n, 2*k)*binomial(2*k, k). - Philippe Deléham, Dec 31 2003
a(n) = Sum_{i+j=n, 0<=j<=i<=n} binomial(n, i)*binomial(i, j). - Benoit Cloitre, Jun 06 2004
a(n) = 3*a(n-1) - 2*A005043(n). - Joost Vermeij (joost_vermeij(AT)hotmail.com), Feb 10 2005
a(n) = Sum_{k=0..n} binomial(n, k)*binomial(k, n-k). - Paul Barry, Apr 23 2005
a(n) = (-1/4)^n*Sum_{k=0..n} binomial(2*k, k)*binomial(2*n-2*k, n-k)*(-3)^k. - Philippe Deléham, Aug 17 2005
a(n) = A111808(n,n). - Reinhard Zumkeller, Aug 17 2005
a(n) = Sum_{k=0..n} (((1 + (-1)^k)/2)*Sum_{i=0..floor((n-k)/2)} binomial(n, i)*binomial(n-i, i+k)*((k + 1)/(i + k + 1))). - Paul Barry, Sep 23 2005
a(n) = 3^n*Sum_{j=0..n} (-1/3)^j*C(n, j)*C(2*j, j); follows from (a) in A027907. - Loic Turban (turban(AT)lpm.u-nancy.fr), Aug 31 2006
a(n) = (1/2)^n*Sum_{j=0..n} 3^j*binomial(n, j)*binomial(2*n-2*j, n) = (3/2)^n*Sum_{j=0..n} (1/3)^j*binomial(n, j)*binomial(2*j, n); follows from (c) in A027907. - Loic Turban (turban(AT)lpm.u-nancy.fr), Aug 31 2006
a(n) = (1/Pi)*Integral_{x=-1..3} x^n/sqrt((3 - x)*(1 + x)) is moment representation. - Paul Barry, Sep 10 2007
G.f.: 1/(1 - x - 2x^2/(1 - x - x^2/(1 - x - x^2/(1 - ... (continued fraction). - Paul Barry, Aug 05 2009
a(n) = sqrt(-1/3)*(-1)^n*hypergeometric([1/2, n+1], [1], 4/3). - Mark van Hoeij, Nov 12 2009
a(n) = (1/Pi)*Integral_{x=-1..1} (1 + 2*x)^n/sqrt(1 - x^2) = (1/Pi)*Integral_{t=0..Pi} (1 + 2*cos(t))^n. - Eli Wolfhagen, Feb 01 2011
In general, g.f.: 1/sqrt(1 - 2*a*x + x^2*(a^2 - 4*b)) = 1/(1 - a*x)*(1 - 2*x^2*b/(G(0)*(a*x - 1) + 2*x^2*b)); G(k) = 1 - a*x - x^2*b/G(k+1); for g.f.: 1/sqrt(1 - 2*x - 3*x^2) = 1/(1 - x)*(1 - 2*x^2/(G(0)*(x - 1) + 2*x^2)); G(k) = 1 - x - x^2/G(k+1), a = 1, b = 1; (continued fraction). - Sergei N. Gladkovskii, Dec 08 2011
a(n) = Sum_{k=0..floor(n/3)} (-1)^k*binomial(2*n-3*k-1, n-3*k)*binomial(n, k). - Gopinath A. R., Feb 10 2012
G.f.: A(x) = x*B'(x)/B(x) where B(x) satisfies B(x) = x*(1 + B(x) + B(x)^2). - Vladimir Kruchinin, Feb 03 2013 (B(x) = x*A001006(x) - Michael Somos, Jul 08 2014)
G.f.: G(0), where G(k) = 1 + x*(2 + 3*x)*(4*k + 1)/(4*k + 2 - x*(2 + 3*x)*(4*k + 2)*(4*k + 3)/(x*(2 + 3*x)*(4*k + 3) + 4*(k + 1)/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, Jun 29 2013
E.g.f.: exp(x) * Sum_{k>=0} (x^k/k!)^2. - Geoffrey Critzer, Sep 04 2013
G.f.: Sum_{n>=0} (2*n)!/n!^2*(x^(2*n)/(1 - x)^(2*n+1)). - Paul D. Hanna, Sep 21 2013
0 = a(n)*(9*a(n+1) + 9*a(n+2) - 6*a(n+3)) + a(n+1)*(3*a(n+1) + 4*a(n+2) - 3*a(n+3)) + a(n+2)*(-a(n+2) + a(n+3)) for all n in Z. - Michael Somos, Jul 08 2014
a(n) = hypergeometric([-n/2, (1-n)/2], [1], 4). - Peter Luschny, Sep 17 2014
a(n) = A132885(n,0), that is, a(n) = A132885(A002620(n+1)). - Altug Alkan, Nov 29 2015
a(n) = GegenbauerC(n,-n,-1/2). - Peter Luschny, May 07 2016
a(n) = 4^n*JacobiP[n,-n-1/2,-n-1/2,-1/2]. - Peter Luschny, May 13 2016
From Alexander Burstein, Oct 03 2017: (Start)
G.f.: A(4*x) = B(-x)*B(3*x), where B(x) is the g.f. of A000984.
G.f.: A(2*x)*A(-2*x) = B(x^2)*B(9*x^2).
G.f.: A(x) = 1 + x*M'(x)/M(x), where M(x) is the g.f. of A001006. (End)
a(n) = Sum_{i=0..n/2} n!/((n - 2*i)!*(i!)^2). [Cf. Lalo and Lalo link. It is Luschny's terminating hypergeometric sum.] - Shara Lalo and Zagros Lalo, Oct 03 2018
From Peter Bala, Feb 07 2022: (Start)
a(n)^2 = Sum_{k = 0..n} (-3)^(n-k)*binomial(2*k,k)^2*binomial(n+k,n-k) and has g.f. Sum_{n >= 0} binomial(2*n,n)^2*x^n/(1 + 3*x)^(2*n+1). Compare with the g.f. for a(n) given above by Hanna.
The Gauss congruences a(n*p^k) == a(n*p^(k-1)) (mod p^k) hold for all prime p and positive integers n and k.
Conjecture: The stronger congruences a(n*p^k) == a(n*p^(k-1)) (mod p^(2*k)) hold for all prime p >= 5 and positive integers n and k. (End)
a(n) = A005043(n) + A005717(n) for n >= 1. - Amiram Eldar, May 17 2024
For even n, a(n) = (n-1)!!* 2^{n/2}/ (n/2)!* 2F1(-n/2,-n/2;1/2;1/4). For odd n, a(n) = n!! *2^(n/2-1/2) / (n/2-1/2)! * 2F1(1/2-n/2,1/2-n/2;3/2;1/4). - R. J. Mathar, Mar 19 2025

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

Original entry on oeis.org

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, 1405155255055, 4142457992363

Offset: 0

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

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

			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 _Eric Rowland_, Sep 25 2021: (Start)
There are a(4) = 13 directed animals of size 4:
  O
  O    O    O    OO              O         O
  O    O    OO   O    OO   O    OO   OOO   O    O    OO    O
  O    OO   O    O    OO   OOO  O    O    OO   OOO  OO   OOO  OOOO
(End)
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)

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.
R. P. Stanley, Catalan Numbers, Cambridge, 2015, p. 132.

T. D. Noe, Table of n, a(n) for n = 0..200
Kassie Archer and Christina Graves, A new statistic on Dyck paths for counting 3-dimensional Catalan words, arXiv:2205.09686 [math.CO], 2022.
Andrei Asinowski and Günter Rote, Point sets with many non-crossing matchings, arXiv preprint arXiv:1502.04925 [cs.CG], 2015.
Andrei Asinowski, Axel Bacher, Cyril Banderier and Bernhard Gittenberger, Analytic combinatorics of lattice paths with forbidden patterns, the vectorial kernel method, and generating functions for pushdown automata, Laboratoire d'Informatique de Paris Nord (LIPN 2019).
Andrei Asinowski, Cyril Banderier and Valerie Roitner, Generating functions for lattice paths with several forbidden patterns, (2019).
Axel Bacher, Improving the Florentine algorithms: recovering algorithms for Motzkin and Schröder paths, arXiv:1802.06030 [cs.DS], 2018.
Cyril Banderier and Paweł Hitczenko, Enumeration and asymptotics of restricted compositions having the same number of parts, Disc. Appl. Math. 160 (18) (2012) 2542-2554.
Cyril Banderier, Christian Krattenthaler, Alan Krinik, Dmitry Kruchinin, Vladimir Kruchinin, David Tuan Nguyen, and Michael Wallner, Explicit formulas for enumeration of lattice paths: basketball and the kernel method, arXiv:1609.06473 [math.CO], 2016.
Elena Barcucci, Alberto Del Lungo, Elisa Pergola, and Renzo Pinzani, From Motzkin to Catalan Permutations, Discr. Math., 217 (2000), 33-49.
Elena Barcucci, Antonio Bernini and Renzo Pinzani, Exhaustive generation of positive lattice paths, Semantic Sensor Networks Workshop 2018, CEUR Workshop Proceedings (2018) Vol. 2113.
Jean-Luc Baril, David Bevan and Sergey Kirgizov, Bijections between directed animals, multisets and Grand-Dyck paths, arXiv:1906.11870 [math.CO], 2019.
Jean-Luc Baril, Rigoberto Flórez, and José L. Ramírez, Counting symmetric and asymmetric peaks in motzkin paths with air pockets, Univ. Bourgogne (France, 2023).
Jean-Luc Baril, Sergey Kirgizov and Armen Petrossian, Forests and pattern-avoiding permutations modulo pure descents, Permutation Patterns 2017, Reykjavik University, Iceland, June 26-30, 2017.
Paul Barry, Riordan-Bernstein Polynomials, Hankel Transforms and Somos Sequences, Journal of Integer Sequences, Vol. 15 2012, #12.8.2.
Paul Barry, Riordan arrays, generalized Narayana triangles, and series reversion, Linear Algebra and its Applications, 491 (2016) 343-385.
Ange Bigeni and Evgeny Feigin, Poincaré polynomials of the degenerate flag varieties of type C, arXiv:1804.10804 [math.CO], 2018.
Alin 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.
Alin Bostan, Andrew Elvey Price, Anthony John Guttmann and Jean-Marie Maillard, Stieltjes moment sequences for pattern-avoiding permutations, arXiv:2001.00393 [math.CO], 2020.
H. Bottomley, Illustration of initial terms
Mireille Bousquet-Mélou, New enumerative results on two-dimensional directed animals
Mireille Bousquet-Mélou, New enumerative results on two-dimensional directed animals, Discr. Math., 180 (1998), 73-106.
Xiang-Ke Chang, Xing-Biao Hu, Hongchuan Lei and Yeong-Nan 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.
Hyunsoo Cho, JiSun Huh and Jaebum Sohn, Counting self-conjugate (s,s+1,s+2)-core partitions, arXiv:1904.02313 [math.CO], 2019.
Ji Young Choi, Digit Sums Generalizing Binomial Coefficients, J. Int. Seq., Vol. 22 (2019), Article 19.8.3.
Rodrigo De Castro, Andrés L. Ramírez, and José L. Ramírez, Applications in Enumerative Combinatorics of Infinite Weighted Automata and Graphs, arXiv:1310.2449 [cs.DM], 2013.
Dennis E. Davenport, Louis W. Shapiro and Leon C. Woodson, The Double Riordan Group, The Electronic Journal of Combinatorics, 18(2) (2012), #P33. - From _N. J. A. Sloane_, May 11 2012
Patrick Dehornoy and Emilie Tesson, Garside combinatorics for Thompson's monoid F+ and a hybrid with the braid monoid B_oo+, arXiv:1803.02639 [math.GR], 2018.
Isaac DeJager, Madeleine Naquin and Frank Seidl, Colored Motzkin Paths of Higher Order, VERUM 2019.
Emeric Deutsch and B. E. Sagan, Congruences for Catalan and Motzkin numbers and related sequences, arXiv:math/0407326 [math.CO], 2004.
Emeric 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.
Igor Dolinka, James East, Athanasios Evangelou, Desmond FitzGerald, Nicholas Ham, James Hyde, Nicholas Loughlin, and James Mitchell, Idempotent Statistics of the Motzkin and Jones Monoids, arXiv:1507.04838 [math.CO], 2015.
Tomislav Došlic and 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.
Juan B. Gil and Luiz E. Lopez, Enumeration of symmetric arc diagrams, arXiv:2203.10589 [math.CO], 2022.
Samuele Giraudo, Tree series and pattern avoidance in syntax trees, arXiv:1903.00677 [math.CO], 2019.
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.
Taras Goy and Mark Shattuck, Determinants of Some Hessenberg-Toeplitz Matrices with Motzkin Number Entries, J. Int. Seq., Vol. 26 (2023), Article 23.3.4.
Petr Gregor, Torsten Mütze, and Namrata, Combinatorial generation via permutation languages. VI. Binary trees, arXiv:2306.08420 [cs.DM], 2023.
Petr Gregor, Torsten Mütze, and Namrata, Pattern-Avoiding Binary Trees-Generation, Counting, and Bijections, Leibniz Int'l Proc. Informatics (LIPIcs), 34th Int'l Symp. Algor. Comp. (ISAAC 2023). See p. 33.13.
Tom Halverson and Mike Reeks, Gelfand Models for Diagram Algebras, arXiv preprint arXiv:1302.6150 [math.RT], 2013.
Nickolas Hein and Jia Huang, Variations of the Catalan numbers from some nonassociative binary operations, arXiv:1807.04623 [math.CO], 2018.
Nickolas Hein and Jia Huang, Modular Catalan Numbers, arXiv:1508.01688 [math.CO], 2015-2016. See Table 1.1 p. 2.
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ít Jelínek, Toufik Mansour, and Mark Shattuck, On multiple pattern avoiding set partitions, Adv. Appl. Math. 50 (2) (2013) 292-326, Theorem 4.2.
Christian Krattenthaler and Daniel Yaqubi, Some determinants of path generating functions, II, Adv. Appl. Math. 101 (2018), 232-265.
J. W. Layman, The Hankel Transform and Some of its Properties, J. Integer Sequences, 4 (2001), #01.1.5.
Toufik Mansour, Restricted 1-3-2 permutations and generalized patterns, arXiv:math/0110039 [math.CO], 2001.
Toufik Mansour, Restricted 1-3-2 permutations and generalized patterns, Annals of Combin., 6 (2002), 65-76.
Toufik Mansour and Mark 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
Toufik Mansour and Mark Shattuck, Avoidance of vincular patterns by Catalan words, arXiv:2405.12435 [math.CO], 2024. See p. 4.
Toufik Mansour and Mark Shattuck, Enumeration of Catalan and smooth words according to capacity, Integers (2025) Vol. 25, Art. No. A5. See p. 3.
Toufik Mansour, Mark Shattuck and David G. L. Wang, Counting subwords in flattened permutations, 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.
Dmitri 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.
Paul Peart and Wen-Jin Woan, Generating Functions via Hankel and Stieltjes Matrices, J. Integer Seqs., Vol. 3 (2000), #00.2.1.
Helmut Prodinger, Cornerless, peakless, valleyless Motzkin paths (regular and skew) and applications to bargraphs, arXiv:2501.13645 [math.CO], 2025. See p. 8.
Lara Pudwell, Pattern avoidance in trees (slides from a talk, mentions many sequences), 2012. - From _N. J. A. Sloane_, Jan 03 2013
Minghai Qin, Eitan Yaakobi, and Paul 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
Eric Rowland and Reem Yassawi, Automatic congruences for diagonals of rational functions, 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.
Mark Shattuck, Subword Patterns in Smooth Words, Enum. Comb. Appl. (2024) Vol. 4, No. 4, Art. No. S2R32. See p. 2.
Paveł Szabłowski, Beta distributions whose moment sequences are related to integer sequences listed in the OEIS, Contrib. Disc. Math. (2024) Vol. 19, No. 4, 85-109. See p. 97.
Pascal 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.
Sherry H. F. Yan, Yao Yu and Hao Zhou, On self-conjugate (s, s+1, .., s+k)-core partitions, arXiv:1905.00570 [math.CO], 2019.
Daniel Yaqubi, Mohammad Farrokhi Derakhshandeh Ghouchan, and Hamed Ghasemian Zoeram, Lattice paths inside a table. I, arXiv:1612.08697 [math.CO], 2016-2017.

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.
Column k=3 of A295679.
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, A245455.
Cf. A005043, A005717, A057682, A064189, A091867.

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

R:=PowerSeriesRing(Rationals(), 30); Coefficients(R!( 2*x/(3*x-1+Sqrt(1-2*x-3*x^2)) )); // G. C. Greubel, Apr 05 2019

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

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

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

Vec(1/(1-serreverse(x*(1-x)/(1-x^3) + O(x*x^25)))) \\ Andrew Howroyd, Dec 04 2017

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([next(A005773) for  in range(28)]) # _Peter Luschny, May 16 2016

(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

G.f.: 2*x/(3*x-1+sqrt(1-2*x-3*x^2)). - Len Smiley
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).
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
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].
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(2*k+1, k+1).
a(n) = 0^n + Sum_{k=0..n-1} (-1)^(n+k-1)*C(n-1, k)*C(2*k+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-2*x-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
From Gary W. Adamson, Jul 29 2011: (Start)
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, ... (End)
Limit_{n->oo} a(n+1)/a(n) = 3.0 = lim_{n->oo} (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
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/(1-x*G(x)) where G(x) is g.f. of A001006. - Andrew Howroyd, Dec 04 2017
a(n) = (-1)^(n + 1)*2*JacobiP(n - 1, 3, -n - 1/2, -7)/(n^2 + n). - Peter Luschny, May 25 2021
a(n+1) = A005043(n) + 2*A005717(n) for n >= 1. - Peter Bala, Feb 11 2022
a(n) = Sum_{k=0..n-1} A064189(n-1,k) for n >= 1. - Alois P. Heinz, Aug 29 2022

cp's OEIS Frontend

A002426 Central trinomial coefficients: largest coefficient of (1 + x + x^2)^n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

Maxima

Maxima

PARI

PARI

PARI

Python

Sage

Sage

Formula

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

PARI

Sage

Sage

Formula