cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

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

Original entry on oeis.org

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

Views

Author

N. J. A. Sloane, Simon Plouffe

Keywords

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

Examples

			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

References

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

Links

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

Programs

  • Haskell
    a002426 n = a027907 n n  -- Reinhard Zumkeller, Jan 22 2013
  • Magma
    P:=PolynomialRing(Integers()); [Max(Coefficients((1+x+x^2)^n)): n in [0..26]]; // Bruno Berselli, Jul 05 2011
  • 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 *)
  • 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 */
  • 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
  • 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
  • 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

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

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.