login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual Appeal: Please make a donation (tax deductible in USA) to keep the OEIS running. Over 5000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A002426 Central trinomial coefficients: largest coefficient of (1 + x + x^2)^n.
(Formerly M2673 N1070)
208
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 (list; graph; refs; listen; history; text; internal format)
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)=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) = 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

a(n) = A111808(n,n). - Reinhard Zumkeller, Aug 17 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

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

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.

LINKS

T. D. Noe and Seiichi Manyama, Table of n, a(n) for n = 0..1000 (first 201 terms from T. D. Noe)

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.

Paul Barry, A Catalan Transform and Related Transformations on Integer Sequences, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.5.

P. Barry, Continued fractions and transformations of integer sequences, JIS 12 (2009) 09.7.6

F. R. Bernhart, Catalan, Motzkin and Riordan numbers, Discr. Math., 204 (1999) 73-112.

J. Cigler, Some nice Hankel determinants. arXiv preprint arXiv:1109.1449 [math.CO], 2011.

E. Deutsch and B. E. Sagan, Congruences for Catalan and Motzkin numbers and related sequences, 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. - From N. J. A. Sloane, Oct 03 2012

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

R. K. Guy, The Second Strong Law of Small Numbers, Math. Mag, 63 (1990) 3-20, esp. 18-19.

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, Y.-N. Yeh, Congruences of Finite Summations of the Coefficients in certain Generating Functions, The Electronic Journal of Combinatorics, 21 (2014), #P2.45.

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.

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.

J. W. Layman, The Hankel Transform and Some of its Properties, J. Integer Sequences, 4 (2001), #01.1.5.

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

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, 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, 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, J. Stat. Phys. 135 (2009) 279-373, arXiv:0711.1738 [cond-mat.stat-mech]. Mentions this sequence. - N. J. A. Sloane, Mar 14 2014

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, 2012. - From 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.

Eric Weisstein's World of Mathematics, Central Trinomial Coefficient

Eric Weisstein's World of Mathematics, 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

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... - Vaclav Kotesovec, Sep 18 2014

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, C(n, k)C(k, k/2)(1+(-1)^k)/2}; a(n)=sum{k=0..n, (-1)^(n-k)C(n, k)C(2k, k) }. - Paul Barry, Jul 01 2003

a(n) = Sum{k>=0, C(n, 2*k)*C(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) is asymptotic to d*3^n/sqrt(n) with d=sqrt(3/Pi)/2=.488602512... - Alec Mihailovs (alec(AT)mihailovs.com), Feb 24 2005

a(n) = sum{k=0..n, C(n, k)C(k, n-k)}. - Paul Barry, Apr 23 2005

a(n) = (-1/4)^n*Sum_{k, 0<=k<=n} = binomial(2k, k)*binomial(2n-2k, n-k)*(-3)^k. - Philippe Deléham, Aug 17 2005

a(n) = sum{k=0..n, ((1+(-1)^k)/2)*sum{i=0..floor((n-k)/2), C(n, i)C(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(2j,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*C(n,j)*C(2n-2j,n)}=(3/2)^n*sum{j=0..n,(1/3)^j*C(n,j)*C(2j,n)}; follows from (c) in A027907. - Loic Turban (turban(AT)lpm.u-nancy.fr), Aug 31 2006

a(n) = (1/Pi)*int(x^n/sqrt((3-x)(1+x)),x,-1,3) 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*hypergeom([1/2, n+1],[1],4/3). - Mark van Hoeij, Nov 12 2009

a(n) = (1/Pi)*int((1+2*x)^n/sqrt(1-x^2),x,-1,1) = (1/Pi)*int((1+2*cos(t))^n,t,0,Pi). - 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(2n-3k-1, n-3k)*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

EXAMPLE

For n=2, (x^2 + x + 1)^2 = x^4 + 2x^3 + 3x^2 + 2x + 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 *)

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

(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([A002426.next() for _ in range(30)]) # Peter Luschny, May 16 2016

CROSSREFS

INVERT transform of A002426 is A007971. Main column of A027907.

Cf. A082758, A152227, A102445, A113302, A113303, A113304, A113305 (divisibility of central trinomial coefficients), A097893 (partial sums), A001006.

See also A002878, A277640.

Sequence in context: A018031 A052948 A026325 * A011769 A087432 A135052

Adjacent sequences:  A002423 A002424 A002425 * A002427 A002428 A002429

KEYWORD

nonn,nice,core,easy,changed

AUTHOR

N. J. A. Sloane, Simon Plouffe

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy .

Last modified December 9 00:45 EST 2016. Contains 278959 sequences.