A045621 -id:A045621 - cp's OEIS frontend

A000346 a(n) = 2^(2n+1) - binomial(2n+1, n+1).

1, 5, 22, 93, 386, 1586, 6476, 26333, 106762, 431910, 1744436, 7036530, 28354132, 114159428, 459312152, 1846943453, 7423131482, 29822170718, 119766321572, 480832549478, 1929894318332, 7744043540348, 31067656725032, 124613686513778, 499744650202436

Offset: 0

N. J. A. Sloane, Wolfdieter Lang

Also a(n) = 2nd elementary symmetric function of binomial(n,0), binomial(n,1), ..., binomial(n,n).
Also a(n) = one half the sum of the heights, over all Dyck (n+2)-paths, of the vertices that are at even height and terminate an upstep. For example with n=1, these vertices are indicated by asterisks in the 5 Dyck 3-paths: UU*UDDD, UU*DU*DD, UDUU*DD, UDUDUD, UU*DDUD, yielding a(1)=(2+4+2+0+2)/2=5. - David Callan, Jul 14 2006
Hankel transform is (-1)^n*(2n+1); the Hankel transform of sum(k=0..n, C(2*n,k) ) - C(2n,n) is (-1)^n*n. - Paul Barry, Jan 21 2007
Row sums of the Riordan matrix (1/(1-4x),(1-sqrt(1-4x))/2) (A187926). - Emanuele Munarini, Mar 16 2011
From Gus Wiseman, Jul 19 2021: (Start)
For n > 0, a(n-1) is also the number of integer compositions of 2n with nonzero alternating sum, where the alternating sum of a sequence (y_1,...,y_k) is Sum_i (-1)^(i-1) y_i. These compositions are ranked by A053754 /\ A345921. For example, the a(3-1) = 22 compositions of 6 are:
  (6)  (1,5)  (1,1,4)  (1,1,1,3)  (1,1,1,1,2)
       (2,4)  (1,2,3)  (1,1,3,1)  (1,1,2,1,1)
       (4,2)  (1,4,1)  (1,2,1,2)  (2,1,1,1,1)
       (5,1)  (2,1,3)  (1,3,1,1)
              (2,2,2)  (2,1,2,1)
              (3,1,2)  (3,1,1,1)
              (3,2,1)
              (4,1,1)
(End)

			G.f. = 1 + 5*x + 22*x^2 + 93*x^3 + 386*x^4 + 1586*x^5 + 6476*x^6 + ...

T. Myers and L. Shapiro, Some applications of the sequence 1, 5, 22, 93, 386, ... to Dyck paths and ordered trees, Congressus Numerant., 204 (2010), 93-104.
D. Phulara and L. W. Shapiro, Descendants in ordered trees with a marked vertex, Congressus Numerantium, 205 (2011), 121-128.
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).

Vincenzo Librandi, Table of n, a(n) for n = 0..500
R. Bacher, On generating series of complementary plane trees arXiv:math/0409050 [math.CO], 2004.
Vijay Balasubramanian, Javier M. Magan, and Qingyue Wu, A Tale of Two Hungarians: Tridiagonalizing Random Matrices, arXiv:2208.08452 [hep-th], 2022.
Paul Barry, On a Central Transform of Integer Sequences, arXiv:2004.04577 [math.CO], 2020.
E. A. Bender, E. R. Canfield and R. W. Robinson, The enumeration of maps on the torus and the projective plane, Canad. Math. Bull., 31 (1988), 257-271; see p. 270.
D. E. Davenport, L. K. Pudwell, L. W. Shapiro and L. C. Woodson, The Boundary of Ordered Trees, 2014.
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 185
R. K. Guy, Letter to N. J. A. Sloane
Toufik Mansour and José L. Ramirez, Enumerations of polyominoes determined by Fuss-Catalan words, Australas. J. Combin. 81 (3) (2021) 447-457, table 1.
Mircea Merca, A Special Case of the Generalized Girard-Waring Formula, J. Integer Sequences, Vol. 15 (2012), Article 12.5.7. - From _N. J. A. Sloane_, Nov 25 2012
D. Merlini, R. Sprugnoli and M. C. Verri, Waiting patterns for a printer, FUN with algorithm'01, Isola d'Elba, 2001.
D. Merlini, R. Sprugnoli and M. C. Verri, The tennis ball problem, J. Combin. Theory, A 99 (2002), 307-344 (A_n for s=2).
Vera Posch, Correlators in Matrix Models, Master Thesis, Uppsala Univ. (Sweden 2023). See p. 44.
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.
W. T. Tutte, On the enumeration of planar maps. Bull. Amer. Math. Soc. 74 1968 64-74.
T. R. S. Walsh and A. B. Lehman, Counting rooted maps by genus, J. Comb. Thy B13 (1972), 122-141 and 192-218 (eq. 5, b=1).
N. J. A. Sloane, Notes

Cf. A000108, A014137, A014318. A column of A058893. Subdiagonal of A053979.
Bisection of A058622 and (possibly) A007008.
Cf. A045621, A068551.
Cf. A033504, A038806, A055217, A069731.
Even bisection of A294175 (without the first two terms).
The following relate to compositions of 2n with alternating sum k.
- The k > 0 case is counted by A000302.
- The k <= 0 case is counted by A000302.
- The k != 0 case is counted by A000346 (this sequence).
- The k = 0 case is counted by A001700 or A088218.
- The k < 0 case is counted by A008549.
- The k >= 0 case is counted by A114121.
A011782 counts compositions.
A086543 counts partitions with nonzero alternating sum (bisection: A182616).
A097805 counts compositions by alternating (or reverse-alternating) sum.
A103919 counts partitions by sum and alternating sum (reverse: A344612).
A345197 counts compositions by length and alternating sum.
Cf. A000070, A001791, A007318, A025047, A027306, A032443, A053754, A120452, A163493, A239830, A344611, A345921.

