A076540 -id:A076540 - cp's OEIS frontend

A001791 a(n) = binomial coefficient C(2n, n-1).

0, 1, 4, 15, 56, 210, 792, 3003, 11440, 43758, 167960, 646646, 2496144, 9657700, 37442160, 145422675, 565722720, 2203961430, 8597496600, 33578000610, 131282408400, 513791607420, 2012616400080, 7890371113950, 30957699535776, 121548660036300, 477551179875952

Offset: 0

N. J. A. Sloane

Number of peaks at even level in all Dyck paths of semilength n+1. Example: a(2)=4 because UDUDUD, UDUU*DD, UU*DDUD, UU*DU*DD, UUUDDD, where U=(1,1), D=(1,-1) and the peaks at even level are shown by *. - Emeric Deutsch, Dec 05 2003
Also number of long ascents (i.e., ascents of length at least two) in all Dyck paths of semilength n+1. Example: a(2)=4 because in the five Dyck paths of semilength 3, namely UDUDUD, UD(UU)DD, (UU)DDUD, (UU)DUDD and (UUU)DDD, we have four long ascents (shown between parentheses). Here U=(1,1) and D=(1,-1). Also number of branch nodes (i.e., vertices of outdegree at least two) in all ordered trees with n+1 edges. - Emeric Deutsch, Feb 22 2004
Number of lattice paths from (0,0) to (n,n) with steps E=(1,0) and N=(0,1) which touch or cross the line x-y=1. Example: For n=2 these are the paths EENN, ENEN, ENNE and NEEN. - Herbert Kociemba, May 23 2004
Narayana transform (A001263) of [1, 3, 5, 7, 9, ...] = (1, 4, 15, 56, 210, ...). Row sums of triangles A136534 and A136536. - Gary W. Adamson, Jan 04 2008
Starting with offset 1 = the Catalan sequence starting (1, 2, 5, 14, ...) convolved with A000984: (1, 2, 6, 20, ...). - Gary W. Adamson, May 17 2009
Also number of peaks plus number of valleys in all Dyck n-paths. - David Scambler, Oct 08 2012
Apparently counts UDDUD in all Dyck paths of semilength n+2. - David Scambler, Apr 22 2013
Apparently the number of peaks strictly left of the midpoint in all Dyck paths of semilength n+1. - David Scambler, Apr 30 2013
For n>0, a(n) is the number of compositions of n into at most n parts if zeros are allowed as parts (so-called "weak" compositions). - L. Edson Jeffery, Jul 24 2014
Number of paths in the half-plane x >= 0, from (0,0) to (2n,2), and consisting of steps U=(1,1) and D=(1,-1). For example, for n=2, we have the 4 paths: UUUD, UUDU, UDUU, DUUU. - José Luis Ramírez Ramírez, Apr 19 2015
For n>1, 1/a(n) is the probability that when a stick is broken up at n points independently and uniformly chosen at random along its length any triple of pieces of the n+1 pieces can form a triangle. The corresponding probability for the existence of at least one triple is A339392(n)/A339393(n). - Amiram Eldar, Dec 04 2020
a(n) is the number of lattice paths of 2n steps taken from the step set {U=(1,1), D=(1,-1)} that start at the origin, never go below the x-axis, and end strictly above the x-axis; more succinctly, proper left factors of Dyck paths. For example, a(2)=4 counts UUUU, UUUD, UUDU, UDUU. - David Callan and Emeric Deutsch, Jan 25 2021
From Gus Wiseman, Jul 21 2021: (Start)
Also the number of integer compositions of 2n+1 with alternating sum -1, where the alternating sum of a sequence (y_1,...,y_k) is Sum_i (-1)^(i-1) y_i. For example, the a(1) = 1 through a(3) = 15 compositions are:
  (1,2)  (2,3)      (3,4)
         (1,3,1)    (1,4,2)
         (1,1,1,2)  (2,4,1)
         (1,2,1,1)  (1,1,2,3)
                    (1,2,2,2)
                    (1,3,2,1)
                    (2,1,1,3)
                    (2,2,1,2)
                    (2,3,1,1)
                    (1,1,1,3,1)
                    (1,2,1,2,1)
                    (1,3,1,1,1)
                    (1,1,1,1,1,2)
                    (1,1,1,2,1,1)
                    (1,2,1,1,1,1)
The following relate to these compositions.
- The unordered version is A000070.
- Allowing any negative alternating sum gives A000346.
- The opposite (positive 1) version is A000984.
- The version for reverse-alternating sum is also A001791 (this sequence).
- Taking alternating sum -2 instead of -1 gives A002054.
- The shifted version for alternating sum 0 is counted by A088218 and ranked by A344619.
- Ranked by A345910 (reverse: A345912).
Equivalently, a(n) counts binary numbers with 2n+1 digits and one more 0 than 1's. For example, the a(2) = 4 binary numbers are: 10001, 10010, 10100, 11000.
(End)
The diagonal of a square n X n matrix where cells of the first row are the nonnegative integers and cells of subsequent rows are sums of cells of the previous row up to and including n. - Torlach Rush, Apr 24 2024
For n>=1, a(n) is the independence number of the odd graph O_{n+1}. - Miquel A. Fiol, Jul 07 2024

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 828.
Cornelius Lanczos, Applied Analysis, Prentice-Hall, Englewood Cliffs, NJ, 1956, p. 517.
R. C. Mullin, E. Nemeth and P. J. Schellenberg, The enumeration of almost cubic maps, pp. 281-295 in Proceedings of the Louisiana Conference on Combinatorics, Graph Theory and Computer Science. Vol. 1, edited R. C. Mullin et al., 1970.
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).

