The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A008549 Number of ways of choosing at most n-1 items from a set of size 2*n+1. 18
 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 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,3 COMMENTS 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 , 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) REFERENCES D. Phulara and L. W. Shapiro, Descendants in ordered trees with a marked vertex, Congressus Numerantium, 205 (2011), 121-128. LINKS 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. Jean-Christophe Aval, A. Boussicault, P. Laborde-Zubieta, and M. Pétréolle, Generating series of Periodic Parallelogram polyominoes, arXiv:1612.03759, 2016. R. Bacher, On generating series of complementary plane trees, arXiv:math/0409050 [math.CO], 2004. C. Banderier, Analytic combinatorics of random walks and planar maps, PhD Thesis, 2001. Adrien Boussicault, P. Laborde-Zubieta, Periodic Parallelogram Polyominoes, arXiv preprint arXiv:1611.03766 [math.CO], 2016. A. Burstein and S. Elizalde, Total occurrence statistics on restricted permutations, arXiv:1305.3177 [math.CO], 2013. R. Chapman, Moments of Dyck paths, Discrete Math., 204 (1999), 113-117. 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. N. 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. M. Jones, S. Kitaev, and J. Remmel, Frame patterns in n-cycles, arXiv preprint arXiv:1311.3332 [math.CO], 2013. Henri Mühle, Symmetric Chain Decompositions and the Strong Sperner Property for Noncrossing Partition Lattices, arXiv:1509.06942v1 [math.CO], 2015. Ran Pan, Jeffrey B. Remmel, Paired patterns in lattice paths, arXiv:1601.07988 [math.CO], 2016. E. Pergola, Two bijections for the area of Dyck paths, Discrete Math., 241 (2001), 435-447. W.-J. Woan, Area of Catalan Paths, Discrete Math., 226 (2001), 439-444. FORMULA 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 EXAMPLE 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 + ... MAPLE A008549:=n->4^n-binomial(2*n+1, n): seq(A008549(n), n=0..30); MATHEMATICA 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 *) PROG (PARI) {a(n)=if(n<0, 0, 4^n - binomial(2*n+1, n))} /* Michael Somos Oct 31 2006 */ (PARI) {a(n) = if( n<-4, 0, n++; (4^n / 2 - binomial(2*n, n)) / 2)} /* Michael Somos, Jan 25 2014 */ (MAGMA) [4^n-Binomial(2*n+1, n): n in [0..30]]; // Vincenzo Librandi, Feb 04 2016 (Python) import math def C(n, r): ....f=math.factorial ....return f(n)/f(r)/f(n-r) def A008549(n): ....return str((4**n)-C(2*n+1, n)) # Indranil Ghosh, Feb 18 2017 CROSSREFS Cf. A038608, A045894, A057571, A109196, A153338. Sequence in context: A172062 A081674 A173413 * A026675 A026873 A081179 Adjacent sequences:  A008546 A008547 A008548 * A008550 A008551 A008552 KEYWORD nonn,easy,nice AUTHOR EXTENSIONS Better description from Dan Velleman (djvelleman(AT)amherst.edu), Dec 01 2000 STATUS approved

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

Last modified April 11 08:10 EDT 2021. Contains 342886 sequences. (Running on oeis4.)