[2^(2*n+1) - Binomial(2*n+1,n+1): n in [0..30]]; // Vincenzo Librandi, Jun 07 2011

seq(2^(2*n+1)-binomial(2*n,n)*(2*n+1)/(n+1), n=0..12); # Emanuele Munarini, Mar 16 2011

Table[2^(2n+1)-Binomial[2n,n](2n+1)/(n+1),{n,0,20}] (* Emanuele Munarini, Mar 16 2011 *)
a[ n_] := If[ n<-4, 0, (4^(n + 1) - Binomial[2 n + 2, n + 1]) / 2]; (* Michael Somos, Jan 25 2014 *)

makelist(2^(2*n+1)-binomial(2*n,n)*(2*n+1)/(n+1),n,0,12); /* Emanuele Munarini, Mar 16 2011 */

{a(n) = if( n<-4, 0, n++; (2^(2*n) - binomial(2*n, n)) / 2)}; /* Michael Somos, Jan 25 2014 */

G.f.: c(x)/(1-4x), c(x) = g.f. of Catalan numbers.
Convolution of Catalan numbers and powers of 4.
Also one half of convolution of central binomial coeffs. A000984(n), n=0, 1, 2, ... with shifted central binomial coeffs. A000984(n), n=1, 2, 3, ...
a(n) = A045621(2n+1) = (1/2)*A068551(n+1).
a(n) = Sum_{k=0..n} A000984(k)*A001700(n-k). - Philippe Deléham, Jan 22 2004
a(n) = Sum_{k=0..n+1} binomial(n+k, k-1)2^(n-k+1). - Paul Barry, Nov 13 2004
a(n) = Sum_{i=0..n} binomial(2n+2, i). See A008949. - Ed Catmur (ed(AT)catmur.co.uk), Dec 09 2006
a(n) = Sum_{k=0..n+1, C(2n+2,k)} - C(2n+2,n+1). - Paul Barry, Jan 21 2007
Logarithm g.f. log(1/(2-C(x)))=sum(n>0, a(n)/n*x^n), C(x)=(1-sqrt(1-4*x))/2x (A000108). - Vladimir Kruchinin, Aug 10 2010
D-finite with recurrence: (n+3) a(n+2) - 2(4n+9) a(n+1) + 8(2n+3) a(n) = 0. - Emanuele Munarini, Mar 16 2011
E.g.f.:exp(2*x)*(2*exp(2*x) - BesselI(0,2*x) - BesselI(1,2*x)).
This is the first derivative of exp(2*x)*(exp(2*x) - BesselI(0,2*x))/2. See the e.g.f. of A032443 (which has a plus sign) and the remarks given there. - Wolfdieter Lang, Jan 16 2012
a(n) = Sum_{0<=iMircea Merca, Apr 05 2012
A000346 = A004171 - A001700. See A032443 for the sum. - M. F. Hasler, Jan 02 2014
0 = a(n) * (256*a(n+1) - 224*a(n+2) + 40*a(n+3)) + a(n+1) * (-32*a(n+1) + 56*a(n+2) - 14*a(n+3)) + a(n+2) * (-2*a(n+2) + a(n+3)) if n>-5. - Michael Somos, Jan 25 2014
REVERT transform is [1,-5,28,-168,1056,...] = alternating signed version of A069731. - Michael Somos, Jan 25 2014
Convolution square is A038806. - Michael Somos, Jan 25 2014
BINOMIAL transform of A055217(n-1) is a(n-1). - Michael Somos, Jan 25 2014
(n+1) * a(n) = A033504(n). - Michael Somos, Jan 25 2014
Recurrence: (n+1)*a(n) = 512*(2*n-7)*a(n-5) + 256*(13-5*n)*a(n-4) + 64*(10*n-17)*a(n-3) + 32*(4-5*n)*a(n-2) + 2*(10*n+1)*a(n-1), n>=5. - Fung Lam, Mar 21 2014
Asymptotic approximation: a(n) ~ 2^(2n+1)*(1-1/sqrt(n*Pi)). - Fung Lam, Mar 21 2014
a(n) = Sum_{m = n+2..2*(n+1)} binomial(2*(n+1), m), n >= 0. - Wolfdieter Lang, May 22 2015
a(n) = A000302(n) + A008549(n). - Gus Wiseman, Jul 19 2021
a(n) = Sum_{j=1..n+1} Sum_{k=1..j} 2^(j-k)*binomial(n+k-1, n). - Fabio Visonà, May 04 2022
a(n) = (1/2)*(-1)^n*binomial(-(n+1), n+2)*hypergeom([1, 2*n + 3], [n + 3], 1/2). - Peter Luschny, Nov 29 2023

Corrected by Christian G. Bower

A008549 Number of ways of choosing at most n-1 items from a set of size 2*n+1.

Original entry on oeis.org

0, 1, 6, 29, 130, 562, 2380, 9949, 41226, 169766, 695860, 2842226, 11576916, 47050564, 190876696, 773201629, 3128164186, 12642301534, 51046844836, 205954642534, 830382690556, 3345997029244, 13475470680616, 54244942336114, 218269673491780, 877940640368572

Offset: 0

N. J. A. Sloane

Area under Dyck excursions (paths ending in 0): a(n) is the sum of the areas under all Dyck excursions of length 2*n (nonnegative walks beginning and ending in 0 with jumps -1,+1).
Number of inversions in all 321-avoiding permutations of [n+1]. Example: a(2)=6 because the 321-avoiding permutations of [3], namely 123,132,312,213,231, have 0, 1, 2, 1, 2 inversions, respectively. - Emeric Deutsch, Jul 28 2003
Convolution of A001791 and A000984. - Paul Barry, Feb 16 2005
a(n) = total semilength of "longest Dyck subpath" starting at an upstep U taken over all upsteps in all Dyck paths of semilength n. - David Callan, Jul 25 2008
[1,6,29,130,562,2380,...] is convolution of A001700 with itself. - Philippe Deléham, May 19 2009
From Ran Pan, Feb 04 2016: (Start)
a(n) is the total number of times that all the North-East lattice paths from (0,0) to (n+1,n+1) bounce off the diagonal y = x to the right. This is related to paired pattern P_2 in Pan and Remmel's link and more details can be found in Section 3.2 in the link.
a(n) is the total number of times that all the North-East lattice paths from (0,0) to (n+1,n+1) horizontally cross the diagonal y = x. This is related to paired pattern P_3 in Pan and Remmel's link and more details can be found in Section 3.3 in the link.
2*a(n) is the total number of times that all the North-East lattice paths from (0,0) to (n+1,n+1) bounce off the diagonal y = x. This is related to paired pattern P_2 and P_4 in Pan and Remmel's link and more details can be found in Section 4.2 in the link.
2*a(n) is the total number of times that all the North-East lattice paths from (0,0) to (n+1,n+1) cross the diagonal y = x. This is related to paired pattern P_3 and P_4 in Pan and Remmel's link and more details can be found in Section 4.3 in the link. (End)
From Gus Wiseman, Jul 17 2021: (Start)
Also the number of integer compositions of 2*(n+1) with alternating sum < 0, where the alternating sum of a sequence (y_1,...,y_k) is Sum_i (-1)^(i-1) y_i. For example, the a(3) = 29 compositions of 8 are:
  (1,7)  (1,5,2)  (1,1,1,5)  (1,1,1,4,1)  (1,1,1,1,1,3)
  (2,6)  (1,6,1)  (1,1,2,4)  (1,2,1,3,1)  (1,1,1,2,1,2)
  (3,5)  (2,5,1)  (1,2,1,4)  (1,3,1,2,1)  (1,1,1,3,1,1)
                  (1,2,2,3)  (1,4,1,1,1)  (1,2,1,1,1,2)
                  (1,3,1,3)               (1,2,1,2,1,1)
                  (1,3,2,2)               (1,3,1,1,1,1)
                  (1,4,1,2)
                  (1,4,2,1)
                  (1,5,1,1)
                  (2,1,1,4)
                  (2,2,1,3)
                  (2,3,1,2)
                  (2,4,1,1)
Also the number of integer compositions of 2*(n+1) with reverse-alternating sum < 0. For a bijection, keep the odd-length compositions and reverse the even-length ones.
Also the number of 2*(n+1)-digit binary numbers with more 0's than 1's. For example, the a(2) = 6 binary numbers are: 100000, 100001, 100010, 100100, 101000, 110000; or in decimal: 32, 33, 34, 36, 40, 48.
(End)

			a(2) = 6 because there are 6 ways to choose at most 1 item from a set of size 5: You can choose the empty set, or you can choose any of the five one-element sets.
G.f. = x + 6*x^2 + 29*x^3 + 130*x^4 + 562*x^5 + 2380*x^6 + 9949*x^7 + ...

D. Phulara and L. W. Shapiro, Descendants in ordered trees with a marked vertex, Congressus Numerantium, 205 (2011), 121-128.

Indranil Ghosh, Table of n, a(n) for n = 0..1500 (terms 0..200 from T. D. Noe)
José Agapito, Ângela Mestre, Maria M. Torres, and Pasquale Petrullo, On One-Parameter Catalan Arrays, Journal of Integer Sequences, 18 (2015), Article 15.5.1.
Octavio Arizmendi, Daniel Perales, and Josue Vazquez-Becerra, Finite Free Convolution: Infinitesimal Distributions, arXiv:c [math.PR], 2025. See p. 34.
Jean Christophe Aval, Adrien Boussicault, Patxi Laborde-Zubieta, and Mathias Pétréolle, Generating series of Periodic Parallelogram polyominoes, arXiv:1612.03759, 2016.
Roland Bacher, On generating series of complementary plane trees, arXiv:math/0409050 [math.CO], 2004.
Vijay Balasubramanian, Javier M. Magan, and Qingyue Wu, A Tale of Two Hungarians: Tridiagonalizing Random Matrices, arXiv:2208.08452 [hep-th], 2022.
Cyril Banderier, Analytic combinatorics of random walks and planar maps, Ph. D. Thesis, 2001. [Broken link]
Adrien Boussicault and P. Laborde-Zubieta, Periodic Parallelogram Polyominoes, arXiv preprint arXiv:1611.03766 [math.CO], 2016.
AJ Bu, Explicit Generating Functions for the Sum of the Areas Under Dyck and Motzkin Paths (and for Their Powers), arXiv:2310.17026 [math.CO], 2023.
AJ Bu and Doron Zeilberger, Using Symbolic Computation to Explore Generalized Dyck Paths and Their Areas, arXiv:2305.09030 [math.CO], 2023.
Alexander Burstein and Sergi Elizalde, Total occurrence statistics on restricted permutations, arXiv:1305.3177 [math.CO], 2013.
Robin Chapman, Moments of Dyck paths, Discrete Math., 204 (1999), 113-117.
Nicolle González, Pamela E. Harris, Gordon Rojas Kirby, Mariana Smit Vega Garcia, and Bridget Eileen Tenner, Pinnacle sets of signed permutations, arXiv:2301.02628 [math.CO], 2023.
Guo-Niu Han, Enumeration of Standard Puzzles, 2011. [Cached copy]
Guo-Niu Han, Enumeration of Standard Puzzles, arXiv:2006.14070 [math.CO], 2020.
Milan Janjić, Pascal Matrices and Restricted Words, J. Int. Seq., Vol. 21 (2018), Article 18.5.2.
Niklas G. Johansson, Efficient Simulation of the Deutsch-Jozsa Algorithm, Master's Project, Department of Electrical Engineering & Department of Physics, Chemistry and Biology, Linkoping University, April, 2015.
Miles Jones, Sergey Kitaev, and Jeffrey Remmel, Frame patterns in n-cycles, arXiv preprint arXiv:1311.3332 [math.CO], 2013.
James A. Mingo and Josue Vazquez-Becerra, The Asymptotic Infinitesimal Distribution of a Real Wishart Random Matrix, arXiv:2112.15231 [math.PR], 2021.
Henri Mühle, Symmetric Chain Decompositions and the Strong Sperner Property for Noncrossing Partition Lattices, arXiv:1509.06942v1 [math.CO], 2015.
Ran Pan and Jeffrey B. Remmel, Paired patterns in lattice paths, arXiv:1601.07988 [math.CO], 2016.
Elisa Pergola, Two bijections for the area of Dyck paths, Discrete Math., 241 (2001), 435-447.
Wen-jin Woan, Area of Catalan Paths, Discrete Math., 226 (2001), 439-444.

Cf. A038608, A045894, A057571, A109196, A153338.
Odd bisection of A294175 (even is A000346).
For integer compositions of 2*(n+1) with alternating sum k < 0 we have:
- The opposite (k > 0) version is A000302.
- The weak (k <= 0) version is (also) A000302.
- The k = 0 version is A001700 or A088218.
- The reverse-alternating version is also A008549 (this sequence).
- These compositions are ranked by A053754 /\ A345919.
- The complement (k >= 0) is counted by A114121.
- The case of reversed integer partitions is A344743(n+1).
A011782 counts compositions.
A097805 counts compositions by alternating (or reverse-alternating) sum.
A103919 counts partitions by sum and alternating sum (reverse: A344612).
A316524 gives the alternating sum of prime indices (reverse: A344616).
A344610 counts partitions by sum and positive reverse-alternating sum.
A345197 counts compositions by length and alternating sum.
Cf. A000070, A001791, A007318, A025047, A027306, A032443, A058622, A120452, A163493, A239830, A344611.

[4^n-Binomial(2*n+1, n): n in [0..30]]; // Vincenzo Librandi, Feb 04 2016

A008549:=n->4^n-binomial(2*n+1,n): seq(A008549(n), n=0..30);

Table[4^n-Binomial[2n+1,n],{n,0,30}] (* Harvey P. Dale, May 11 2011 *)
a[ n_] := If[ n<-4, 0, 4^n - Binomial[2 n + 2, n + 1] / 2] (* Michael Somos, Jan 25 2014 *)

{a(n)=if(n<0, 0, 4^n - binomial(2*n+1, n))} /* Michael Somos Oct 31 2006 */

{a(n) = if( n<-4, 0, n++; (4^n / 2 - binomial(2*n, n)) / 2)} /* Michael Somos, Jan 25 2014 */

import math
def C(n,r):
    f=math.factorial
    return f(n)/f(r)/f(n-r)
def A008549(n):
    return int((4**n)-C(2*n+1,n)) # Indranil Ghosh, Feb 18 2017

a(n) = 4^n - C(2*n+1, n).
a(n) = Sum_{k=1..n} Catalan(k)*4^(n-k): convolution of Catalan numbers and powers of 4.
G.f.: x*c(x)^2/(1 - 4*x), c(x) = g.f. of Catalan numbers. - Wolfdieter Lang
Note Sum_{k=0..2*n+1} binomial(2*n+1, k) = 2^(2n+1). Therefore, by the symmetry of Pascal's triangle, Sum_{k=0..n} binomial(2*n+1, k) = 2^(2*n) = 4^n. This explains why the following two expressions for a(n) are equal: Sum_{k=0..n-1} binomial(2*n+1, k) = 4^n - binomial(2*n+1, n). - Dan Velleman
G.f.: (2*x^2 - 1 + sqrt(1 - 4*x^2))/(2*(1 + 2*x)*(2*x - 1)*x^3).
a(n) = Sum_{k=0..n} C(2*k, k)*C(2*(n-k), n-k-1). - Paul Barry, Feb 16 2005
Second binomial transform of 2^n - C(n, floor(n/2)) = A045621(n). - Paul Barry, Jan 13 2006
a(n) = Sum_{0 < i <= k < n} binomial(n, k+i)*binomial(n, k-i). - Mircea Merca, Apr 05 2012
D-finite with recurrence (n+1)*a(n) + 2*(-4*n-1)*a(n-1) + 8*(2*n-1)*a(n-2) = 0. - R. J. Mathar, Dec 03 2012
0 = a(n) * (256*a(n+1) - 224*a(n+2) + 40*a(n+3)) + a(n+1) * (-32*a(n+1) + 56*a(n+2) - 14*a(n+3)) + a(n+2) * (-2*a(n+2) + a(n+3)) if n > -5. - Michael Somos, Jan 25 2014
Convolution square is A045894. - Michael Somos, Jan 25 2014
HANKEL transform is [0, -1, 2, -3, 4, -5, ...]. - Michael Somos, Jan 25 2014
BINOMIAL transform of [0, 0, 1, 3, 11, 35,...] (A109196) is [0, 0, 1, 6, 29, 130, ...]. - Michael Somos, Jan 25 2014
(n+1) * a(n) = A153338(n+1). - Michael Somos, Jan 25 2014
a(n) = Sum_{m = n+2..2*n+1} binomial(2*n+1,m), n >= 0. - Wolfdieter Lang, May 22 2015
E.g.f.: (exp(2*x) - BesselI(0,2*x) - BesselI(1,2*x))*exp(2*x). - Ilya Gutkovskiy, Aug 30 2016

Better description from Dan Velleman (djvelleman(AT)amherst.edu), Dec 01 2000

A054336 A convolution triangle of numbers based on A001405 (central binomial coefficients).

Original entry on oeis.org

1, 1, 1, 2, 2, 1, 3, 5, 3, 1, 6, 10, 9, 4, 1, 10, 22, 22, 14, 5, 1, 20, 44, 54, 40, 20, 6, 1, 35, 93, 123, 109, 65, 27, 7, 1, 70, 186, 281, 276, 195, 98, 35, 8, 1, 126, 386, 618, 682, 541, 321, 140, 44, 9, 1, 252, 772, 1362, 1624, 1440, 966, 497, 192, 54, 10, 1

Offset: 0

Wolfdieter Lang, Mar 13 2000

T(n,k) is the number of 2-Motzkin paths (i.e., Motzkin paths with blue and red level steps) with no level steps at positive height and having k blue level steps. Example: T(4,2)=9 because, denoting U=(1,1), D=(1,-1), B=blue (1,0), R=red (1,0), we have BBRR, BRBR, BRRB, RBBR, RBRB, RRBB, BBUD, BUDB, and UDBB. - Emeric Deutsch, Jun 07 2011
In the language of the Shapiro et al. reference (given in A053121) such a lower triangular (ordinary) convolution array, considered as a matrix, belongs to the Bell-subgroup of the Riordan-group.
The g.f. for the row polynomials p(n,x) (increasing powers of x) is 1/(1-(1+x)*z-z^2*c(z^2)), with c(x) the g.f. for Catalan numbers A000108.
Column sequences: A001405, A045621.
Riordan array (f(x), x*f(x)), f(x) the g.f. of A001405. - Philippe Deléham, Dec 08 2009
From Paul Barry, Oct 21 2010: (Start)
Riordan array ((sqrt(1+2x) - sqrt(1-2x))/(2x*sqrt(1-2x)), (sqrt(1+2x)-sqrt(1-2x))/(2*sqrt(1-2x))),
inverse of Riordan array ((1+x)/(1+2x+2x^2), x(1+x)/(1+2x+2x^2)) (A181472). (End)

			Fourth row polynomial (n=3): p(3,x)= 3 + 5*x + 3*x^2 + x^3.
From _Paul Barry_, Oct 21 2010: (Start)
Triangle begins
   1;
   1,  1;
   2,  2,   1;
   3,  5,   3,   1;
   6, 10,   9,   4,  1;
  10, 22,  22,  14,  5,  1;
  20, 44,  54,  40, 20,  6, 1;
  35, 93, 123, 109, 65, 27, 7, 1;
Production matrix is
   1,  1;
   1,  1,  1;
  -1,  1,  1,  1;
   1, -1,  1,  1,  1;
  -1,  1, -1,  1,  1,  1;
   1, -1,  1, -1,  1,  1,  1;
  -1,  1, -1,  1, -1,  1,  1, 1;
   1, -1,  1, -1,  1, -1,  1, 1, 1;
  -1,  1, -1,  1, -1,  1, -1, 1, 1, 1; (End)

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

Cf. A001405, A035324, A054335.

Row sums: A054341.

A053121:= function(n,k)
    if ((n-k+1) mod 2)=0 then return 0;
    else return (k+1)*Binomial(n+1, Int((n-k)/2))/(n+1);
    fi;
  end;
T:= function(n,k)
    return Sum([k..n], j-> Binomial(j,k)*A053121(n,j));
  end;
Flat(List([0..10], n-> List([0..n], k-> T(n,k) ))); # G. C. Greubel, Jul 21 2019

A053121:= func< n,k | ((n-k+1) mod 2) eq 0 select 0 else (k+1)*Binomial(n+1, Floor((n-k)/2))/(n+1) >;
T:= func< n,k | (&+[Binomial(j,k)*A053121(n,j): j in [k..n]]) >;
[T(n,k): k in [0..n], n in [0..10]]; // G. C. Greubel, Jul 21 2019

c[n_, j_] /; n < j || OddQ[n - j] = 0; c[n_, j_] = (j + 1) Binomial[n + 1, (n - j)/2]/(n + 1); t[n_, k_] := Sum[c[n, j]*Binomial[j, k], {j, 0, n}]; Flatten[Table[t[n, k], {n, 0, 10}, {k, 0, n}]][[;; 66]] (* Jean-François Alcover, Jul 13 2011, after Philippe Deléham *)

A053121(n,k) = if((n-k+1)%2==0, 0, (k+1)*binomial(n+1, (n-k)\2)/(n+1) );
T(n,k) = sum(j=k,n, A053121(n,j)*binomial(j,k));
for(n=0,10, for(k=0,n, print1(T(n,k), ", "))) \\ G. C. Greubel, Jul 21 2019

def A053121(n, k):
    if (n-k+1) % 2==0: return 0
    else: return (k+1)*binomial(n+1, ((n-k)//2))/(n+1)
def T(n,k): return sum(binomial(j,k)*A053121(n,j) for j in (k..n))
[[T(n,k) for k in (0..n)] for n in (0..10)] # G. C. Greubel, Jul 21 2019

G.f. for column m: cbi(x)*(x*cbi(x))^m, with cbi(x) := (1+x*c(x^2))/sqrt(1-4*x^2) = 1/(1-x-x^2*c(x^2)), where c(x) is the g.f. for Catalan numbers A000108.
T(n,k) = Sum_{j>=0} A053121(n,j)*binomial(j,k). - Philippe Deléham, Mar 30 2007
T(n,k) = T(n-1,k-1) + T(n-1,l) + Sum_{j>=0} T(n-1,k+1+j)*(-1)^j. - Philippe Deléham, Feb 23 2012

A068551 a(n) = 4^n - binomial(2*n,n).

Original entry on oeis.org

0, 2, 10, 44, 186, 772, 3172, 12952, 52666, 213524, 863820, 3488872, 14073060, 56708264, 228318856, 918624304, 3693886906, 14846262964, 59644341436, 239532643144, 961665098956, 3859788636664, 15488087080696, 62135313450064

Offset: 0

N. J. A. Sloane, Mar 23 2002

Number of rooted two-face n-edge maps in the plane (planar with a distinguished outside face). - Valery A. Liskovets, Mar 17 2005
Total number of returns to the x axis in all lattice paths using steps (1,1) and (1,-1) from the origin to (2n,0). Cf. A108747. - Geoffrey Critzer, Jan 30 2012
Total depth of all leaves in all binary trees on 2n+1 nodes. - Marko Riedel, Sep 10 2016

H. W. Gould, Combinatorial Identities, Morgantown, WV, 1972. p. 32.
Hojoo Lee, Posting to Number Theory List, Feb 18 2002.
V. A. Liskovets and T. R. Walsh, Enumeration of unrooted maps on the plane, Rapport technique, UQAM, No. 2005-01, Montreal, Canada, 2005.

Vincenzo Librandi, Table of n, a(n) for n = 0..175
Dennis E. Davenport, Lara K. Pudwell, Louis W. Shapiro, and Leon C. Woodson, The Boundary of Ordered Trees, Journal of Integer Sequences, Vol. 18 (2015), Article 15.5.8.
Nicolle González, Pamela E. Harris, Gordon Rojas Kirby, Mariana Smit Vega Garcia, and Bridget Eileen Tenner, Pinnacle sets of signed permutations, arXiv:2301.02628 [math.CO], 2023.
Guo-Niu Han, Enumeration of Standard Puzzles, 2011. [Cached copy]
Guo-Niu Han, Enumeration of Standard Puzzles, arXiv:2006.14070 [math.CO], 2020.
Marko R. Riedel, Average depth of a leaf in a binary tree, Math.Stackexchange.com.
V. A. Liskovets and T. R. Walsh, Counting unrooted maps on the plane, Advances in Applied Math., 36(4) (2006), 364-387.

Cf. A000108, A000346, A000984, A005470, A045621.

[4^n - Binomial(2*n,n): n in [0..35]]; // Vincenzo Librandi, Jun 07 2011

A068551:=n->4^n - binomial(2*n,n): seq(A068551(n), n=0..30); # Wesley Ivan Hurt, Mar 22 2014

nn=20;c=(1-(1-4x)^(1/2))/(2x); D[CoefficientList[ Series[ 1/(1-2y x c), {x,0,nn}], x], y]/.y->1 (* Geoffrey Critzer, Jan 30 2012 *)

PARI
```
a(n)=if(n<0,0,4^n-binomial(2*n,n))
```

x='x+O('x^100); concat(0, Vec(1/(1-4*x)-1/sqrt(1-4*x))) \\ Altug Alkan, Dec 29 2015

G.f.: 1/(1 - 4*x) - 1/sqrt(1 - 4*x) = C(x)*2*x/(1 - 4*x) where C(x) = g.f. for Catalan numbers A000108.
a(n) = Sum_{k >= 1} binomial(2*m-2*k, m-k) * binomial(2*k, k).
a(n+1) = 4*a(n) + 2*C(n), where C(n) = Catalan numbers.
a(n) = 2*A000346(n-1) for n > 0.
a(n) = A045621(2*n).
Conjecture: n*a(n) + 2*(3-4*n)*a(n-1) + 8*(2*n-3)*a(n-2) = 0. - R. J. Mathar, Apr 01 2012
Recurrence (an alternative): n*a(n) = 2^9*(2*n - 9)*a(n-5) + 2^8*(18 - 5*n)*a(n-4) + 2^6*(10*n - 27)*a(n-3) + 2^5*(9 - 5*n)*a(n-2) + 2*(10*n - 9)*a(n-1), n >= 5. - Fung Lam, Mar 22 2014
Asymptotics: a(n) ~ 2^(2*n)*(1 - 1/sqrt(n*Pi)). - Fung Lam, Mar 22 2014
E.g.f.: (exp(2*x) - BesselI(0, 2*x))*exp(2*x). - Ilya Gutkovskiy, Sep 10 2016
a(n) = (-1)^(n+1)*binomial(-n, n + 1)*hypergeom([1, 2*n + 1], [n + 2], 1/2). - Peter Luschny, Nov 29 2023

A127630 Expansion of (1+x-x^2-x^3)/(1+x^2)^2.

Original entry on oeis.org

1, 1, -3, -3, 5, 5, -7, -7, 9, 9, -11, -11, 13, 13, -15, -15, 17, 17, -19, -19, 21, 21, -23, -23, 25, 25, -27, -27, 29, 29, -31, -31, 33, 33, -35, -35, 37, 37, -39, -39, 41, 41, -43, -43, 45, 45, -47, -47, 49, 49, -51, -51, 53, 53, -55, -55

Offset: 0

Paul Barry, Jan 20 2007

Hankel transform of A045621(n+1).

Index entries for linear recurrences with constant coefficients, signature (0,-2,0,-1).

Cf. A109613.

CoefficientList[Series[(1+x-x^2-x^3)/(1+x^2)^2,{x,0,100}],x] (* or *) LinearRecurrence[{0,-2,0,-1},{1,1,-3,-3},100] (* Harvey P. Dale, Nov 18 2020 *)

a(n) = (-1)^binomial(n,2) * ( 2*floor(n/2)+1 ).
a(n) = (n + 1 - (n mod 2))*(-1)^floor(n/2). [Wesley Ivan Hurt, Jun 30 2013]
G.f.:  1/(G(0) - x), where G(k) = x*(2*k+1) - (2*k-1)/( 1 + x/( 1 - x*(2*k+3)/G(k+1) )); (continued fraction ). - Sergei N. Gladkovskii, Dec 27 2013

A191391 Number of horizontal segments in all dispersed Dyck paths of length n (i.e., in all Motzkin paths of length n with no (1,0)-steps at positive heights; a horizontal segment is a maximal sequence of consecutive (1,0)-steps).

Original entry on oeis.org

0, 1, 1, 3, 5, 12, 22, 49, 93, 200, 386, 814, 1586, 3304, 6476, 13381, 26333, 54096, 106762, 218386, 431910, 880616, 1744436, 3547658, 7036530, 14281072, 28354132, 57451164, 114159428, 230993296, 459312152, 928319149, 1846943453, 3729244576, 7423131482, 14975907754

Offset: 0

Emeric Deutsch, Jun 03 2011

nonn

			a(4)=5 because in (HHHH), (HH)UD, (H)UD(H), UD(HH), UDUD, and UUDD we have a total of 1+1+2+1+0+0=5 horizontal segments (shown between parentheses).

Cf. A191390.

First differences of A045621.

g := 4*z*(1-z)/(1-2*z+sqrt(1-4*z^2))^2: gser := series(g, z = 0, 40): seq(coeff(gser, z, n), n = 0 .. 35);

a(n) = Sum_{k>=0} k*A191390(n,k).
G.f.: g(z) = 4*z*(1-z)/(1-2*z+sqrt(1-4*z^2))^2.
a(0)=0 and a(n)=2^(n-1)-C(n-1,floor(n/2)-1) for n>=1. [Joerg Arndt, Aug 07 2012, aeb]
D-finite with recurrence (n+1)*a(n) +(-3*n-1)*a(n-1) +2*(-n+3)*a(n-2) +4*(3*n-8)*a(n-3) +8*(-n+4)*a(n-4)=0. - R. J. Mathar, Jul 24 2022

A307768 Number of n-step random walks on a line starting from the origin and returning to it at least once.

Original entry on oeis.org

0, 0, 2, 4, 10, 20, 44, 88, 186, 372, 772, 1544, 3172, 6344, 12952, 25904, 52666, 105332, 213524, 427048, 863820, 1727640, 3488872, 6977744, 14073060, 28146120, 56708264, 113416528, 228318856, 456637712, 918624304, 1837248608, 3693886906, 7387773812, 14846262964, 29692525928

Offset: 0

Robert FERREOL, Apr 27 2019

a(n)/2^n tends to 1 as n goes to infinity; this means that on the line any random walk returns sooner or later to its starting point with a probability 1.

a(n) is also the number of heads-or-tails games of length n during which at some point there are as many heads as tails.

			The a(3)=4 three-step walks returning to 0 are [0, -1, 0, -1], [0, -1, 0, 1], [0, 1, 0, -1], [0, 1, 0, 1].
The a(4)=10 three-step walks returning to 0 are [0, -1, -2, -1, 0], [0, -1, 0, -1, -2], [0, -1, 0, -1, 0], [0, -1, 0, 1, 0], [0, -1, 0, 1, 2], [0, 1, 0, -1, -2], [0, 1, 0, -1, 0], [0, 1, 0, 1, 0], [0, 1, 0, 1, 2], [0, 1, 2, 1, 0].

Robert Israel, Table of n, a(n) for n = 0..3318
Monique Laurent, Sven Polak, and Luis Felipe Vargas, Semidefinite approximations for bicliques and biindependent pairs, arXiv:2302.08886 [math.CO], 2023.

Cf. A027306, A063886, A045621, A128014, A284016.

b:=n->piecewise(n mod 2 = 0,binomial(n,n/2),2*binomial(n-1,(n-1)/2)):
seq(2^n-b(n),n=0..20);
# second program:
A307768 := series(exp(2*x) - int((1/x + 2)*BesselI(1,2*x),x) - BesselI(1,2*x), x = 0, 36): seq(n!*coeff(A307768, x, n), n = 0 .. 35); # Mélika Tebni, Jun 19 2024

a[n_] := If[n == 0, 0, 2^n - 2*Binomial[n-1, Floor[(n-1)/2]]];
Array[a, 36, 0] (* Jean-François Alcover, May 05 2019 *)

a(n) = 2^n - A063886(n).
a(n+1) = 2*A045621(n) = 2*(2^n - binomial(n,floor(n/2))).
a(2n) = 2^(2n) - binomial(2n,n); a(2n+1) = 2*a(2n).
G.f.: (1-sqrt(1-4*x^2))/(1-2*x). - Alois P. Heinz, May 05 2019
n*(a(n)-2*a(n-1)) - 4*(n-3)*(a(n-2)-2*a(n-3)) = 0. - Robert Israel, May 06 2019
a(2n+2) - 2*a(2n+1) = A284016(n) = 2*Catalan(n). - Robert FERREOL, Aug 26 2019
From Mélika Tebni, Jun 19 2024: (Start)
E.g.f.: exp(2*x) - Integral_{x=-oo..oo} (1/x + 2)*BesselI(1, 2*x) dx - BesselI(1, 2*x).
a(n) = 2*(A027306(n) - A128014(n)). (End)

A330796 a(n) = Sum_{k=0..n} binomial(n, k)*(2^k - binomial(k, floor(k/2))).

Original entry on oeis.org

0, 1, 4, 14, 46, 147, 462, 1437, 4438, 13637, 41746, 127426, 388076, 1179739, 3581052, 10856790, 32880942, 99496293, 300845658, 909073356, 2745419352, 8287110075, 25003877784, 75412396575, 227366950140, 685293578217, 2064924137152, 6220442229932, 18734334462598

Offset: 0

Peter Luschny, Jan 12 2020

nonn

G. C. Greubel, Table of n, a(n) for n = 0..1000

Cf. A008549, A045621.

m:=40;
R:=PowerSeriesRing(Rationals(), m+2);
A330796:= func< n | Coefficient(R!( (1-x-Sqrt(1-3*x)*Sqrt(1+x))/(2*x*(1-3*x)) ), n) >;
[A330796(n): n in [0..m]]; // G. C. Greubel, Sep 14 2023

gf := exp(x)*(exp(2*x) - BesselI(0,2*x) - BesselI(1,2*x)):
ser := series(gf, x, 32): seq(n!*coeff(ser, x, n), n=0..28);
# Alternative:
a := proc(n) option remember; if n < 3 then return n^2 fi;
((18-9*n)*a(n-3) - (3*n+3)*a(n-2) + (5*n+2)*a(n-1))/(n+1) end:
seq(a(n), n=0..28);
# Or:
a := n -> add(binomial(n, k)*(2^k - binomial(k, floor(k/2))), k=0..n):
seq(a(n), n=0..28);

a[n_]:= Sum[k Binomial[n,k] Hypergeometric2F1[(k-n)/2, (k-n+1)/2, k+2, 4], {k,0,n}]; Table[a[n], {n,0,30}] (* Peter Luschny, May 24 2021 *)
(* Second program *)
A330796[n_]:= Coefficient[Series[(1-x-Sqrt[1-3*x]*Sqrt[1+x])/(2*x*(1- 3*x)), {x,0,50}], x, n];
Table[A330796[n], {n,0,30}] (* G. C. Greubel, Sep 14 2023 *)

a(n):=(2*sum((-1)^j*binomial(2*j+1,j)*3^(n-j-1)*binomial(n+1,j+2),j,0,n-1))/(n+1); /* Vladimir Kruchinin, Sep 30 2020 */

m=40
P. = PowerSeriesRing(ZZ, m+2)
def A330796(n): return P( (1-x-sqrt(1-3*x)*sqrt(1+x))/(2*x*(1-3*x)) ).list()[n]
[A330796(n) for n in range(m+1)] # G. C. Greubel, Sep 14 2023

a(n) = n! * [x^n] e^x*(e^(2*x) - I_{0}(2*x) - I_{1}(2*x)), where I_{n}(x) are the modified Bessel functions of the first kind.
a(n) = [x^n] (1 - x - sqrt(1 - 3*x)*sqrt(1 + x))/(2*x*(1 - 3*x)).
D-finite with recurrence a(n) = ((18-9*n)*a(n-3) - (3*n+3)*a(n-2) + (5*n+2)*a(n-1))/(n+1).
Sum_{k=0..n} binomial(n, k)*a(k) = A008549(n).
Sum_{k=0..n} (-1)^(n-k)*binomial(n, k)*a(k) = A045621(n).
a(n) = 2*Sum_{j=0..n-1} (-1)^j*C(2*j+1,j)*3^(n-j-1)*C(n+1,j+2)/(n+1). - Vladimir Kruchinin, Sep 30 2020
a(n) = Sum_{k=0..n} k*binomial(n,k)*hypergeom([(k-n)/2, (k-n+1)/2], [k+2], 4). - Peter Luschny, May 24 2021
a(n) ~ 3^n * (1 - sqrt(3/(Pi*n))). - Vaclav Kotesovec, May 24 2021

cp's OEIS Frontend

A134377 Binomial transform of A045621.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

Extensions

A000346 a(n) = 2^(2*n+1) - binomial(2*n+1, n+1).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Maxima

PARI

Formula

Extensions

A008549 Number of ways of choosing at most n-1 items from a set of size 2*n+1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

Python

Formula

Extensions

A054336 A convolution triangle of numbers based on A001405 (central binomial coefficients).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

GAP

Magma

Mathematica

PARI

Sage

Formula

A068551 a(n) = 4^n - binomial(2*n,n).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

Formula

A127630 Expansion of (1+x-x^2-x^3)/(1+x^2)^2.

Views

Author

A000346 a(n) = 2^(2n+1) - binomial(2n+1, n+1).