T. D. Noe and Matuszka Tamás, Table of n, a(n) for n = 0..1200 (terms n = 0..200 from T. D. Noe)
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].
Anwar Al Ghabra, K. Gopala Krishna, Patrick Labelle, and Vasilisa Shramchenko, Enumeration of multi-rooted plane trees, arXiv:2301.09765 [math.CO], 2023.
Jean-Luc Baril and Sergey Kirgizov, The pure descent statistic on permutations, Discrete Mathematics, Vol. 340, No. 10 (2017), pp. 2550-2558; preprint, 2016.
Paul Barry, A Catalan Transform and Related Transformations on Integer Sequences, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.5.
Paul Barry, On the Hurwitz Transform of Sequences, Journal of Integer Sequences, Vol. 15 (2012), #12.8.7.
Norman Biggs, Some odd graph theory, Second International Conference on Combinatorial Mathematics, Annals of the New York Academy of Sciences 319 (1979), 71-81.
Miklós Bóna, Surprising Symmetries in Objects Counted by Catalan Numbers, Electronic J. Combin., 19 (2012), P62, eq. (6).
Libor Caha and Daniel Nagaj, The pair-flip model: a very entangled translationally invariant spin chain, arXiv:1805.07168 [quant-ph], 2018.
Jelena Đokic, A short note on the order of the double reduced 2-factor transfer digraph for rectangular grid graphs, arXiv:2308.04155 [math.CO], 2023.
Ricardo Gómez Aíza, Trees with flowers: A catalog of integer partition and integer composition trees with their asymptotic analysis, arXiv:2402.16111 [math.CO], 2024. See p. 21.
Guo-Niu Han, Enumeration of Standard Puzzles.
Guo-Niu Han, Enumeration of Standard Puzzles. [Cached copy]
A. Ivanyi, L. Lucz, T. Matuszka, and S. Pirzada, Parallel enumeration of degree sequences of simple graphs, Acta Univ. Sapientiae, Informatica, 4, 2 (2012) 260-288.
Milan Janjic, Two Enumerative Functions.
Milan Janjic and Boris Petkovic, A Counting Function, arXiv preprint arXiv:1301.4550 [math.CO], 2013.
Milan Janjic and Boris Petkovic, A Counting Function Generalizing Binomial Coefficients and Some Other Classes of Integers, J. Int. Seq., Vol. 17 (2014), Article 14.3.5.
Christian Krattenthaler and Daniel Yaqubi, Some determinants of path generating functions, II, Advances in Applied Mathematics, Vol. 101 (2018), pp. 232-265; arXiv preprint, arXiv:1802.05990 [math.CO], 2018.
Cornelius Lanczos, Applied Analysis. (Annotated scans of selected pages)
Asamoah Nkwanta and Earl R. Barnes, Two Catalan-type Riordan Arrays and their Connections to the Chebyshev Polynomials of the First Kind, Journal of Integer Sequences, Vol. 15 (2012), Article 12.3.3. - From _N. J. A. Sloane_, Sep 16 2012
Mark Shattuck, Enumeration of non-crossing partitions according to subwords with repeated letters, arXiv:2303.06300 [math.CO], 2023.
Zhi Lan Wang, Tautological integrals on symmetric products of curves, Acta Mathematica Sinica, English Series, Vol. 32, No. 8 (2016), pp. 901-910; arXiv preprint, arXiv:1506.08405 [math.AG], 2015-2016; alternative link.
Jian Zhou, Fat and Thin Emergent Geometries of Hermitian One-Matrix Models, arXiv:1810.03883 [math-ph], 2018.

Diagonal 3 of triangle A100257.
First differences are in A076540.
Cf. A000108, A000984, A002378, A002390, A025566, A132812.
A345197 counts compositions by length and alternating sum.
Cf. A000070, A000302, A000346, A002054, A008549, A032443, A088218, A097805, A163493, A202736, A345910.

List([0..30],n->Binomial(2*n,n-1)); # Muniru A Asiru, Aug 09 2018

[Binomial(2*n, n-1): n in [0..30]]; // Vincenzo Librandi, Apr 20 2015

Table[Binomial[2n,n-1],{n,0,30}] (* Harvey P. Dale, Jul 12 2012 *)
CoefficientList[ Series[(1 - 2x - Sqrt[1 - 4x])/(2x*Sqrt[1 - 4x]), {x, 0, 26}], x] (* Robert G. Wilson v, Aug 10 2018 *)

A001791(n):=binomial(2*n,n-1)$
makelist(A001791(n),n,0,30); /* Martin Ettl, Nov 05 2012 */

PARI
```
a(n)=if(n<1,0,(2*n)!/(n+1)!/(n-1)!)
```

