A092566 -id:A092566 - 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

A001850 Central Delannoy numbers: a(n) = Sum_{k=0..n} C(n,k)*C(n+k,k).

Original entry on oeis.org

1, 3, 13, 63, 321, 1683, 8989, 48639, 265729, 1462563, 8097453, 45046719, 251595969, 1409933619, 7923848253, 44642381823, 252055236609, 1425834724419, 8079317057869, 45849429914943, 260543813797441, 1482376214227923, 8443414161166173, 48141245001931263

Offset: 0

N. J. A. Sloane

Number of paths from (0,0) to (n,n) in an n X n grid using only steps north, northeast and east (i.e., steps (1,0), (1,1), and (0,1)).
Also the number of ways of aligning two sequences (e.g., of nucleotides or amino acids) of length n, with at most 2*n gaps (-) inserted, so that while unnecessary gappings: - -a a- - are forbidden, both b- and -b are allowed. (If only other of the latter is allowed, then the sequence A000984 gives the number of alignments.) There is an easy bijection from grid walks given by Dickau to such set of alignments (e.g., the straight diagonal corresponds to the perfect alignment with no gaps). - Antti Karttunen, Oct 10 2001
Also main diagonal of array A008288 defined by m(i,1) = m(1,j) = 1, m(i,j) = m(i-1,j-1) + m(i-1,j) + m(i,j-1). - Benoit Cloitre, May 03 2002
So, as a special case of Dmitry Zaitsev's Dec 10 2015 comment on A008288, a(n) is the number of points in Z^n that are L1 (Manhattan) distance <= n from any given point. These terms occur in the crystal ball sequences: a(n) here is the n-th term in the sequence for the n-dimensional cubic lattice. See A008288 for a list of crystal ball sequences (rows or columns of A008288). - Shel Kaphan, Dec 26 2022
a(n) is the number of n-matchings of a comb-like graph with 2*n teeth. Example: a(2) = 13 because the graph consisting of a horizontal path ABCD and the teeth Aa, Bb, Cc, Dd has 13 2-matchings: any of the six possible pairs of teeth and {Aa, BC}, {Aa, CD}, {Bb, CD}, {Cc, AB}, {Dd, AB}, {Dd, BC}, {AB, CD}. - Emeric Deutsch, Jul 02 2002
Number of ordered trees with 2*n+1 edges, having root of odd degree, nonroot nodes of outdegree at most 2 and branches of odd length. - Emeric Deutsch, Aug 02 2002
The sum of the first n coefficients of ((1 - x) / (1 - 2*x))^n is a(n-1). - Michael Somos, Sep 28 2003
Row sums of A063007 and A105870. - Paul Barry, Apr 23 2005
The Hankel transform (see A001906 for definition) of this sequence is A036442: 1, 4, 32, 512, 16384, ... . - Philippe Deléham, Jul 03 2005
Also number of paths from (0,0) to (n,0) using only steps U = (1,1), H = (1,0) and D =(1,-1), U can have 2 colors and H can have 3 colors. - N-E. Fahssi, Jan 27 2008
Equals row sums of triangle A152250 and INVERT transform of A109980: (1, 2, 8, 36, 172, 852, ...). - Gary W. Adamson, Nov 30 2008
Number of overpartitions in the n X n box (treat a walk of the type in the first comment as an overpartition, by interpreting a NE step as N, E with the part thus created being overlined). - William J. Keith, May 19 2017
Diagonal of rational functions 1/(1 - x - y - x*y), 1/(1 - x - y*z - x*y*z). - Gheorghe Coserea, Jul 03 2018
Dimensions of endomorphism algebras End(R^{(n)}) in the Delannoy category attached to the oligomorphic group of order preserving self-bijections of the real line. - Noah Snyder, Mar 22 2023
a(n) is the number of ways to tile a strip of length n with white squares, black squares, and red dominos, where we must have an equal number of white and black squares. - Greg Dresden and Leo Zhang, Jul 11 2025

			G.f. = 1 + 3*x + 13*x^2 + 63*x^3 + 321*x^4 + 1683*x^5 + 8989*x^6 + ...

Frits Beukers, Arithmetic properties of Picard-Fuchs equations, Séminaire de Théorie des nombres de Paris, 1982-83, Birkhäuser Boston, Inc.
Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 593.
L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 81.
L. Moser and W. Zayachkowski, Lattice paths with diagonal steps, Scripta Math., 26 (1961), 223-229.
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, Wadsworth, Vol. 2, 1999; see Example 6.3.8 and Problem 6.49.
D. B. West, Combinatorial Mathematics, Cambridge, 2021, p. 28.

