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

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,3

Comments

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

References

E. Barcucci, R. Pinzani, R. Sprugnoli, The Motzkin family, P.U.M.A. Ser. A, Vol. 2, 1991, No. 3-4, pp. 249-279.

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.

Lin Yang and S.-L. Yang, The parametric Pascal rhombus. Fib. Q., 57:4 (2019), 337-346. See p. 341.

Links

T. D. Noe and 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).

G. E. Andrews, Three aspects of partitions, Séminaire Lotharingien de Combinatoire, B25f (1990), 1 p.

G. 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.

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.

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

J. 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.

E. 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.

S. 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

S. 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.

P.-Y. Huang, S.-C. Liu and Y.-N. 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]

D. Kruchinin and V. 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).

J. 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.

R. Mestrovic, Lucas' theorem: its generalizations, extensions and applications (1878--2014), arXiv preprint arXiv:1409.3820 [math.NT], 2014.

T. 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.

P. Peart and W.-J. 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.

J. L. Ramírez and V. 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.

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

M. Rudolph-Lilith and L. 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.

J. Salas and A. 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.

L. W. Shapiro, S. Getu, W.-J. Woan and L. 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.

R. 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

Z.-W. 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

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.

C.-Y. Wang, P. Miska and I. 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.

D. 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.

D. 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 "core" sequences

Index entries for sequences related to making change.

Formula

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

Recurrence: (n + 2)*a(n+2) - (2*n + 3)*a(n+1) - 3*(n + 1)*a(n) = 0. - Emanuele Munarini, Dec 20 2016

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

Example

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

Maple

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

Mathematica

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

Prog

(PARI) {a(n) = if( n<0, 0, polcoeff( (1 + x + x^2)^n, n))};
(PARI) /* as lattice paths: same as in A092566 but use */
steps=[[2, 0], [0, 2], [1, 1]];
/* Joerg Arndt, Jul 01 2011 */
(PARI) 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
(Maxima) trinomial(n, k):=coeff(expand((1+x+x^2)^n), x, k);
makelist(trinomial(n, n), n, 0, 12); /* Emanuele Munarini, Mar 15 2011 */
(Maxima) makelist(ultraspherical(n, -n, -1/2), n, 0, 12); /* Emanuele Munarini, Dec 20 2016 */
(Magma) P<x>:=PolynomialRing(Integers()); [Max(Coefficients((1+x+x^2)^n)): n in [0..26]]; // Bruno Berselli, Jul 05 2011
(Haskell)
a002426 n = a027907 n n  -- Reinhard Zumkeller, Jan 22 2013
(Sage)
A002426 = lambda n: hypergeometric([-n/2, (1-n)/2], [1], 4)
[simplify(A002426(n)) for n in (0..29)]
# Peter Luschny, Sep 17 2014
(Sage)
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
(Python)
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

Crossrefs

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.

Cf. A001006, A002878, A082758, A102445, A113302, A113303, A113304, A113305 (divisibility of central trinomial coefficients), A152227, A277640.

Sequence in context: A018031 A052948 A026325 * A011769 A087432 A135052

Adjacent sequences: A002423 A002424 A002425 * A002427 A002428 A002429

Keyword

nonn,nice,core,easy

Author

N. J. A. Sloane, Simon Plouffe

Status

approved