a(n) = n*A000108(n).
G.f.: x*(d/dx)c(x) where c(x) = Catalan g.f. - Wolfdieter Lang
Convolution of A001700 (central binomial of odd order) and A000108 (Catalan): a(n+1) = Sum_{k=0..n} C(k)*binomial(2*(n-k)+1, n-k), C(k): Catalan. - Wolfdieter Lang
E.g.f.: exp(2x) * I_1(2x), where I_1 is Bessel function. - Michael Somos, Sep 08 2002
a(n) = Sum_{k=0..n} C(n, k)*C(n, k+1). - Paul Barry, May 15 2003
a(n) = Sum_{i=1..n} binomial(i+n-1, n).
G.f.: (1-2x-sqrt(1-4x))/(2x*sqrt(1-4x)). - Emeric Deutsch, Dec 05 2003
a(n) = A092956/(n!). - Amarnath Murthy, Jun 16 2004
a(n) = binomial(2n,n) - A000108(n). - Paul Barry, Apr 21 2005
a(n) = (1/(2*Pi))*Integral_{x=0..4} (x^n*(x-2)/sqrt(x(4-x))) is the moment sequence representation. - Paul Barry, Jan 11 2007
Row sums of triangle A132812 starting (1, 4, 15, 56, 210, ...). - Gary W. Adamson, Sep 01 2007
Starting (1, 4, 15, 56, 210, ...) gives the binomial transform of A025566 starting (1, 3, 8, 22, 61, 171, ...). - Gary W. Adamson, Sep 01 2007
For n >= 1, a(2^n) = 2^(n+1)*A001795(2^(n-1)). - Vladimir Shevelev, Sep 05 2010
D-finite with recurrence: (n-1)*(n+1)*a(n) = 2*n*(2n-1)*a(n-1). - R. J. Mathar, Dec 17 2011
From Sergei N. Gladkovskii, Jul 07 2012: (Start)
G.f.: -1/(2*x) - G(0) where G(k) = 1 - 1/(2*x - 8*x^3*(2*k+1)/(4*x^2*(2*k+1)- (k+1)/G(k+1))); (continued fraction, 3rd kind, 3-step);
E.g.f.: BesselI(1,2*x)*exp(2*x) = x*G(0) where G(k) = 1 + 2*x*(4*k+3)/((2*k+1)*(2*k+3) - x*(2*k+1)*(2*k+3)*(4*k+5)/(x*(4*k+5) + 2*(k+1)*(k+2)/G(k+1))); (continued fraction, 3rd kind, 3-step).
(End)
G.f.: c(x)^3/(2-c(x)) where c(x) is the g.f. for A000108. - Cheyne Homberger, May 05 2014
G.f.: z*C(z)^2/(1-2*z*C(z)), where C(z) is the g.f. of Catalan numbers. - José Luis Ramírez Ramírez, Apr 19 2015
G.f.: x*2F1(3/2,2;3;4x). - R. J. Mathar, Aug 09 2015
a(n) = Sum_{i=1..n} binomial(2*i-2,i-1)*binomial(2*(n-i+1),n-i+2)/(n-i+1). - Vladimir Kruchinin, Sep 07 2015
L.g.f.: 1/(1 - x/(1 - x/(1 - x/(1 - x/(1 - x/(1 - ...)))))) = Sum_{n>=1} a(n)*x^n/n. - Ilya Gutkovskiy, May 10 2017
Sum_{n>=1} 1/a(n) = 1/3 + 5*Pi/(9*sqrt(3)). - Amiram Eldar, Dec 04 2020
Sum_{n>=1} (-1)^(n+1)/a(n) = 1/5 + 14*sqrt(5)*log(phi)/25, where log(phi) = A002390. - Amiram Eldar, Feb 20 2021
a(n) = Product_{i=1..(n - 1)} (((4*i + 6)*i + 2)/((i + 2)*i)), for n>=1. - Neven Sajko, Oct 10 2021
a(n) = 2^(2*n)*gamma(n + 1/2)/(sqrt(Pi)*gamma(n)*(n+1)) for n > 0, and a(0) = lim_{n->0} a(n). - Karol A. Penson, Apr 24 2025

A005717 Construct triangle in which n-th row is obtained by expanding (1 + x + x^2)^n and take the next-to-central column.

Original entry on oeis.org

1, 2, 6, 16, 45, 126, 357, 1016, 2907, 8350, 24068, 69576, 201643, 585690, 1704510, 4969152, 14508939, 42422022, 124191258, 363985680, 1067892399, 3136046298, 9217554129, 27114249960, 79818194925, 235128465026, 693085098852, 2044217638456, 6032675068061

Offset: 1

N. J. A. Sloane