Chai Wah Wu, Table of n, a(n) for n = 0..1308 (all terms < 10^1000, first 201 terms from T. D. Noe)
M. Abrate, S. Barbero, U. Cerruti, and N. Murru, Fixed Sequences for a Generalization of the Binomial Interpolated Operator and for some Other Operators, J. Int. Seq. 14 (2011), #11.8.1.
B. Adamczewski, J. P. Bell, and E. Delaygue, Algebraic independence of G-functions and congruences "à la Lucas", arXiv:1603.04187 [math.NT], 2016.
J.-M. Autebert, A.-M. Décaillot, and S. R. Schwer, H.-A. Delannoy et les oeuvres posthumes d'Édouard Lucas, Gazette des Mathématiciens - no 95, Jan 2003 (in French).
J.-M. Autebert, M. Latapy, and S. R. Schwer, Le treillis des Chemins de Delannoy, Discrete Math., 258 (2002), 225-234.
J.-M. Autebert and S. R. Schwer, On generalized Delannoy paths, SIAM J. Discrete Math., 16(2) (2003), 208-223.
Cyril Banderier and Sylviane Schwer, Why Delannoy numbers?, arXiv:math/0411128 [math.CO], 2004.
Cyril Banderier and Sylviane Schwer, Why Delannoy numbers?, Journal of Statistical Planning and Inference, 135(1) (2005), 40-54.
Paul Barry, On Integer-Sequence-Based Constructions of Generalized Pascal Triangles, Journal of Integer Sequences, 9 (2006), #06.2.4.
Paul Barry, On the Central Coefficients of Riordan Matrices, Journal of Integer Sequences, 16 (2013), #13.5.1.
Paul Barry, On the Inverses of a Family of Pascal-Like Matrices Defined by Riordan Arrays, Journal of Integer Sequences, 16 (2013), #13.5.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 and Aoife Hennessy, Generalized Narayana Polynomials, Riordan Arrays, and Lattice Paths, Journal of Integer Sequences, 15 (2012), #12.4.8.
Paul Barry, Moment sequences, transformations, and Spidernet graphs, arXiv:2307.00098 [math.CO], 2023.
Thomas Baruchel and C. Elsner, On error sums formed by rational approximations with split denominators, arXiv:1602.06445 [math.NT], 2016.
H. Bateman, Some problems in potential theory, Messenger Math., 52 (1922), 71-78. [Annotated scanned copy]
Raymond A. Beauregard and Vladimir A. Dobrushkin, Powers of a Class of Generating Functions, Mathematics Magazine, 89(5) (2016), 359-363.
Hacène Belbachir and Abdelghani Mehdaoui, Recurrence relation associated with the sums of square binomial coefficients, Quaestiones Mathematicae (2021) Vol. 44, Issue 5, 615-624.
Hacène Belbachir, Abdelghani Mehdaoui, and László Szalay, Diagonal Sums in the Pascal Pyramid, II: Applications, J. Int. Seq., 22 (2019), #19.3.5.
A. Bostan, S. Boukraa, J.-M. Maillard, and J.-A. Weil, Diagonals of rational functions and selected differential Galois groups, arXiv:1507.03227 [math-ph], 2015.
J. S. Caughman et al., A note on lattice chains and Delannoy numbers, Discrete Math., 308 (2008), 2623-2628.
Jia-Yu Chen and Chen Wang, Congruences concerning generalized central trinomial coefficients, arXiv:2012.04523 [math.NT], 2020.
Johann Cigler, Some nice Hankel determinants, 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.
M. Coster, Email, Nov 1990.
F. D. Cunden, Statistical distribution of the Wigner-Smith time-delay matrix for chaotic cavities, arXiv:1412.2172 [cond-mat.mes-hall], 2014.
Emeric Deutsch and B. E. Sagan, Congruences for Catalan and Motzkin numbers and related sequences, J. Num. Theory 117 (2006), 191-215.
Ömür Deveci and Anthony G. Shannon, Some aspects of Neyman triangles and Delannoy arrays, Mathematica Montisnigri (2021) Vol. L, 36-43.
R. M. Dickau, Delannoy and Motzkin Numbers [Many illustrations].
R. M. Dickau, The 13 paths in a 4 X 4 grid.
T. Doslic, Seven lattice paths to log-convexity, Acta Appl. Mathem. 110(3) (2010), 1373-1392.
Tomislav Došlic and Darko Veljan, Logarithmic behavior of some combinatorial sequences, Discrete Math. 308(11) (2008), 2182-2212. MR2404544 (2009j:05019) - _N. J. A. Sloane_, May 01 2012
D. Drake, Bijections from Weighted Dyck Paths to Schröder Paths, J. Int. Seq. 13 (2010), #10.9.2.
Rui Duarte and António Guedes de Oliveira, Generating functions of lattice paths, Univ. do Porto (Portugal 2023).
M. Dziemianczuk, Generalizing Delannoy numbers via counting weighted lattice paths, INTEGERS, 13 (2013), #A54.
M. Dziemianczuk, On Directed Lattice Paths With Additional Vertical Steps, arXiv:1410.5747 [math.CO], 2014.
James East and Nicholas Ham, Lattice paths and submonoids of Z^2, arXiv:1811.05735 [math.CO], 2018.
Steffen Eger, On the Number of Many-to-Many Alignments of N Sequences, arXiv:1511.00622 [math.CO], 2015.
Luca Ferrari and Emanuele Munarini, Enumeration of edges in some lattices of paths, arXiv:1203.6792 [math.CO], 2012.
Luca Ferrari and Emanuele Munarini, Enumeration of edges in some lattices of paths, J. Int. Seq. 17 (2014), #14.1.5.
Seth Finkelstein, Letter to N. J. A. Sloane, Mar 24 1990, with attachments.
S. Garrabrant and I. Pak, Counting with irrational tiles, arXiv:1407.8222 [math.CO], 2014.
Joël Gay and Vincent Pilaud, The weak order on Weyl posets, arXiv:1804.06572 [math.CO], 2018.
Taras Goy and Mark Shattuck, Determinant identities for the Catalan, Motzkin and Schröder numbers, Art Disc. Appl. Math. (2023).
Nate Harman, Andrew Snowden, and Noah Snyder, The Delannoy Category, arxiv:2211.15392 [math.RT], 2023.
Tian-Xiao He, One-pth Riordan Arrays in the Construction of Identities, arXiv:2011.00173 [math.CO], 2020.
M. D. Hirschhorn, How many ways can a king cross the board?, Austral. Math. Soc. Gaz., 27 (2000), 104-106.
Nick Hobson, Python program for this sequence.
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.
Milan Janjic, Two Enumerative Functions
Svante Janson, Patterns in random permutations avoiding some sets of multiple patterns, arXiv:1804.06071 [math.PR], 2018.
S. Kaparthi and H. R. Rao, Higher dimensional restricted lattice paths with diagonal steps, Discr. Appl. Math., 31 (1991), 279-289.
D. E. Knuth and N. J. A. Sloane, Correspondence, December 1999.
Daniel Krenn and Jeffrey Shallit, Strongly k-recursive sequences, arXiv:2401.14231 [cs.FL], 2024.
D. F. Lawden, On the Solution of Linear Difference Equations, Math. Gaz., 36 (1952), 193-196.
Tamás Lengyel, On some p-adic properties and supercongruences of Delannoy and Schröder Numbers, Integers (2021) Vol. 21, #A86.
Huyile Liang, Yanni Pei, and Yi Wang, Analytic combinatorics of coordination numbers of cubic lattices, arXiv:2302.11856 [math.CO], 2023. See p. 4.
Huyile Liang, Jeffrey Remmel, and Sainan Zheng, Stieltjes moment sequences of polynomials, arXiv:1710.05795 [math.CO], 2017, see page 18.
Max A. Little and Ugur Kayas, Polymorphic dynamic programming by algebraic shortcut fusion, arXiv:2107.01752 [cs.DS], 2021.
Lily L. Liu, Positivity of three-term recurrence sequences, Electronic J. Combinatorics, 17 (2010), #R57.
Romeo Mestrovic, Lucas' theorem: its generalizations, extensions and applications (1878-2014), arXiv preprint arXiv:1409.3820 [math.NT], 2014.
Lili Mu and Sai-nan Zheng, On the Total Positivity of Delannoy-Like Triangles, Journal of Integer Sequences, 20 (2017), #17.1.6.
Leo Moser, Note 2487: King paths on a chessboard, Math. Gaz., 39 (1955), 54 (one page only).
Emanuele Munarini, Combinatorial properties of the antichains of a garland, Integers, 9 (2009), 353-374.
Tony D. Noe, On the Divisibility of Generalized Central Trinomial Coefficients, Journal of Integer Sequences, 9 (2006), #06.2.7.
P. Peart and W.-J. Woan, Generating Functions via Hankel and Stieltjes Matrices, J. Integer Seqs., 3 (2000), #00.2.1.
R. Pemantle and M. C. Wilson, Asymptotics of multivariate sequences, I: smooth points of the singular variety, arXiv:math/0003192 [math.CO], 2000.
C. de Jesús Pita Ruiz Velasco, Convolution and Sulanke Numbers, JIS 13 (2010), #10.1.8.
F. Qi, X.-T. Shi and B.-N. Guo, Some properties of the Schroder numbers, Indian J. Pure Appl. Math 47 (4) (2016) 717-732.
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
J. Riordan, Letter, Jul 06 1978.
John Riordan, Letter to N. J. A. Sloane, Sep 26 1980 with notes on the 1973 Handbook of Integer Sequences. Note that the sequences are identified by their N-numbers, not their A-numbers.
E. Rowland and D. Zeilberger, A Case Study in Meta-AUTOMATION: AUTOMATIC Generation of Congruence AUTOMATA For Combinatorial Sequences, arXiv:1311.4776 [math.CO], 2013.
S. Samieinia, The number of continuous curves in digital geometry, Research Reports in Mathematics, Number 3, 2008.
S. R. Schwer and J.-M. Auterbert, Henri-Auguste Delannoy, une biographie, Math. & Sci. hum. / Mathematical Social Sciences, 43e année, no. 174 (2006), 25-67.
Seunghyun Seo, The Catalan Threshold Arrangement, Journal of Integer Sequences, 20 (2017), #17.1.1.
T. Sillke, The Delannoy numbers.
Mark Shattuck, On the zeros of some polynomials with combinatorial coefficients, Annales Mathematicae et Informaticae, 42 (2013), 93-101.
Zhao Shen, On the 3-adic valuation of a class of Apery-like numbers, arXiv:2112.11135 [math.NT], 2021.
J. B. Slowinski, The Number of Multiple Alignments, Molecular Phylogenetics and Evolution, 10(2) (1998), 264-266.
J. B. Slowinski, The Number of Multiple Alignments, Molecular Phylogenetics and Evolution, 10(2) (1998), 264-266.
R. G. Stanton and D. D. Cowan, Note on a "square" functional equation, SIAM Rev., 12 (1970), 277-279.
R. A. Sulanke, Moments of generalized Motzkin paths, J. Integer Sequences, 3 (2000), #00.1.
R. A. Sulanke, Objects Counted by the Central Delannoy Numbers, Journal of Integer Sequences, 5 (2002), #03.1.5.
R. A. Sulanke et al., Another description of the central Delannoy numbers, Problem 10894, Amer. Math. Monthly, 110(5) (2003), 443-444.
Zhi-Wei Sun, On Delannoy numbers and Schroeder numbers, Journal of Number Theory 131(12) (2011), 2387-2397. doi:10.1016/j.jnt.2011.06.005
Marius Tarnauceanu, The number of fuzzy subgroups of finite cyclic groups and Delannoy numbers, European Journal of Combinatorics 30(1) (2009), 283-287.
Bernhard Von Stengel, New maximal numbers of equilibria in bimatrix games, Discrete & Computational Geometry 21(4) (1999), 557-568. See Eq. (3.7).
Rong-Hua Wang and Michael X. X. Zhong, Congruences for sums of Delannoy numbers and polynomials, arXiv:2505.05728 [math.CO], 2025. See p. 2.
Yi Wang, Sai-Nan Zheng, and Xi Chen, Analytic aspects of Delannoy numbers, Discrete Mathematics 342.8 (2019): 2270-2277.
Eric Weisstein's World of Mathematics, Delannoy Number.
Eric Weisstein's World of Mathematics, Schmidt's Problem.
W.-J. Woan, Hankel Matrices and Lattice Paths, J. Integer Sequences, 4 (2001), #01.1.2.
E. X. W. Xia and O. X. M. Yao, A Criterion for the Log-Convexity of Combinatorial Sequences, The Electronic Journal of Combinatorics, 20 (2013), #P3.
Lin Yang, Yu-Yuan Zhang, and Sheng-Liang Yang, The halves of Delannoy matrix and Chung-Feller properties of the m-Schröder paths, Linear Alg. Appl. (2024).

Cf. A008288, bisection of A026003, A027618, A047665, A052141, A084773, A152250, A109980, A000129, A078057, A241023, A243949.
Main diagonal of A064861.
Column k=2 of A262809 and A263159.

seq(add(multinomial(n+k,n-k,k,k),k=0..n),n=0..20); # Zerinvary Lajos, Oct 18 2006
seq(orthopoly[P](n,3), n=0..100); # Robert Israel, Nov 03 2015

f[n_] := Sum[ Binomial[n, k] Binomial[n + k, k], {k, 0, n}]; Array[f, 21, 0] (* Or *)
a[0] = 1; a[1] = 3; a[n_] := a[n] = (3(2 n - 1)a[n - 1] - (n - 1)a[n - 2])/n; Array[a, 21, 0] (* Or *)
CoefficientList[ Series[1/Sqrt[1 - 6x + x^2], {x, 0, 20}], x] (* Robert G. Wilson v *)
Table[LegendreP[n, 3], {n, 0, 22}] (* Jean-François Alcover, Jul 16 2012, from first formula *)
a[n_] := Hypergeometric2F1[-n, n+1, 1, -1]; Table[a[n], {n, 0, 22}] (* Jean-François Alcover, Feb 26 2013 *)
a[ n_] := With[ {m = If[n < 0, -1 - n, n]}, SeriesCoefficient[ (1 - 6 x + x^2)^(-1/2), {x, 0, m}]]; (* Michael Somos, Jun 10 2015 *)

a(n):=coeff(expand((1+3*x+2*x^2)^n),x,n);
makelist(a(n),n,0,12); /* Emanuele Munarini, Mar 02 2011 */

{a(n) = if( n<0, n = -1 - n); polcoeff( 1 / sqrt(1 - 6*x + x^2 + x * O(x^n)), n)}; /* Michael Somos, Sep 23 2006 */

{a(n) = if( n<0, n = -1 - n); subst( pollegendre(n), x, 3)}; /* Michael Somos, Sep 23 2006 */

{a(n) = if( n<0, n = -1 - n); n++; subst( Pol(((1 - x) / (1 - 2*x) + O(x^n))^n), x, 1);} /* Michael Somos, Sep 23 2006 */

a(n)=if(n<0, 0, polcoeff((1+3*x+2*x^2)^n, n)) \\ Paul Barry, Aug 22 2007

/* same as in A092566 but use */
steps=[[1,0], [0,1], [1,1]]; /* Joerg Arndt, Jun 30 2011 */

a(n)=sum(k=0,n,binomial(n,k)*binomial(n+k,k)); \\ Joerg Arndt, May 11 2013

my(x='x+O('x^30)); Vec(1/sqrt(1 - 6*x + x^2)) \\ Altug Alkan, Oct 17 2015