Number of ordered trees with n+1 edges, having root of even degree and nonroot nodes of outdegree at most 2. - Emeric Deutsch, Aug 02 2002
The connection to Motzkin numbers comes from the Lagrange inversion formula. - Michael Somos, Oct 10 2003
Number of horizontal steps in all Motzkin paths of length n. - Emeric Deutsch, Nov 09 2003
Number of UHD's in all Motzkin paths of length n+2 (here U=(1,1), H=(1,0) and D=(1,-1)). Example: a(2)=2 because in the nine Motzkin paths of length 4, HHHH, HHUD, HUDH, H(UHD), UDHH, UDUD, (UHD)H, UHHD and UUDD, we have altogether two UHD's (shown between parentheses). - Emeric Deutsch, Dec 26 2003
Number of ordered trees with n+1 edges, having exactly one leaf at even height. Number of Dyck path of semilength n+1, having exactly one peak at even height. Example: a(3)=6 because we have uuu(ud)ddd, u(ud)dudud, udu(ud)dud, ududu(ud)d, u(ud)uuddd and uuudd(ud)d (here u=(1,1),d=(1,-1) and the unique peak at even height is shown between parentheses). - Emeric Deutsch, Mar 10 2004
a(n) is the number of Dyck (n+1)-paths containing exactly one UDU. - David Callan, Jul 15 2004
Number of peaks in all Motzkin paths of length n+1. - Emeric Deutsch, Sep 01 2004
This is a kind of Motzkin transform of A059841 because the substitution x -> x*A001006(x) in the independent variable of the g.f. of A059841 generates 1,0,1,2,6,16,... that is 1,0 followed by this sequence here. - R. J. Mathar, Nov 08 2008
a(n) is the number of lattice paths avoiding N^(>=3) from (0,0) to (n,n). - Shanzhen Gao, Apr 20 2010
a(n+1) is the number of binary strings having n 0's and n 1's and no appearance of 000.  For example, for n = 1, there 2 strings: 01 and 10.  For n = 2, there are 6: 0011, 0101, 0110, 1001, 1010, 1100. - Toby Gottfried, Sep 12 2011
a(n) is the number of paths in the half-plane x>=0, from (0,0) to (n,1), and consisting of steps U=(1,1), D=(1,-1) and H=(1,0). For example, for n=3, we have the 6 paths HHU, HUH, UDU, UUD, UHH, DUU. - José Luis Ramírez Ramírez, Apr 19 2015
a(n) is the number of ways to tile a strip of length 2*n+1 with squares, dominos, and trominos, where the number of trominos is always one more than the number of squares. - Greg Dresden and Anna Kalynchuk, Jul 30 2025

			G.f. = x + 2*x^2 + 6*x^3 + 16*x^4 + 45*x^5 + 126*x^6 + 357*x^7 + ...

Louis Comtet, Advanced Combinatorics, Reidel, 1974, p. 78.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

G. C. Greubel, Table of n, a(n) for n = 1..1000 (Terms 1 to 200 computed by T. D. Noe; terms 201 to 1000 by G. C. Greubel, Jan 15 2017)
Kassie Archer and Christina Graves, A new statistic on Dyck paths for counting 3-dimensional Catalan words, arXiv:2205.09686 [math.CO], 2022.
Jean-Luc Baril, Sergey Kirgizov, José L. Ramírez, and Diego Villamizar, The Combinatorics of Motzkin Polyominoes, arXiv:2401.06228 [math.CO], 2024. See page 13.
Emeric Deutsch, Ordered trees with prescribed root degrees, node degrees, and branch lengths, Discrete Mathematics 282 (2004), 89-94.
Ricardo Gómez Aíza, Trees with flowers: A catalog of integer partition and integer composition trees with their asymptotic analysis, arXiv:2402.16111 [math.CO], 2024. See p. 23.
Richard K. Guy, Letter to N. J. A. Sloane, 1987.
Stanislav Krymski and Alexander Okhotin, Longer Shortest Strings in Two-Way Finite Automata, in: Jirásková G., Pighizzini G. (eds) Descriptional Complexity of Formal Systems. DCFS 2020. Lecture Notes in Computer Science, vol 12442. Springer, Cham.
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, Une méthode pour obtenir la fonction génératrice d'une série, arXiv:0912.0072 [math.NT], 2009; FPSAC 1993, Florence. Formal Power Series and Algebraic Combinatorics.
Mark Shattuck, Subword Patterns in Smooth Words, Enum. Comb. Appl. (2024) Vol. 4, No. 4, Art. No. S2R32. See p. 6.
Chenying Wang, Piotr Miska, and István Mező, The r-derangement numbers, Discrete Mathematics 340(7) (2017), 1681-1692.
Eric Weisstein's World of Mathematics, Trinomial Coefficient.

A diagonal of A027907.

Cf. A001006, A002426, A005043, A005773, A076540 (binomial transform).

seq(add(binomial(i, k) *binomial(i-k, k+1), k=0..floor(i/2)), i=1..30); # Detlef Pauly (dettodet(AT)yahoo.de), Nov 09 2001
M:= proc(n) option remember; `if` (n<2, 1, (3*(n-1)*M(n-2) +(2*n+1) *M(n-1))/ (n+2)) end: A005717 := n -> n*M(n-1):
seq(A005717(i), i=1..27); # Peter Luschny, Sep 12 2011
a := n -> simplify(GegenbauerC(n,-n-1,-1/2)):
seq(a(n), n=0..28); # Peter Luschny, May 07 2016

Table[Coefficient[Expand[(1+x+x^2)^n], x, n-1], {n, 1, 40}]
Table[n*Hypergeometric2F1[(1 - n)/2, 1 - n/2, 2, 4], {n, 29}] (* Arkadiusz Wesolowski, Aug 13 2012 *)
Table[GegenbauerC[n,-n-1,-1/2],{n,0,100}] (* Emanuele Munarini, Oct 20 2016 *)

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

{a(n) = if( n<0, 0, polcoeff( (1 + x + x^2)^n, n-1))}; /* Michael Somos, Sep 09 2002 */

{a(n) = if( n<0, 0, n * polcoeff( serreverse( x / (1 + x + x^2) + x * O(x^n)), n))}; /* Michael Somos, Oct 10 2003 */

N=10^3;  x='x+'x*O('x^N);
gf = 2*x/(1-2*x-3*x^2+(1-x)*sqrt(1-2*x-3*x^2));
v005717 = Vec(gf);
/* Joerg Arndt, Aug 16 2012 */

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

a(n) = Sum_{k=1..n} T(k, k-1), where T is the array defined in A025177.
G.f.: 2*x/(1-2*x-3*x^2+(1-x)*sqrt(1-2*x-3*x^2)). - Emeric Deutsch, Aug 14 2002
E.g.f.: exp(x) * I_1(2x), where I_1 is the Bessel function. - Michael Somos, Sep 09 2002
a(n) = A111808(n,n-1). - Reinhard Zumkeller, Aug 17 2005
a(n) = Sum_{k=0..floor((n-1)/3)} (-1)^k * binomial(n,k) * binomial(2n-2-3k, n-1). - David Callan, Jul 03 2006
From Paul Barry, Feb 05 2007: (Start)
a(n) = n*Sum_{k=0..floor((n-1)/2), C(n-1,2k)*C(k)}, C(n) = A000108(n).
a(n) = Sum_{k=0..floor((n-1)/2)} (2k+1)*C(n,2k+1)*C(k).
a(n) = Sum_{k=0..n-1} ( Sum_{j=0..floor(k/2)} C(k,2j)*C(2j+1,j) ). (End)
a(n) = (A002426(n+1) - A002426(n))/2. - Paul Barry, May 22 2008
a(n) = n*A001006(n-1). - Paul Barry, Oct 05 2009
a(n) = Sum_{i=0..floor(n/2)} C(n+1,n-i) * C(n-i,i). - Shanzhen Gao, Apr 20 2010
D-finite with recurrence: (n+1)*a(n) - 3*n*a(n-1) - (n+3)*a(n-2) + 3*(n-2)*a(n-3) = 0. - R. J. Mathar, Nov 28 2011
a(n) ~ 3^(n+1/2)/(2*sqrt(Pi*n)). - Vaclav Kotesovec, Aug 09 2013
0 = a(n) * 3*(n+1)*(n+2) + a(n+1) * (n+2)*(2*n+3) - a(n+2) * (n+1)*(n+3) for all n in Z. - Michael Somos, Apr 03 2014
G.f.: z*M(z)/(1-z-2*z^2*M(z)), where M(z) is the g.f. of Motzkin paths. - José Luis Ramírez Ramírez, Apr 19 2015
Working with an offset of 0, a(n) = [x^n](1 + x + x^2)^(n+1); binomial transform is A076540. - Peter Bala, Jun 15 2015
a(n) = GegenbauerC(n,-n-1,-1/2). - Peter Luschny, May 07 2016
a(n) = (-1)^(n+1) * n * hypergeom([3/2, 1-n], [3], 4). - Vladimir Reshetnikov, Sep 28 2016
a(n) = Sum_{k=0..n-1} binomial(n,k)*binomial(n-k, k+1) [Krymski and Okhotin]. - Michel Marcus, Dec 04 2020
a(n) = (1/2)*(A005773(n+1) - A005043(n)). - Peter Bala, Feb 11 2022
a(n) = A002426(n) - A005043(n). - Amiram Eldar, May 17 2024

More terms from Erich Friedman, Jun 01 2001

A051924 a(n) = binomial(2n,n) - binomial(2n-2,n-1); or (3n-2)*C(n-1), where C = Catalan numbers (A000108).

Original entry on oeis.org

1, 4, 14, 50, 182, 672, 2508, 9438, 35750, 136136, 520676, 1998724, 7696444, 29716000, 115000920, 445962870, 1732525830, 6741529080, 26270128500, 102501265020, 400411345620, 1565841089280, 6129331763880, 24014172955500, 94163002754652, 369507926510352

Offset: 1

Barry E. Williams, Dec 19 1999

Number of partitions with Ferrers plots that fit inside an n X n box, but not in an n-1 X n-1 box. - Wouter Meeussen, Dec 10 2001
From Benoit Cloitre, Jan 29 2002: (Start)
Let m(1,j)=j, m(i,1)=i and m(i,j) = m(i-1,j) + m(i,j-1); then a(n) = m(n,n):
  1  2  3  4 ...
  2  4  7 11 ...
  3  7 14 25 ...
  4 11 25 50 ... (End)
This sequence also gives the number of clusters and non-crossing partitions of type D_n. - F. Chapoton, Jan 31 2005
If Y is a 2-subset of a 2n-set X then a(n) is the number of (n+1)-subsets of X intersecting Y. - Milan Janjic, Nov 18 2007
Prefaced with a 1: (1, 1, 4, 14, 50, ...) and convolved with the Catalan sequence = A097613: (1, 2, 7, 25, 91, ...). - Gary W. Adamson, May 15 2009
Total number of up steps before the second return in all Dyck n-paths. - David Scambler, Aug 21 2012
Conjecture: a(n) mod n^2 = n+2 iff n is an odd prime. - Gary Detlefs, Feb 19 2013
First differences of A000984 and A030662. - J. M. Bergot, Jun 22 2013
From R. J. Mathar, Jun 30 2013: (Start)
Equivalent to the Meeussen comment and the Bergot comment: The array view of A007318 is
  1,   1,   1,   1,   1,   1,
  1,   2,   3,   4,   5,   6,
  1,   3,   6,  10,  15,  21,
  1,   4,  10,  20,  35,  56,
  1,   5,  15,  35,  70, 126,
  1,   6,  21,  56, 126, 252,
and a(n) are the hook sums Sum_{k=0..n} A(n,k) + Sum_{r=0..n-1} A(r,n). (End)
From Gus Wiseman, Apr 12 2019: (Start)
Equivalent to Wouter Meeussen's comment, a(n) is the number of integer partitions (of any positive integer) such that the maximum of the length and the largest part is n. For example, the a(1) = 1 through a(3) = 14 partitions are:
  (1)  (2)   (3)
       (11)  (31)
       (21)  (32)
       (22)  (33)
             (111)
             (211)
             (221)
             (222)
             (311)
             (321)
             (322)
             (331)
             (332)
             (333)
(End)
Coxeter-Catalan numbers for Coxeter groups of type D_n [Armstrong]. - N. J. A. Sloane, Mar 09 2022
a(n+1) is the number of ways that a best of n pairs contest with early termination can go. For example, the first stage of an association football (soccer) penalty-kick shoot out has n=5 pairs of shots and there are a(6)=672 distinct ways it can go. For n=2 pairs, writing G for goal and M for miss, and listing the up-to-four shots in chronological order with teams alternating shots, the n(3)=14 possibilities are MMMM, MMMG, MMGM, MMGG, MGM, MGGM, MGGG, GMMM, GMMG, GMG, GGMM, GGMG, GGGM, and GGGG. Not all four shots are taken in two cases because it becomes impossible for one team to overcome the lead of the other team. - Lee A. Newberg, Jul 20 2024

			Sums of {1}, {2, 1, 1}, {2, 2, 3, 3, 2, 1, 1}, {2, 2, 4, 5, 7, 6, 7, 5, 5, 3, 2, 1, 1}, ...

Drew Armstrong, Generalized Noncrossing Partitions and Combinatorics of Coxeter Groups, Mem. Amer. Math. Soc. 202 (2009), no. 949, x+159. MR 2561274 16; See Table 2.8.

Reinhard Zumkeller, Table of n, a(n) for n = 1..1000
Drew Armstrong, Generalized Noncrossing Partitions and Combinatorics of Coxeter Groups, arXiv:math/0611106 [math.CO], 2006-2007.
Jean-Luc Baril, Pamela E. Harris, Kimberly J. Harry, Matt McClinton, and José L. Ramírez, Enumerating runs, valleys, and peaks in Catalan words, arXiv:2404.05672 [math.CO], 2024. See p. 10.
F. Chapoton, Clusters.
FindStat, St000784: The maximum of the length and the largest part of the integer partition.
Sergey Fomin and Andrei Zelevinsky, Y-systems and generalized associahedra, Ann. of Math. (2) 158 (2003), no. 3, 977-1018.
Joël Gay and Vincent Pilaud, The weak order on Weyl posets, arXiv:1804.06572 [math.CO], 2018.
Milan Janjic, Two Enumerative Functions.
Joshua Marsh and Nathan Williams, Nesting Nonpartitions, J. Int. Seq., Vol. 25 (2022), Article 22.8.8.
Sanjay Moudgalya, Abhinav Prem, Rahul Nandkishore, Nicolas Regnault, and B. Andrei Bernevig, Thermalization and its absence within Krylov subspaces of a constrained Hamiltonian, arXiv:1910.14048 [cond-mat.str-el], 2019.
Hugh Thomas, Tamari Lattices and Non-Crossing Partitions in Types B and D, arXiv:math/0311334 [math.CO], 2003-2005.
Lin Yang and Shengliang Yang, Protected Branches in Ordered Trees, J. Math. Study, Vol. 56, No. 1 (2023), 1-17.

Left-central elements of the (1, 2)-Pascal triangle A029635.
Column sums of A096771.
Cf. A000108, A024482 (diagonal from 2), A076540 (diagonal from 3), A000124 (row from 2), A004006 (row from 3), A006522 (row from 4).
Cf. A128064; first differences of A000984.
Cf. A097613.
Cf. A115720, A252464, A257990, A263297, A325189, A325192, A325193.

a051924 n = a051924_list !! (n-1)
a051924_list = zipWith (-) (tail a000984_list) a000984_list
-- Reinhard Zumkeller, May 25 2013

[Binomial(2*n, n)-Binomial(2*n-2, n-1): n in [1..28]]; // Vincenzo Librandi, Dec 21 2016

C:= n-> binomial(2*n, n)/(n+1): seq((n+1)*C(n)-n*C(n-1), n=1..25); # Emeric Deutsch, Jan 08 2008
Z:=(1-z-sqrt(1-4*z))/sqrt(1-4*z): Zser:=series(Z, z=0, 32): seq(coeff(Zser, z, n), n=1..24); # Zerinvary Lajos, Jan 01 2007
a := n -> 2^(-2+2*n)*GAMMA(-1/2+n)*(3*n-2)/(sqrt(Pi)*GAMMA(1+n)):
seq(simplify(a(n)), n=1..24); # Peter Luschny, Dec 14 2015

Table[Binomial[2n,n]-Binomial[2n-2,n-1],{n,30}] (* Harvey P. Dale, Jan 15 2012 *)

a(n)=binomial(2*n,n)-binomial(2*n-2,n-1) \\ Charles R Greathouse IV, Jun 25 2013

{a(n)=polcoeff((1-x) / sqrt(1-4*x +x*O(x^n)) - 1,n)}
for(n=1,30,print1(a(n),", ")) \\ Paul D. Hanna, Nov 08 2014

{a(n)=polcoeff( sum(m=1, n, x^m * sum(k=0, m, binomial(m, k)^2 * x^k) / (1-x +x*O(x^n))^(2*m)), n)}
for(n=1, 30, print1(a(n), ", ")) \\ Paul D. Hanna, Nov 08 2014

a = lambda n: 2^(-2+2*n)*gamma(n-1/2)*(3*n-2)/(sqrt(pi)*gamma(1+n))
[a(n) for n in (1..120)] # Peter Luschny, Dec 14 2015

G.f.: (1-x) / sqrt(1-4*x) - 1. - Paul D. Hanna, Nov 08 2014
G.f.: Sum_{n>=1} x^n/(1-x)^(2*n) * Sum_{k=0..n} C(n,k)^2 * x^k. - Paul D. Hanna, Nov 08 2014
a(n+1) = binomial(2*n, n) + 2*Sum_{i=0..n-1} binomial(n+i, i) (V's in Pascal's Triangle). - Jon Perry Apr 13 2004
a(n) = n*C(n-1) - (n-1)*C(n-2), where C(n) = A000108(n) = Catalan(n). For example, a(5) = 50 = 5*C(4) - 4*C(3) - 5*14 - 3*5 = 70 - 20. Triangle A128064 as an infinite lower triangular matrix * A000108 = A051924 prefaced with a 1: (1, 1, 4, 14, 50, 182, ...). - Gary W. Adamson, May 15 2009
Sum of 3 central terms of Pascal's triangle: 2*C(2+2*n, n)+C(2+2*n, 1+n). - Zerinvary Lajos, Dec 20 2005
a(n+1) = A051597(2n,n). - Philippe Deléham, Nov 26 2006
The sequence 1,1,4,... has a(n) = C(2*n,n)-C(2*(n-1),n-1) = 0^n+Sum_{k=0..n} C(n-1,k-1)*A002426(k), and g.f. given by (1-x)/(1-2*x-2*x^2/(1-2*x-x^2/(1-2*x-x^2/(1-2*x-x^2/(1-.... (continued fraction). - Paul Barry, Oct 17 2009
a(n) = (3*n-2)*(2*n-2)!/(n*(n-1)!^2) = A001700(n) + A001791(n-1). - David Scambler, Aug 21 2012
D-finite with recurrence: a(n) = 2*(3*n-2)*(2*n-3)*a(n-1)/(n*(3*n-5)). - Alois P. Heinz, Apr 25 2014
a(n) = 2^(-2+2*n)*Gamma(-1/2+n)*(3*n-2)/(sqrt(Pi)*Gamma(1+n)). - Peter Luschny, Dec 14 2015
a(n) ~ (3/4)*4^n*(1-(7/24)/n-(7/128)/n^2-(85/3072)/n^3-(581/32768)/n^4-(2611/262144)/n^5)/sqrt(n*Pi). - Peter Luschny, Dec 16 2015
E.g.f.: ((1 - x)*BesselI(0,2*x) + x*BesselI(1,2*x))*exp(2*x) - 1. - Ilya Gutkovskiy, Dec 20 2016
a(n) = 2 * A097613(n) for n > 1. - Bruce J. Nicholson, Jan 06 2019
Sum_{n>=1} a(n)/8^n = 7/(4*sqrt(2)) - 1. - Amiram Eldar, May 06 2023

Edited by N. J. A. Sloane, May 03 2008, at the suggestion of R. J. Mathar

A099569 Riordan array (((1+x)^2 - x^3)/(1+x)^3, 1/(1+x)).

Original entry on oeis.org

1, -1, 1, 1, -2, 1, -2, 3, -3, 1, 4, -5, 6, -4, 1, -7, 9, -11, 10, -5, 1, 11, -16, 20, -21, 15, -6, 1, -16, 27, -36, 41, -36, 21, -7, 1, 22, -43, 63, -77, 77, -57, 28, -8, 1, -29, 65, -106, 140, -154, 134, -85, 36, -9, 1, 37, -94, 171, -246, 294, -288, 219, -121, 45, -10, 1, -46, 131, -265, 417, -540, 582, -507, 340, -166, 55, -11, 1

Offset: 0

Paul Barry, Oct 22 2004

Inverse matrix of A099567. Row sums are A099570.

			Rows begin as:
    1;
   -1,   1;
    1,  -2,    1;
   -2,   3,   -3,   1;
    4,  -5,    6,  -4,    1;
   -7,   9,  -11,  10,   -5,   1;
   11, -16,   20, -21,   15,  -6,   1;
  -16,  27,  -36,  41,  -36,  21,  -7,  1;
   22, -43,   63, -77,   77, -57,  28, -8,  1;
  -29,  65, -106, 140, -154, 134, -85, 36, -9,  1;

G. C. Greubel, Rows n = 0..50 of the triangle, flattened

Cf. A076540, A099570 (row sums), A099567.

[n eq 0 select 1 else (-1)^(n+k)*(Binomial(n, k) + Binomial(n-1, k+2)): k in [0..n], n in [0..15]]; // G. C. Greubel, Jul 25 2022

C := proc (n, k) if 0 <= k and k <= n then factorial(n)/(factorial(k)*factorial(n-k)) else 0 end if;
end proc:
for n from 0 to 10 do
    seq((-1)^(n+k)*(C(n, n-k) + add((i-2)*C(n-i, n-k-i), i = 3..n)), k = 0..n);
end do; # Peter Bala, Mar 21 2018

T[n_, k_]:= (-1)^(n+k)*(Binomial[n, k] + Binomial[n-1, k+2]);
Table[T[n, k], {n,0,15}, {k,0,n}]//Flatten (* G. C. Greubel, Jul 25 2022 *)

def A099569(n, k): return 1 if (n==0) else (-1)^(n+k)*(binomial(n, k) +binomial(n-1, k+2))
flatten([[A099569(n,k) for k in (0..n)] for n in (0..15)]) # G. C. Greubel, Jul 25 2022

Sum_{k=0..n} T(n, k) = A099570(n).
Columns have g.f. ((1+x)^2 - x^3)/(1+x)^3*(x/(1+x))^k.
T(n,k) = (-1)^(n+k)*(binomial(n, n-k) + Sum_{i = 3..n} (i-2)*binomial(n-i,n-k-i)), for 0 <= k <= n, otherwise 0. - Peter Bala, Mar 21 2018
From G. C. Greubel, Jul 25 2022: (Start)
T(n, k) = (-1)^(n+k)*(binomial(n, k) + binomial(n-1, k+2)), with T(0, k) = 1.
T(2*n-1, n-1) = (-1)^n*A076540(n), n >= 1.
T(n, n-1) = -n. (End)

A073663 Total number of branches of length k (k>=1) in all ordered trees with n+k edges (it is independent of k).

Original entry on oeis.org

1, 2, 8, 30, 113, 428, 1629, 6226, 23881, 91884, 354484, 1370812, 5312058, 20622904, 80196055, 312319530, 1217938665, 4755296460, 18586968840, 72723903780, 284804791230, 1116315593640, 4378929921210, 17189573707956

Offset: 0

Emeric Deutsch, Sep 01 2002

nonn

			a(2)=8 because for n=2 and k=1 (for example), the five ordered trees with n+k=3 edges have altogether 0+3+1+1+3=8 branches of length 1.

G. C. Greubel, Table of n, a(n) for n = 0..1000
J. Riordan, Enumeration of plane trees by branches and endpoints, J. Comb. Theory (A) 19, 1975, 214-222.

First differences of A076540.

Concatenation([1], List([1..30], n-> 3*(3*n^3+2*n^2+n-2)* Binomial(2*n, n)/(2*(n+1)*(n+2)*(2*n-1)))); # G. C. Greubel, Jul 22 2019

[1] cat [3*(3*n^3+2*n^2+n-2)*Catalan(n)/(2*(n+2)*(2*n-1)): n in [1..30]]; // G. C. Greubel, Jul 22 2019

Table[If[n==0, 1, 3*(3*n^3+2*n^2+n-2)*CatalanNumber[n]/(2*(n+2)*(2*n - 1))], {n,0,30}] (* G. C. Greubel, Jul 22 2019 *)

vector(30, n, n--; if(n==0, 1, 3*(3*n^3+2*n^2+n-2)*binomial(2*n, n)/(2*(n+1)*(n+2)*(2*n-1)))) \\ G. C. Greubel, Jul 22 2019

[1]+[3*(3*n^3+2*n^2+n-2)*catalan_number(n)/(2*(n+2)*(2*n-1)) for n in (1..30)] # G. C. Greubel, Jul 22 2019

a(n) = binomial(2n+2, n) - 2*binomial(2n, n-1) + binomial(2n-2, n-2) (n > 0).
a(n) = 3*(3*n^3 + 2*n^2 + n - 2)*binomial(2*n, n)/(2*(n+1)*(n+2)*(2*n-1)) (n > 0).
G.f.: (1-z)^2*C^2/sqrt(1-4z), where C = (1-sqrt(1-4z))/(2z) is the Catalan function.
D-finite with recurrence (n+2)*a(n) +(-7*n-5)*a(n-1) +2*(7*n-8)*a(n-2) +4*(-2*n+7)*a(n-3)=0. - R. J. Mathar, Jul 26 2022

cp's OEIS Frontend

A001791 a(n) = binomial coefficient C(2n, n-1).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

GAP

Magma

Mathematica

Maxima

PARI

Formula

A005717 Construct triangle in which n-th row is obtained by expanding (1 + x + x^2)^n and take the next-to-central column.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Maxima

PARI

PARI

PARI

Python

Formula

Extensions

A051924 a(n) = binomial(2*n,n) - binomial(2*n-2,n-1); or (3n-2)*C(n-1), where C = Catalan numbers (A000108).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

PARI

Sage

Formula

Extensions

A099569 Riordan array (((1+x)^2 - x^3)/(1+x)^3, 1/(1+x)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

SageMath

Formula

A073663 Total number of branches of length k (k>=1) in all ordered trees with n+k edges (it is independent of k).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

GAP

Magma

Mathematica

A051924 a(n) = binomial(2n,n) - binomial(2n-2,n-1); or (3n-2)*C(n-1), where C = Catalan numbers (A000108).