# from Nick Hobson.
def f(a, b):
    if a == 0 or b == 0:
        return 1
    return f(a, b - 1) + f(a - 1, b) + f(a - 1, b - 1)
[f(n, n) for n in range(7)]

from gmpy2 import divexact
A001850 = [1, 3]
for n in range(2,10**3):
    A001850.append(divexact(A001850[-1]*(6*n-3)-(n-1)*A001850[-2],n))
# Chai Wah Wu, Sep 01 2014

a = lambda n: hypergeometric([-n, -n], [1], 2)
[simplify(a(n)) for n in range(23)] # Peter Luschny, Nov 19 2014

a(n) = P_n(3), where P_n is n-th Legendre polynomial.
G.f.: 1 / sqrt(1 - 6*x + x^2).
a(n) = a(n-1) + 2*A002002(n) = Sum_{j} A063007(n, j). - Henry Bottomley, Jul 02 2001
Dominant term in asymptotic expansion is binomial(2*n, n)/2^(1/4)*((sqrt(2) + 1)/2)^(2*n + 1)*(1 + c_1/n + c_2/n^2 + ...). - Michael David Hirschhorn
a(n) = Sum_{i=0..n} (A000079(i)*A008459(n, i)) = Sum_{i=0..n} (2^i * C(n, i)^2). - Antti Karttunen, Oct 10 2001
a(n) = Sum_{k=0..n} C(n+k, n-k)*C(2*k, k). - Benoit Cloitre, Feb 13 2003
a(n) = Sum_{k=0..n} C(n, k)^2 * 2^k. - Michael Somos, Oct 08 2003
a(n - 1) = coefficient of x^n in A120588(x)^n if n>=0. - Michael Somos, Apr 11 2012
G.f. of a(n-1) = 1 / (1 - x / (1 - 2*x / (1 - 2*x / (1 - x / (1 - 2*x / (1 - x / ...)))))). - Michael Somos, May 11 2012
INVERT transform is A109980. BINOMIAL transform is A080609. BINOMIAL transform of A006139. PSUM transform is A089165. PSUMSIGN transform is A026933. First backward difference is A110170. - Michael Somos, May 11 2012
E.g.f.: exp(3*x)*BesselI(0, 2*sqrt(2)*x). - Vladeta Jovovic, Mar 21 2004
a(n) = Sum_{k=0..n} C(2*n-k, n)*C(n, k). - Paul Barry, Apr 23 2005
a(n) = Sum_{k>=n} binomial(k, n)^2/2^(k+1). - Vladeta Jovovic, Aug 25 2006
a(n) = a(-1 - n) for all n in Z. - Michael Somos, Sep 23 2006
D-finite with recurrence: a(-1) = a(0) = 1; n*a(n) = 3*(2*n-1)*a(n-1) - (n-1)*a(n-2). Eq (4) in T. D. Noe's article in JIS 9 (2006) #06.2.7.
Define general Delannoy numbers by (i,j > 0): d(i,0) = d(0,j) = 1 =: d(0,0) and d(i,j) = d(i-1,j-1) + d(i-2,j-1) + d(i-1,j). Then a(k) = Sum_{j >= 0} d(k,j)^2 + d(k-1,j)^2 = A026933(n)+A026933(n-1). This is a special case of the following formula for general Delannoy numbers: d(k,j) = Sum_{i >= 0, p=0..n} d(p, i) * d(n-p, j-i) + d(p-1, i) * d(n-p-1, j-i-1). - Peter E John, Oct 19 2006
Coefficient of x^n in (1 + 3*x + 2*x^2)^n. - N-E. Fahssi, Jan 11 2008
a(n) = A008288(A046092(n)). - Philippe Deléham, Apr 08 2009
G.f.: 1/(1 - x - 2*x/(1 - x - x/(1 - x - x/(1 - x - x/(1 - ... (continued fraction). - Paul Barry, May 28 2009
G.f.: d/dx log(1/(1 - x*A001003(x))). - Vladimir Kruchinin, Apr 19 2011
G.f.: 1/(2*Q(0) + x - 1) where Q(k) = 1 + k*(1-x) - x - x*(k + 1)*(k + 2)/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, Mar 14 2013
a(n) = Sum_{k=0..n} C(n,k) * C(n+k,k). - Joerg Arndt, May 11 2013
G.f.: G(0), where G(k) = 1 + x*(6 - x)*(4*k + 1)/(4*k + 2 - 2*x*(6-x)*(2*k + 1)*(4*k + 3)/(x*(6 - x)*(4*k + 3) + 4*(k + 1)/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, Jun 22 2013
G.f.: 2/G(0), where G(k) = 1 + 1/(1 - x*(6 - x)*(2*k - 1)/(x*(6 - x)*(2*k - 1) + 2*(k + 1)/G(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Jul 16 2013
G.f.: G(0)/2, where G(k) = 1 + 1/(1 - x*(6 - x)*(2*k + 1)/(x*(6 - x)*(2*k + 1) + 2*(k + 1)/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, Jul 17 2013
a(n)^2 = Sum_{k=0..n} 2^k * C(2*k, k)^2 * C(n+k, n-k) = A243949(n). - Paul D. Hanna, Aug 17 2014
a(n) = hypergeom([-n, -n], [1], 2). - Peter Luschny, Nov 19 2014
a(n) = Sum_{k=0..n/2} C(n-k,k) * 3^(n-2*k) * 2^k * C(n,k). - Vladimir Kruchinin, Jun 29 2015
a(n) = A049600(n, n-1).
a(n) = Sum_{0 <= j, k <= n} (-1)^(n+j)*C(n,k)*C(n,j)*C(n+k,k)*C(n+k+j,k+j). Cf. A126086 and A274668. - Peter Bala, Jan 15 2020
a(n) ~ c * (3 + 2*sqrt(2))^n / sqrt(n), where c = 1/sqrt(4*Pi*(3*sqrt(2)-4)) = 0.572681... (Banderier and Schwer, 2005). - Amiram Eldar, Jun 07 2020
a(n+1) = 3*a(n) + 2*Sum_{l=1..n} A006318(l)*a(n-l). [Eq. (1.16) in Qi-Shi-Guo (2016)]
a(n) ~ (1 + sqrt(2))^(2*n+1) / (2^(5/4) * sqrt(Pi*n)). - Vaclav Kotesovec, Jan 09 2023
a(n-1) + a(n) = A241023(n) for n >= 1. - Peter Bala, Sep 18 2024
a(n) = Sum_{k=0..n} C(n+k, 2*k) * C(2*k, k). - Greg Dresden and Leo Zhang, Jul 11 2025

New name and reference Sep 15 1995

Formula and more references from Don Knuth, May 15 1996

A026641 Number of nodes of even outdegree (including leaves) in all ordered trees with n edges.

Original entry on oeis.org

1, 1, 4, 13, 46, 166, 610, 2269, 8518, 32206, 122464, 467842, 1794196, 6903352, 26635774, 103020253, 399300166, 1550554582, 6031074184, 23493410758, 91638191236, 357874310212, 1399137067684, 5475504511858, 21447950506396

Offset: 0

Clark Kimberling

Number of lattice paths from (0,0) to (n,n) using steps (1,0),(0,2),(1,1). - Joerg Arndt, Jun 30 2011
From Emeric Deutsch, Jan 25 2004: (Start)
Let B = 1/sqrt(1-4*z) = g.f. for central binomial coeffs (A000984); F = (1-sqrt(1-4*z))/(z*(3-sqrt(1-4*z))) = g.f. for (A000957).
B = 1 + 2*z + 6*z^2 + 20*z^3 + ... gives the number of nodes in all ordered trees with 0,1,2,3,... edges. On p. 288 of the Deutsch-Shapiro paper one finds that z*B*F = z + 2*z^2 + 7*z^3 + 24*z^4 + ... gives the number of nodes of odd outdegree in all ordered trees with 1,2,3,... edges (cf. A014300).
Consequently, B - z*B*F = 2/(3*sqrt(1-4*z)-1+4*z) = 1 + z + 4*z^2 + 13*z^3 + 46*z^4 + ... gives the total number of nodes of even degree in all ordered trees with 0,1,2,3,4,... edges.  (End)
Main diagonal of the following array: first column is filled with 1's, first row is filled alternatively with 1's or 0's: m(i,j) = m(i-1,j) + m(i,j-1): 1 0 1 0 1 ... / 1 1 2 2 3 ... / 1 2 4 6 9 ... / 1 3 7 13 22 ... / 1 4 11 24 46 ... - Benoit Cloitre, Aug 05 2002
The Hankel transform of [1,1,4,13,46,166,610,2269,...] is 3^n. - Philippe Deléham, Mar 08 2007
Second binomial transform of A127361. - Philippe Deléham, Mar 14 2007
Starting with offset 1, generated from iterates of M * [1,1,1,...]; where M = a tridiagonal matrix with (0,2,2,2,...) in the main diagonal and (1,1,1,...) in the super and subdiagonals. - Gary W. Adamson, Jan 04 2009
Equals left border of triangle A158815. - Gary W. Adamson, Mar 27 2009
Equals the INVERTi transform of A101850: (1, 2, 7, 26, 100, ...). - Gary W. Adamson, Jan 10 2012
Diagonal of rational function 1/(1 - (x + x*y + y^2)). - Gheorghe Coserea, Aug 06 2018
Let A(i, j) denote the infinite array such that the i-th row of this array is the sequence obtained by applying the partial sum operator i times to the function (-1)^(n+1) for n > 0. Then A(n, n) equals a(n-1) for all n > 0. - John M. Campbell, Jan 20 2019
These numbers have the same parity as the Catalan numbers A000108; that is, a(n) is odd if and only if n = 2^k - 1 for some nonnegative integer k. It appears that if a(n) is odd then a(n) == 1 (mod 4). - Peter Bala, Feb 07 2024
The number a(n)/(n+1) is the coefficient of x^(n+1) in log(1+(1-sqrt(1-4*x))/2), the generating series of the Sabinin operad. - F. Chapoton, Mar 14 2024

			From _Joerg Arndt_, Jul 01 2011: (Start)
The triangle of number of lattice paths from (0,0) to (n,k) using steps (1,0),(0,2),(1,1) begins
  1;
  1, 1;
  1, 2,  4;
  1, 3,  7, 13;
  1, 4, 11, 24,  46;
  1, 5, 16, 40,  86, 166;
  1, 6, 22, 62, 148, 314,  610;
  1, 7, 29, 91, 239, 553, 1163, 2269;
This sequence is the diagonal. (End)
G.f. = 1 + x + 4*x^2 + 13*x^3 + 46*x^4 + 166*x^5 + 610*x^6 + 2269*x^7 + ...

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Paul Barry, A Catalan Transform and Related Transformations on Integer Sequences, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.5.
Isaac DeJager, Madeleine Naquin, and Frank Seidl, Colored Motzkin Paths of Higher Order, VERUM 2019.
Emeric Deutsch and L. Shapiro, A survey of the Fine numbers, Discrete Math., 241 (2001), 241-265.
Karl Dilcher and Maciej Ulas, Arithmetic properties of polynomial solutions of the Diophantine equation P(x)x^(n+1)+Q(x)(x+1)^(n+1) = 1, arXiv:1909.11222 [math.NT], 2019.
Filippo Disanto, Andrea Frosini and Simone Rinaldi, Renzo Pinzani, The Combinatorics of Convex Permutominoes, Southeast Asian Bulletin of Mathematics (2008) 32: 883-912.

Cf. A101850, A120588, A158815.

Cf. A091526 (k=-2), A072547 (k=-1), this sequence (k=0), A014300 (k=1), A014301 (k=2), A172025 (k=3), A172061 (k=4), A172062 (k=5), A172063 (k=6), A172064 (k=7), A172065 (k=8), A172066 (k=9), A172067 (k=10).

List([0..25],n->(-1)^n*Sum([0..n],k->(-1)^k*Binomial(n+k,k))); # Muniru A Asiru, Aug 06 2018

[(-1)^n*(&+[(-1)^k*Binomial(n+k, k): k in [0..n]]): n in [0..30]]; // G. C. Greubel, Feb 12 2019

seq(add((binomial(k+n, n-k)*binomial(n-k, k)),k=0..floor(n/2)),n=0..30);
# From Richard Choulet, Jan 22 2010: (Start)
a:= n -> add(binomial(2*n-k, k)*binomial(k, n-k), k=floor(n/2)..n):
a:= n -> `if`(n<2, 1, (3/(2))*binomial(2*n-1, n-1)-(1/2)*a(n-1)):
a:= n -> (-1/2)^(n+2)+(2/3)*add(4^(n-k)*(binomial(2*k, k)*(1/(1-2*k))
        *(1-(-1/8)^(n-k+1))), k=0..n):
a:= n -> (-1/2)^(n+2)+(3/4)*add(((-1/2)^(n-k))*(binomial(2*k, k)), k=0..n):
seq(a(n), n=0..30); # (End)
gf := log(1 + (1 - sqrt(1 - 4*x))/2) / x: ser := series(gf, x, 30):
seq((n + 1)*coeff(ser, x, n), n = 0..24);  # Peter Luschny, Mar 16 2024

f[n_]:= Sum[ Binomial[n+k, k]*Cos[Pi*(n+k)], {k, 0, n}]; Array[f, 25, 0] (* Robert G. Wilson v, Apr 02 2012 *)
CoefficientList[Series[2/(3*Sqrt[1-4*x]-1+4*x), {x, 0, 20}], x] (* Vaclav Kotesovec, Feb 12 2014 *)
a[ n_]:= SeriesCoefficient[ D[ Log[1+(1-Sqrt[1-4x])/2], x], {x, 0, n}]; (* Michael Somos, May 18 2015 *)

a(n)=(-1)^n*sum(k=0,n,(-1)^k*binomial(n+k,k))

/* same as in A092566 but use */
steps=[[1,0], [0,2], [1,1]]; /* Joerg Arndt, Jun 30 2011 */

[(-1)^n*sum((-1)^k*binomial(n+k, k) for k in (0..n)) for n in (0..30)] # G. C. Greubel, Feb 12 2019

G.f. is logarithmic derivative of the generating function for the Catalan numbers A000108. So this sequence might be called the "log-Catalan" numbers. - Murray R. Bremner, Jan 25 2004
a(n) = Sum_{k=0..floor(n/2)} binomial(k+n, n-k)*binomial(n-k, k). - Detlef Pauly (dettodet(AT)yahoo.de), Nov 15 2001
G.f.: 2/(3*sqrt(1-4*z)-1+4*z). - Emeric Deutsch, Jul 09 2002
a(n) = (-1)^n*Sum_{k=0..n} (-1)^k*C(n+k, k). - Benoit Cloitre, Aug 20 2002
a(n) = Sum_{j=0..floor(n/2)} binomial(2*n-2*j-1, n-1). - Emeric Deutsch, Jan 28 2004
From Paul Barry, Dec 18 2004: (Start)
A Catalan transform of the Jacobsthal numbers A001045(n+1) under the mapping G(x)-> G(xc(x)), c(x) the g.f. of A000108. The inverse mapping is H(x)->H(x(1-x)).
a(n) = Sum_{k=0..n} (k/(2*n-k))*binomial(2*n-k, n-k)*A001045(k+1). (End)
a(n) = Sum_{k=0..n} binomial(2*n-k, k)*binomial(k, n-k). - Paul Barry, Jul 25 2005
a(n) = Sum_{k=0..n-1} A126093(n,k). - Philippe Deléham, Mar 08 2007
a(n) = (-1/2)^(n+2) + (2/3)*Sum_{k=0..n} ( (4^n-k)*binomial(2*k,k)*(1/(1-2*k))*(1-(-1/8)^(n-k+1)) ). - Yalcin Aktar, Jul 06 2007
a(n) = (-1/2)^(n+2) + (3/4)*Sum_{k=0..n} (-1/2)^(n-k)*binomial(2*k,k). - Yalcin Aktar, Jul 06 2007
From Richard Choulet, Jan 22 2010: (Start)
a(n) = (3*binomial(2*n-1,n-1) - d(n-1))/2, where d(n) = Sum_{k=floor(n/2)..n} binomial(2*n-k, k)*binomial(k, n-k).
a(n) = a(n-1) + (3/2)*Sum_{k=2..n} (1/(2*k-1))*binomial(2*k,k)*a(n-k).
a(n) = (2/3)*binomial(2*n,n) + (2/9)*((-2)^n/n!)*Sum_{k>=0} ( Product_{p=0..n-1} (k-2*p) /3^k).
a(n) = Sum_{k=0..n} (-1)^k*binomial(2*n-k,n).
a(n) = ( Sum_{k=0..n} (1/2)^(n-k+1)*binomial(n+k,k) )^2*(-1/2)^(n+2). (End)
From Gary W. Adamson, Nov 22 2011: (Start)
a(n) is the upper left term of M^n, M = an infinite square production matrix as follows:
  1, 3, 0, 0, 0, ...
  1, 1, 1, 0, 0, ...
  1, 1, 1, 1, 0, ...
  1, 1, 1, 1, 1, ...
  ...
Also, a(n+1) is the sum of top row terms of M^n; e.g. top row of M^3 = (13, 21, 9, 3), sum = 46 = a(4), a(3) = 13. (End)
D-finite with recurrence: 2n*a(n) + (4-7n)*a(n-1) + 2*(1-2n)*a(n-2) = 0. - R. J. Mathar, Dec 17 2011 [The recurrence is proved with the Wilf-Zeilberger (WZ) method applied to Sum_{k=0..floor(n/2)} binomial(k+n, n-k)*binomial(n-k, k). - T. Amdeberhan, Jul 23 2012]
a(n) = A035317(2*n-1,n) for n > 0. - Reinhard Zumkeller, Jul 19 2012
a(n) ~ 2^(2*n+1) / (3*sqrt(Pi*n)). - Vaclav Kotesovec, Feb 12 2014
a(n) = binomial(2*n,n)*hypergeom([1, -n], [-2*n], -1). - Peter Luschny, May 22 2014
G.f. is the derivative of the logarithm of the g.f. for A120588. - Michael Somos, May 18 2015
a(n) = [x^n] 1/((1 - x^2)*(1 - x)^n). - Ilya Gutkovskiy, Oct 25 2017
From Peter Bala, Feb 25 2019: (Start)
a(n) = Sum_{k = 0..n} binomial(2*n + 1, n + k + 1)*(-2)^k.
a(n-1) = (1/2)*binomial(2*n,n)*( 1 - 2*(n-1)/(n+1) + 4*(n-1)*(n-2)/((n+1)*(n+2)) - 8*(n-1)*(n-2)*(n-3)/((n+1)*(n+2)*(n+3)) + ...) = (1/2)*binomial(2*n,n)*hypergeom([1 - n, 1], [n + 1], 2). (End)
a(0)=1, a(1)=1, and a(n) = (2 - 1/n)*a(n-2) + (7/2 - 2/n)*a(n-1) for n > 1. - Reginald Robson, Nov 01 2022

A013609 Triangle of coefficients in expansion of (1+2*x)^n.

Original entry on oeis.org

1, 1, 2, 1, 4, 4, 1, 6, 12, 8, 1, 8, 24, 32, 16, 1, 10, 40, 80, 80, 32, 1, 12, 60, 160, 240, 192, 64, 1, 14, 84, 280, 560, 672, 448, 128, 1, 16, 112, 448, 1120, 1792, 1792, 1024, 256, 1, 18, 144, 672, 2016, 4032, 5376, 4608, 2304, 512, 1, 20, 180, 960, 3360, 8064, 13440, 15360, 11520, 5120, 1024

Offset: 0

N. J. A. Sloane

T(n,k) is the number of lattice paths from (0,0) to (n,k) with steps (1,0) and two kinds of steps (1,1). The number of paths with steps (1,0) and s kinds of steps (1,1) corresponds to the expansion of (1+s*x)^n. - Joerg Arndt, Jul 01 2011
Also sum of rows in A046816. - Lior Manor, Apr 24 2004
Also square array of unsigned coefficients of Chebyshev polynomials of second kind. - Philippe Deléham, Aug 12 2005
The rows give the number of k-simplices in the n-cube. For example, 1, 6, 12, 8 shows that the 3-cube has 1 volume, 6 faces, 12 edges and 8 vertices. - Joshua Zucker, Jun 05 2006
Triangle whose (i, j)-th entry is binomial(i, j)*2^j.
With offset [1,1] the triangle with doubled numbers, 2*a(n,m), enumerates sequences of length m with nonzero integer entries n_i satisfying sum(|n_i|) <= n. Example n=4, m=2: [1,3], [3,1], [2,2] each in 2^2=4 signed versions: 2*a(4,2) = 2*6 = 12. The Sum over m (row sums of 2*a(n,m)) gives 2*3^(n-1), n >= 1. See the W. Lang comment and a K. A. Meissner reference under A024023. - Wolfdieter Lang, Jan 21 2008
n-th row of the triangle = leftmost column of nonzero terms of X^n, where X = an infinite bidiagonal matrix with (1,1,1,...) in the main diagonal and (2,2,2,...) in the subdiagonal. - Gary W. Adamson, Jul 19 2008
Numerators of a matrix square-root of Pascal's triangle A007318, where the denominators for the n-th row are set to 2^n. - Gerald McGarvey, Aug 20 2009
From Johannes W. Meijer, Sep 22 2010: (Start)
The triangle sums (see A180662 for their definitions) link the Pell-Jacobsthal triangle, whose mirror image is A038207, with twenty-four different sequences; see the crossrefs.
This triangle may very well be called the Pell-Jacobsthal triangle in view of the fact that A000129 (Kn21) are the Pell numbers and A001045 (Kn11) the Jacobsthal numbers.
(End)
T(n,k) equals the number of n-length words on {0,1,2} having n-k zeros. - Milan Janjic, Jul 24 2015
T(n-1,k-1) is the number of 2-compositions of n with zeros having k positive parts; see Hopkins & Ouvry reference. - Brian Hopkins, Aug 16 2020
T(n,k) is the number of chains 0=x_0Geoffrey Critzer, Oct 01 2022
Excluding the initial 1, T(n,k) is the number of k-faces of a regular n-cross polytope. See A038207 for n-cube and A135278 for n-simplex. - Mohammed Yaseen, Jan 14 2023

			Triangle begins:
  1;
  1,  2;
  1,  4,   4;
  1,  6,  12,    8;
  1,  8,  24,   32,   16;
  1, 10,  40,   80,   80,    32;
  1, 12,  60,  160,  240,   192,    64;
  1, 14,  84,  280,  560,   672,   448,    128;
  1, 16, 112,  448, 1120,  1792,  1792,   1024,    256;
  1, 18, 144,  672, 2016,  4032,  5376,   4608,   2304,    512;
  1, 20, 180,  960, 3360,  8064, 13440,  15360,  11520,   5120,  1024;
  1, 22, 220, 1320, 5280, 14784, 29568,  42240,  42240,  28160, 11264,  2048;
  1, 24, 264, 1760, 7920, 25344, 59136, 101376, 126720, 112640, 67584, 24576, 4096;
From _Peter Bala_, Apr 20 2012: (Start)
The triangle can be written as the matrix product A038207*(signed version of A013609).
  |.1................||.1..................|
  |.2...1............||-1...2..............|
  |.4...4...1........||.1..-4...4..........|
  |.8..12...6...1....||-1...6...-12...8....|
  |16..32..24...8...1||.1..-8....24.-32..16|
  |..................||....................|
(End)

B. N. Cyvin et al., Isomer enumeration of unbranched catacondensed polygonal systems with pentagons and heptagons, Match, No. 34 (Oct 1996), pp. 109-121.
G. Hotz, Zur Reduktion von Schaltkreispolynomen im Hinblick auf eine Verwendung in Rechenautomaten, El. Datenverarbeitung, Folge 5 (1960), pp. 21-27.

T. D. Noe, Rows n=0..50 of triangle, flattened
Feryal Alayont and Evan Henning, Edge Covers of Caterpillars, Cycles with Pendants, and Spider Graphs, J. Int. Seq. (2023) Vol. 26, Art. 23.9.4.
H. J. Brothers, Pascal's Prism: Supplementary Material, PDF version.
John Cartan, Cartan's triangle shows the relationship to the n-cube.
R. Ehrenborg and M. Readdy, Characterization of the factorial functions of Eulerian binomial and Sheffer posets
J. Goldman and J. Haglund, Generalized rook polynomials, J. Combin. Theory A91 (2000), 509-530, 1-rook coefficients of k rooks on the 2xn board, all heights 2.
W. G. Harter, Representations of multidimensional symmetries in networks, J. Math. Phys., 15 (1974), 2016-2021.
Brian Hopkins and Stéphane Ouvry, Combinatorics of Multicompositions, arXiv:2008.04937 [math.CO], 2020.
D. A. Zaitsev, A generalized neighborhood for cellular automata, Theoretical Computer Science, 666 (2017), 21-35.

Cf. A007318, A013610, etc.
Appears in A167580 and A167591. - Johannes W. Meijer, Nov 23 2009
From Johannes W. Meijer, Sep 22 2010: (Start)
Triangle sums (see the comments): A000244 (Row1); A000012 (Row2); A001045 (Kn11); A026644 (Kn12); 4*A011377 (Kn13); A000129 (Kn21); A094706 (Kn22); A099625 (Kn23); A001653 (Kn3); A007583 (Kn4); A046717 (Fi1); A007051 (Fi2); A077949 (Ca1); A008998 (Ca2); A180675 (Ca3); A092467 (Ca4); A052942 (Gi1); A008999 (Gi2); A180676 (Gi3); A180677 (Gi4); A140413 (Ze1); A180678 (Ze2); A097117 (Ze3); A055588 (Ze4).
(End)
Cf. A024023, A038207, A046816, A105728, A115068, A135278, A171977, A180662.
T(2n,n) gives A059304.

a013609 n = a013609_list !! n
a013609_list = concat $ iterate ([1,2] *) [1]
instance Num a => Num [a] where
   fromInteger k = [fromInteger k]
   (p:ps) + (q:qs) = p + q : ps + qs
   ps + qs         = ps ++ qs
   (p:ps) * qs'@(q:qs) = p * q : ps * qs' + [p] * qs
    *                = []
-- Reinhard Zumkeller, Apr 02 2011

a013609 n k = a013609_tabl !! n !! k
a013609_row n = a013609_tabl !! n
a013609_tabl = iterate (\row -> zipWith (+) ([0] ++ row) $
                                zipWith (+) ([0] ++ row) (row ++ [0])) [1]
-- Reinhard Zumkeller, Jul 22 2013, Feb 27 2013

[2^k*Binomial(n,k): k in [0..n], n in [0..15]]; // G. C. Greubel, Sep 17 2021

bin2:=proc(n,k) option remember; if k<0 or k>n then 0 elif k=0 then 1 else 2*bin2(n-1,k-1)+bin2(n-1,k); fi; end; # N. J. A. Sloane, Jun 01 2009

Flatten[Table[CoefficientList[(1 + 2*x)^n, x], {n, 0, 10}]][[1 ;; 59]] (* Jean-François Alcover, May 17 2011 *)
BinomialROW[n_, k_, t_] := Sum[Binomial[n, k]*Binomial[k, j]*(-1)^(k - j)*t^j, {j, 0, k}]; Column[Table[BinomialROW[n, k, 3], {n, 0, 10}, {k, 0, n}], Center] (* Kolosov Petro, Jan 28 2019 *)

a(n,k):=coeff(expand((1+2*x)^n),x^k);
create_list(a(n,k),n,0,6,k,0,n); /* Emanuele Munarini, Nov 21 2012 */

/* same as in A092566 but use */
steps=[[1,0], [1,1], [1,1]]; /* note double [1,1] */
/* Joerg Arndt, Jul 01 2011 */

flatten([[2^k*binomial(n,k) for k in (0..n)] for n in (0..15)]) # G. C. Greubel, Sep 17 2021

G.f.: 1 / (1 - x*(1+2*y)).
T(n,k) = 2^k*binomial(n,k).
T(n,k) = 2*T(n-1,k-1) + T(n-1,k). - Jon Perry, Nov 22 2005
Row sums are 3^n = A000244(n). - Joerg Arndt, Jul 01 2011
T(n,k) = Sum_{i=n-k..n} C(i,n-k)*C(n,i). - Mircea Merca, Apr 28 2012
E.g.f.: exp(2*y*x + x). - Geoffrey Critzer, Nov 12 2012
Riordan array (x/(1 - x), 2*x/(1 - x)). Exp(2*x) * e.g.f. for row n = e.g.f. for diagonal n. For example, for n = 3 we have exp(2*x)*(1 + 6*x + 12*x^2/2! + 8*x^3/3!) = 1 + 8*x + 40*x^2/2! + 160*x^3/3! + 560*x^4/4! + .... The same property holds more generally for Riordan arrays of the form (f(x), 2*x/(1 - x)). - Peter Bala, Dec 21 2014
T(n,k) = Sum_{j=0..k} (-1)^(k-j) * binomial(n,k) * binomial(k,j) * 3^j. - Kolosov Petro, Jan 28 2019
T(n,k) = 2*(n+1-k)*T(n,k-1)/k, T(n,0) = 1. - Alexander R. Povolotsky, Oct 08 2023
For n >= 1, GCD(T(n,1), ..., T(n,n)) = GCD(T(n,1),T(n,n)) = GCD(2*n,2^n) = A171977(n). - Pontus von Brömssen, Nov 01 2024

A059304 a(n) = 2^n * (2*n)! / (n!)^2.

Original entry on oeis.org

1, 4, 24, 160, 1120, 8064, 59136, 439296, 3294720, 24893440, 189190144, 1444724736, 11076222976, 85201715200, 657270374400, 5082890895360, 39392404439040, 305870434467840, 2378992268083200, 18531097667174400

Offset: 0

Henry Bottomley, Jan 25 2001

Number of lattice paths from (0,0) to (n,n) using steps (0,1), and two kinds of steps (1,0). - Joerg Arndt, Jul 01 2011
The convolution square root of this sequence is A004981. - T. D. Noe, Jun 11 2002
Also main diagonal of array: T(i,1)=2^(i-1), T(1,j)=1, T(i,j) = T(i,j-1) + 2*T(i-1,j). - Benoit Cloitre, Feb 26 2003
The Hankel transform (see A001906 for definition) of this sequence with interpolated zeros(1, 0, 4, 0, 24, 0, 160, 0, 1120, ...) = is A036442: 1, 4, 32, 512, 16384, ... . - Philippe Deléham, Jul 03 2005
The Hankel transform of this sequence gives A103488. - Philippe Deléham, Dec 02 2007
Equals the central column of the triangle A038207. - Zerinvary Lajos, Dec 08 2007
Equals number of permutations whose reverse shares the same recording tableau in the Robinson-Schensted correspondence with n=(k-1)/2 for k odd. - Dang-Son Nguyen, Jul 02 2024
Number of ternary strings of length 2*n that have the same number of 0's as the combined number of 1's and 2's. For example, a(2)=24 since the strings of length 4 are the 6 permutations of 0011, the 12 permutations of 0012, and the 6 permutations of 0022. - Enrique Navarrete, Jul 30 2025

Harry J. Smith, Table of n, a(n) for n = 0..200
Paul Barry and Arnauld Mesinga Mwafise, Classical and Semi-Classical Orthogonal Polynomials Defined by Riordan Arrays, and Their Moment Sequences, Journal of Integer Sequences, Vol. 21 (2018), Article 18.1.5.
Hacène Belbachir and Abdelghani Mehdaoui, Recurrence relation associated with the sums of square binomial coefficients, Quaestiones Mathematicae (2021) Vol. 44, Issue 5, 615-624.
Hacène Belbachir, Abdelghani Mehdaoui, and László Szalay, Diagonal Sums in the Pascal Pyramid, II: Applications, J. Int. Seq., Vol. 22 (2019), Article 19.3.5.
H. J. Brothers, Pascal's Prism: Supplementary Material.
Tucker J. Ervin, Blake Jackson, Jay Lane, Kyungyong Lee, Son Dang Nguyen, Jack O'Donohue and Michael Vaughan, Permutations whose Reverse Shares the Same Recording Tableau in the Robinson-Schensted Correspondence, Séminaire Lotharingien de Combinatoire 86 (2022), Article B86a.
Tony D. Noe, On the Divisibility of Generalized Central Trinomial Coefficients, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.7.
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.

Diagonal of A013609.
Column k=0 of A067001.
Cf. A000079, A000984, A001906, A036442, A038207, A103488.

[2^n*Binomial(2*n,n): n in [0..25]]; // Vincenzo Librandi, Oct 08 2015

seq(binomial(2*n,n)*2^n,n=0..19); # Zerinvary Lajos, Dec 08 2007

Table[2^n Binomial[2n,n],{n,0,30}] (* Harvey P. Dale, Dec 16 2014 *)

{a(n)=if(n<0, 0, 2^n*(2*n)!/n!^2)} /* Michael Somos, Jan 31 2007 */

{ for (n = 0, 200, write("b059304.txt", n, " ", 2^n * (2*n)! / n!^2); ) } \\ Harry J. Smith, Jun 25 2009

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

def A059304(n): return pow(2,n)*binomial(2*n,n)
print([A059304(n) for n in range(41)]) # G. C. Greubel, Jan 18 2025

a(n) = 2^n * C(2*n,n).
D-finite with recurrence a(n) = 4*(2-1/n)*a(n-1).
a(n) = A000079(n)*A000984(n)
G.f.: 1/sqrt(1-8*x) - T. D. Noe, Jun 11 2002
E.g.f.: exp(4*x)*BesselI(0, 4*x). - Vladeta Jovovic, Aug 20 2003
a(n) = A038207(n,n). - Joerg Arndt, Jul 01 2011
G.f.: G(0)/2, where G(k) = 1 + 1/(1 - 4*x*(2*k+1)/(4*x*(2*k+1) + (k+1)/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 24 2013
E.g.f.: E(0)/2, where E(k) = 1 + 1/(1 - 4*x/(4*x + (k+1)^2/(2*k+1)/E(k+1))); (continued fraction). - Sergei N. Gladkovskii, Jun 01 2013
G.f.: Q(0)/(1+2*sqrt(x)), where Q(k) = 1 + 2*sqrt(x)/(1 - 2*sqrt(x)*(2*k+1)/(2*sqrt(x)*(2*k+1) + (k+1)/Q(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Aug 09 2013
O.g.f.: hypergeom([1/2], [], 8*x). - Peter Luschny, Oct 08 2015
a(n) = Sum_{k = 0..2*n} (-1)^(n+k)*binomial(2*n,k)*binomial(3*n-2*k,n)* binomial(n+k,n). - Peter Bala, Aug 04 2016
a(n) ~ 8^n/sqrt(Pi*n). - Ilya Gutkovskiy, Aug 04 2016
From Amiram Eldar, Jul 21 2020: (Start)
Sum_{n>=0} 1/a(n) = 8/7 + 8*sqrt(7)*arcsin(1/sqrt(8))/49.
Sum_{n>=0} (-1)^n/a(n) = (8/27)*(3 - arcsinh(1/sqrt(8))). (End)
a(n) = Sum_{k = n..2*n} binomial(2*n,k)*binomial(k,n). In general, for m >= 1, Sum_{k = n..m*n} binomial(m*n,k)*binomial(k,n) = 2^((m-1)*n)*binomial(m*n,n). - Peter Bala, Mar 25 2023
Conjecture: a(n) = Sum_{0 <= j, k <= n} binomial(n, j)*binomial(n, k)* binomial(k+j, n). - Peter Bala, Jul 16 2024

A036355 Fibonacci-Pascal triangle read by rows.

Original entry on oeis.org

1, 1, 1, 2, 2, 2, 3, 5, 5, 3, 5, 10, 14, 10, 5, 8, 20, 32, 32, 20, 8, 13, 38, 71, 84, 71, 38, 13, 21, 71, 149, 207, 207, 149, 71, 21, 34, 130, 304, 478, 556, 478, 304, 130, 34, 55, 235, 604, 1060, 1390, 1390, 1060, 604, 235, 55, 89, 420, 1177, 2272, 3310, 3736, 3310, 2272, 1177, 420, 89

Offset: 0

Floor van Lamoen, Dec 28 1998

T(n,k) is the number of lattice paths from (0,0) to (n-k,k) using steps (1,0),(2,0),(0,1),(0,2). - Joerg Arndt, Jun 30 2011, corrected by Greg Dresden, Aug 25 2020
For a closed-form formula for arbitrary left and right borders of Pascal like triangle see A228196. - Boris Putievskiy, Aug 18 2013
For a closed-form formula for generalized Pascal's triangle see A228576. - Boris Putievskiy, Sep 09 2013

			Triangle begins
   1;
   1,   1;
   2,   2,   2;
   3,   5,   5,    3;
   5,  10,  14,   10,    5;
   8,  20,  32,   32,   20,    8;
  13,  38,  71,   84,   71,   38,   13;
  21,  71, 149,  207,  207,  149,   71,  21;
  34, 130, 304,  478,  556,  478,  304, 130,  34;
  55, 235, 604, 1060, 1390, 1390, 1060, 604, 235, 55;
with indices
  T(0,0);
  T(1,0),  T(1,1);
  T(2,0),  T(2,1),  T(2,2);
  T(3,0),  T(3,1),  T(3,2),  T(3,3);
  T(4,0),  T(4,1),  T(4,2),  T(4,3),  T(4,4);
For example, T(4,2) = 14 and there are 14 lattice paths from (0,0) to (4-2,2) = (2,2) using steps (1,0),(2,0),(0,1),(0,2). - _Greg Dresden_, Aug 25 2020

Reinhard Zumkeller, Rows n = 0..120 of triangle, flattened
Index entries for triangles and arrays related to Pascal's triangle

Row sums form sequence A002605. T(n, 0) forms the Fibonacci sequence (A000045). T(n, 1) forms sequence A001629.
Derived sequences: A036681, A036682, A036683, A036684, A036692 (central terms).
Cf. A007318, A051159, A091533, A228196, A228576.
Some other Fibonacci-Pascal triangles: A027926, A037027, A074829, A105809, A109906, A111006, A114197, A162741, A228074.

a036355 n k = a036355_tabl !! n !! k
a036355_row n = a036355_tabl !! n
a036355_tabl = [1] : f [1] [1,1] where
   f us vs = vs : f vs (zipWith (+)
                       (zipWith (+) ([0,0] ++ us) (us ++ [0,0]))
                       (zipWith (+) ([0] ++ vs) (vs ++ [0])))
-- Reinhard Zumkeller, Apr 23 2013

nmax = 11; t[n_, m_] := t[n, m] = tp[n-1, m-1] + tp[n-2, m-2] + tp[n-1, m] + tp[n-2, m]; tp[n_, m_] /; 0 <= m <= n && n >= 0 := t[n, m]; tp[n_, m_] = 0; t[0, 0] = 1; Flatten[ Table[t[n, m], {n, 0, nmax}, {m, 0, n}]] (* Jean-François Alcover, Nov 09 2011, after formula *)

/* same as in A092566 but use */
steps=[[1,0], [2,0], [0,1], [0,2]];
/* Joerg Arndt, Jun 30 2011 */

T(n, m) = T'(n-1, m-1)+T'(n-2, m-2)+T'(n-1, m)+T'(n-2, m), where T'(n, m) = T(n, m) if 0<=m<=n and n >= 0 and T'(n, m)=0 otherwise. Initial term T(0, 0)=1.

G.f.: 1/(1-(1+y)*x-(1+y^2)*x^2). - Vladeta Jovovic, Oct 11 2003

A069835 Define an array as follows: b(i,0)=b(0,j)=1, b(i,j) = 2*b(i-1,j-1) + b(i-1,j) + b(i,j-1). Then a(n) = b(n,n).

Original entry on oeis.org

1, 4, 22, 136, 886, 5944, 40636, 281488, 1968934, 13875544, 98365972, 700701808, 5011371964, 35961808432, 258805997752, 1867175631136, 13500088649734, 97794850668952, 709626281415076, 5157024231645616, 37528209137458516, 273431636191026064, 1994448720786816712

Offset: 0

Benoit Cloitre, May 03 2002

2^n*LegendreP(n,k) yields the central coefficients of (1 + 2*k*x + (k^2-1)*x^2)^n, with g.f. 1/sqrt(1 - 4*k*x + 4*x^2) and e.g.f. exp(2*k*x)BesselI(0, 2*sqrt(k^2-1)*x). - Paul Barry, May 25 2005
Number of Delannoy paths from (0,0) to (n,n) with steps U(0,1), H(1,0) and D(1,1) where D can have two colors. - Paul Barry, May 25 2005
Also number of paths from (0,0) to (n,0) using steps U=(1,1), H=(1,0) and D=(1,-1), the U steps can have three colors and H steps can have four colors. - N-E. Fahssi, Mar 31 2008
Number of lattice paths from (0,0) to (n,n) using steps (1,0), (0,1), and two kinds of steps (1,1). - Joerg Arndt, Jul 01 2011
Hankel transform is 2^n*3^C(n+1,2) = (-1)^C(n+1,2)*A127946(n). - Paul Barry, Jan 24 2011
Central terms of triangle A152842. - Reinhard Zumkeller, May 01 2014
Diagonal of rational functions 1/(1 - x - y - 2*x*y), 1/(1 - x - y*z - 2*x*y*z). - Gheorghe Coserea, Jul 06 2018
The Gauss congruences a(n*p^k) == a(n^p^(k-1)) (mod p^k) hold for prime p and positive integers n and k. - Peter Bala, Jan 07 2022

			The array b is a rewriting of A081577:
  1,  1,  1,   1,   1,    1,    1,    1,     1,     1,     1, ...
  1,  4,  7,  10,  13,   16,   19,   22,    25,    28,    31, ...
  1,  7, 22,  46,  79,  121,  172,  232,   301,   379,   466, ...
  1, 10, 46, 136, 307,  586, 1000, 1576,  2341,  3322,  4546, ...
  1, 13, 79, 307, 886, 2086, 4258, 7834, 13327, 21331, 32521, ...

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

Arkadiusz Wesolowski, Table of n, a(n) for n = 0..250
Paul Barry and Aoife Hennessy, Generalized Narayana Polynomials, Riordan Arrays, and Lattice Paths, Journal of Integer Sequences, Vol. 15, 2012, #12.4.8. - _N. J. A. Sloane_, Oct 08 2012
Hacène Belbachir and Abdelghani Mehdaoui, Recurrence relation associated with the sums of square binomial coefficients, Quaestiones Mathematicae (2021) Vol. 44, Issue 5, 615-624.
Hacène Belbachir, Abdelghani Mehdaoui, and László Szalay, Diagonal Sums in the Pascal Pyramid, II: Applications, J. Int. Seq., Vol. 22 (2019), Article 19.3.5.
Tony D. Noe, On the Divisibility of Generalized Central Trinomial Coefficients, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.7.
Franck Ramaharo, Statistics on some classes of knot shadows, arXiv:1802.07701 [math.CO], 2018.

Cf. A001850.

List([0..25],n->Sum([0..n],k->Binomial(n,k)^2*3^k)); # Muniru A Asiru, Jul 29 2018

a069835 n = a081577 (2 * n) n -- Reinhard Zumkeller, Mar 16 2014

Table[Hypergeometric2F1[-n, -n, 1, 3], {n, 0, 21}] (* Arkadiusz Wesolowski, Aug 13 2012 *)

PARI
```
a(n)=sum(k=0,n,binomial(n,k)^2*3^k)
```

a(n)=if(n<0, 0, polcoeff((1+4*x+3*x^2)^n, n))

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

a(n)=pollegendre(n,2)<Charles R Greathouse IV, Mar 18 2017

From Vladeta Jovovic, May 13 2003: (Start)
a(n) = 2^n*LegendreP(n, 2) = 2^n*hypergeom([ -n, n+1], [1], -1/2) = 2^n*GegenbauerC(n, 1/2, 2) = Sum_{k=0..n} 3^k*binomial(n, k)^2.
D-finite with recurrence: a(n) = 4*(2*n-1)/n*a(n-1) - 4*(n-1)/n*a(n-2).
G.f.: 1/sqrt(1 - 8*x + 4*x^2). (End)
a(n) equals the central coefficient of (1 + 4*x + 3*x^2)^n. - Paul D. Hanna, Jun 03 2003
E.g.f.: exp(4*x)*Bessel_I(0, 2*sqrt(3)*x). - Paul Barry, Sep 20 2004
a(n) = Sum_{k=0..floor(n/2)} C(n, k)*C(2*(n-k), n)*(-1)^k*2^(n-2*k). - Paul Barry, May 25 2005
a(n) = Sum_{k=0..n} C(n, k)*C(n+k, k)*2^(n-k). - Paul Barry, May 25 2005
a(n) = Sum_{k=0..n} C(n, k)^2*3^k. - Paul Barry, Oct 15 2005
G.f.: 1/(1-4x-6x^2/(1-4x-3x^2/(1-4x-3x^2/(1-4x-3x^2/(1-... (continued fraction). - Paul Barry Jan 24 2011
Asymptotic: a(n) ~ sqrt(1/2 + 1/sqrt(3))*(1+sqrt(3))^(2*n)/sqrt(Pi*n). - Vaclav Kotesovec, Sep 11 2012
0 = a(n)*(16*a(n+1) - 48*a(n+2) + 8*a(n+3)) + a(n+1)*(-16*a(n+1) + 64*a(n+2) - 12*a(n+3)) + a(n+2)*(-4*a(n+2) + a(n+3)) for all n in Z. - Michael Somos, Apr 21 2020

A046899 Triangle in which n-th row is {binomial(n+k,k), k=0..n}, n >= 0.

Original entry on oeis.org

1, 1, 2, 1, 3, 6, 1, 4, 10, 20, 1, 5, 15, 35, 70, 1, 6, 21, 56, 126, 252, 1, 7, 28, 84, 210, 462, 924, 1, 8, 36, 120, 330, 792, 1716, 3432, 1, 9, 45, 165, 495, 1287, 3003, 6435, 12870, 1, 10, 55, 220, 715, 2002, 5005, 11440, 24310, 48620, 1, 11, 66, 286, 1001

Offset: 0

N. J. A. Sloane

C(n,k) is the number of lattice paths from (0,0) to (n,k) using steps (1,0) and (0,1). - Joerg Arndt, Jul 01 2011
Row sums are A001700.
T(n, k) is also the number of order-preserving full transformations (of an n-chain) of waist k (waist(alpha) = max(Im(alpha))). - Abdullahi Umar, Oct 02 2008
If T(r,c), r=0,1,2,..., c=1,2,...,(r+1), are the triangle elements, then for r > 0, T(r,c) = binomial(r+c-1,c-1) = M(r,c) is the number of monotonic mappings from an ordered set of r elements into an ordered set of c elements. For example, there are 15 monotonic mappings from an ordered set of 4 elements into an ordered set of 3 elements. For c > r+1, use the identity M(r,c) = M(c-1,r+1) = T(c-1,r+1). For example, there are 210 monotonic mappings from an ordered set of 4 elements into an ordered set of 7 elements, because M(4,7) = T(6,5) = 210. Number of monotonic endomorphisms in a set of r elements, M(r,r), therefore appear on the second diagonal of the triangle which coincides with A001700. - Stanislav Sykora, May 26 2012
Start at the origin. Flip a fair coin to determine steps of (1,0) or (0,1). Stop when you are a (perpendicular) distance of n steps from the x axis or the y axis. For k = 0,1,...,n-1, C(n-1,k)/2^(n+k) is the probability that you will stop on the point (n,k). This is equal to the probability that you will stop on the point (k,n). Hence, Sum_{k=0..n} C(n,k)/2^(n+k) = 1. - Geoffrey Critzer, May 13 2017

			The triangle is the lower triangular part of the square array:
  1|  1,  1,   1,   1,    1,    1,     1,     1,     1, ...
  1,  2|  3,   4,   5,    6,    7,     8,     9,    10, ...
  1,  3,  6|  10,  15,   21,   28,    36,    45,    55, ...
  1,  4, 10,  20|  35,   56,   84,   120,   165,   220, ...
  1,  5, 15,  35,  70|  126,  210,   330,   495,   715, ...
  1,  6, 21,  56, 126,  252|  462,   792,  1287,  2002, ...
  1,  7, 28,  84, 210,  462,  924|  1716,  3003,  5005, ...
  1,  8, 36, 120, 330,  792, 1716,  3432|  6435, 11440, ...
  1,  9, 45, 165, 495, 1287, 3003,  6435, 12870| 24310, ...
  1, 10, 55, 220, 715, 2002, 5005, 11440, 24310, 48620| ...
The array read by antidiagonals gives the binomial triangle.
From _Reinhard Zumkeller_, Jul 27 2012: (Start)
Take the first n elements of the n-th diagonal (NW to SE) of left half of Pascal's triangle and write it as n-th row on the triangle on the right side, see above
  0:                 1                    1
  1:               1   _                  1  2
  2:             1   2  __                1  3  6
  3:           1   3  __  __              1  4 10 20
  4:         1   4   6  __  __            1  5 15 35 70
  5:       1   5  10  __  __  __          1  6 21 56 .. ..
  6:     1   6  15  20  __  __  __        1  7 28 .. .. .. ..
  7:   1   7  21  35  __  __  __  __      1  8 .. .. .. .. .. ..
  8: 1   8  28  56  70  __  __  __  __    1 .. .. .. .. .. .. .. .. (End)

H. W. Gould, A class of binomial sums and a series transform, Utilitas Math., 45 (1994), 71-83.

Reinhard Zumkeller, Rows n=0..150 of triangle, flattened
Karl Dilcher and Maciej Ulas, Arithmetic properties of polynomial solutions of the Diophantine equation P(x)x^(n+1)+Q(x)(x+1)^(n+1)=1, arXiv:1909.11222 [math.NT], 2019. See Qn(x) Table 1 p. 2.
H. W. Gould, A class of binomial sums and a series transform, Utilitas Math., 45 (1994), 71-83. (Annotated scanned copy)
A. Laradji and A. Umar, Combinatorial results for semigroups of order-preserving partial transformations, Journal of Algebra 278, (2004), 342-359.
A. Laradji and A. Umar, Combinatorial results for semigroups of order-preserving full transformations, Semigroup Forum 72 (2006), 51-62.
Index entries for triangles and arrays related to Pascal's triangle

Cf. A000108, A046900, A001700, A007318, A034868, A092392, A239103, A178300.

import Data.List (transpose)
a046899 n k = a046899_tabl !! n !! k
a046899_row n = a046899_tabl !! n
a046899_tabl = zipWith take [1..] $ transpose a007318_tabl
-- Reinhard Zumkeller, Jul 27 2012

/* As triangle */ [[Binomial(n+k, n): k in [0..n]]: n in [0.. 15]]; // Vincenzo Librandi, Aug 18 2015

for n from 0 to 10 do seq( binomial(n+m,n), m = 0 .. n) od; # Zerinvary Lajos, Dec 09 2007

t[n_, k_] := Binomial[n + k, n]; Table[t[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-François Alcover, Aug 12 2013 *)

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

for n in (0..9):
    print([multinomial(n, k) for k in (0..n)]) # Peter Luschny, Dec 24 2020

T(n,k) = A092392(n,n-k), k = 0..n. - Reinhard Zumkeller, Jul 27 2012
T(n,k) = A178300(n,k), n>0, k = 1..n. - L. Edson Jeffery, Jul 23 2014
T(n,k) = (n + 1)*hypergeom([-n, 1 - k], [2], 1). - Peter Luschny, Jan 09 2022
T(n,k) = hypergeom([-n, -k], [1], 1). - Peter Luschny, Mar 21 2024
G.f.: 1/((1-2x*y*C(x*y))*(1-x*C(x*y))), where C(x) is the g.f. for A000108, the Catalan numbers. - Michael D. Weiner, Jul 31 2024

More terms from James Sellers

A084771 Coefficients of expansion of 1/sqrt(1 - 10x + 9x^2); also, a(n) is the central coefficient of (1 + 5x + 4x^2)^n.

Original entry on oeis.org

1, 5, 33, 245, 1921, 15525, 127905, 1067925, 9004545, 76499525, 653808673, 5614995765, 48416454529, 418895174885, 3634723102113, 31616937184725, 275621102802945, 2407331941640325, 21061836725455905, 184550106298084725

Offset: 0

Paul D. Hanna, Jun 10 2003

Also number of paths from (0,0) to (n,0) using steps U=(1,1), H=(1,0) and D=(1,-1), the U steps come in four colors and the H steps come in five colors. - N-E. Fahssi, Mar 30 2008
Number of lattice paths from (0,0) to (n,n) using steps (1,0), (0,1), and three kinds of steps (1,1). - Joerg Arndt, Jul 01 2011
Sums of squares of coefficients of (1+2*x)^n. - Joerg Arndt, Jul 06 2011
The Hankel transform of this sequence gives A103488. - Philippe Deléham, Dec 02 2007
Partial sums of A085363. - J. M. Bergot, Jun 12 2013
Diagonal of rational functions 1/(1 - x - y - 3*x*y), 1/(1 - x - y*z - 3*x*y*z). - Gheorghe Coserea, Jul 06 2018

			G.f.: 1/sqrt(1-2*b*x+(b^2-4*c)*x^2) yields central coefficients of (1+b*x+c*x^2)^n.

Seiichi Manyama, Table of n, a(n) for n = 0..1000 (terms 0..200 from Vincenzo Librandi)
Tewodros Amdeberhan, In search of multiple expressions for a sequence
Paul Barry and Aoife Hennessy, Generalized Narayana Polynomials, Riordan Arrays, and Lattice Paths, Journal of Integer Sequences, Vol. 15, 2012, #12.4.8.
Hacène Belbachir and Abdelghani Mehdaoui, Recurrence relation associated with the sums of square binomial coefficients, Quaestiones Mathematicae (2021) Vol. 44, Issue 5, 615-624.
Hacène Belbachir, Abdelghani Mehdaoui, and László Szalay, Diagonal Sums in the Pascal Pyramid, II: Applications, J. Int. Seq., Vol. 22 (2019), Article 19.3.5.
Curtis Greene, Posets of shuffles, Journal of Combinatorial Theory, Series A 47.2 (1988): 191-206. See Eq. (30).
Christopher Huffaker, Nathan McCue, Cameron N. Miller, and Kayla S. Miller, The M&M Game: From Morsels to Modern Mathematics, arXiv:1508.06542 [math.HO], 2015.
Greg Morrow, Some probability distributions and integer sequences related to rook paths, Univ. Colorado Springs (2024). See p. 3.
Tony D. Noe, On the Divisibility of Generalized Central Trinomial Coefficients, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.7.
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.
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.

Cf. A001850, A059231, A059304, A246923 (a(n)^2).

List([0..20],n->Sum([0..n],k->Binomial(n,k)^2*4^k)); # Muniru A Asiru, Jul 29 2018

[3^n*Evaluate(LegendrePolynomial(n), 5/3) : n in [0..40]]; // G. C. Greubel, May 30 2023

seq(simplify(hypergeom([-n,1/2], [1], -8)),n=0..19); # Peter Luschny, Apr 26 2016

Table[n! SeriesCoefficient[E^(5 x) BesselI[0, 4 x], {x, 0, n}], {n, 0, 30}] (* Vincenzo Librandi, May 10 2013 *)
Table[Hypergeometric2F1[-n, -n, 1, 4], {n,0,30}] (* Vladimir Reshetnikov, Nov 29 2013 *)
CoefficientList[Series[1/Sqrt[1-10x+9x^2],{x,0,30}],x] (* Harvey P. Dale, Mar 08 2016 *)
Table[3^n*LegendreP[n, 5/3], {n, 0, 40}] (* G. C. Greubel, May 30 2023 *)

{a(n) = if( n<0, -3 * 9^n * a(-1-n), sum(k=0,n, binomial(n, k)^2 * 4^k))}; /* Michael Somos, Oct 08 2003 */

{a(n) = if( n<0, -3 * 9^n * a(-1-n), polcoeff((1 + 5*x + 4*x^2)^n, n))}; /* Michael Somos, Oct 08 2003 */

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

a(n)={local(v=Vec((1+2*x)^n));sum(k=1,#v,v[k]^2);} /* Joerg Arndt, Jul 06 2011 */

a(n)={local(v=Vec((1+2*I*x)^n)); sum(k=1,#v, real(v[k])^2+imag(v[k])^2);} /* Joerg Arndt, Jul 06 2011 */

[3^n*gen_legendre_P(n, 0, 5/3) for n in range(41)] # G. C. Greubel, May 30 2023

G.f.: 1 / sqrt(1 - 10*x + 9*x^2).
From Vladeta Jovovic, Aug 20 2003: (Start)
Binomial transform of A059304.
G.f.: Sum_{k >= 0} binomial(2*k,k)*(2*x)^k/(1-x)^(k+1).
E.g.f.: exp(5*x)*BesselI(0, 4*x). (End)
a(n) = Sum_{k = 0..n} Sum_{j = 0..n-k} C(n,j)*C(n-j,k)*C(2*n-2*j,n-j). - Paul Barry, May 19 2006
a(n) = Sum_{k = 0..n} 4^k*C(n,k)^2. - heruneedollar (heruneedollar(AT)gmail.com), Mar 20 2010
a(n) ~ 3^(2*n+1)/(2*sqrt(2*Pi*n)). - Vaclav Kotesovec, Sep 11 2012
D-finite with recurrence: n*a(n) = 5*(2*n-1)*a(n-1) - 9*(n-1)*a(n-2). - R. J. Mathar, Nov 26 2012
a(n) = hypergeom([-n, -n], [1], 4). - Vladimir Reshetnikov, Nov 29 2013
a(n) = hypergeom([-n, 1/2], [1], -8). - Peter Luschny, Apr 26 2016
From Michael Somos, Jun 01 2017: (Start)
a(n) = -3 * 9^n * a(-1-n) for all n in Z.
0 = a(n)*(+81*a(n+1) -135*a(n+2) +18*a(n+3)) +a(n+1)*(-45*a(n+1) +100*a(n+2) -15*a(n+3)) +a(n+2)*(-5*a(n+2) +a(n+3)) for all n in Z. (End)
From Peter Bala, Nov 13 2022: (Start)
1 + x*exp(Sum_{n >= 1} a(n)*x^n/n) = 1 + x + 5*x^2 + 29*x^3 + 185*x^4 + 1257*x^5 + ... is the g.f. of A059231.
The Gauss congruences hold: a(n*p^r) == a(n*p^(r-1)) (mod p^r) for all positive integers n and r and all primes p. (End)
a(n) = 3^n * LegendreP(n, 5/3). - G. C. Greubel, May 30 2023
a(n) = (1/4)^n * Sum_{k=0..n} 9^k * binomial(2*k,k) * binomial(2*(n-k),n-k). - Seiichi Manyama, Aug 18 2025

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

A001850 Central Delannoy numbers: a(n) = Sum_{k=0..n} C(n,k)*C(n+k,k).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Maxima

PARI

PARI

PARI

PARI

PARI

PARI

PARI

Python

Python

Sage

Formula

Extensions

A026641 Number of nodes of even outdegree (including leaves) in all ordered trees with n edges.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

PARI

Sage

Formula

A013609 Triangle of coefficients in expansion of (1+2*x)^n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Haskell

Magma

Maple