login
This site is supported by donations to The OEIS Foundation.

 

Logo


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 2n+1. 17
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 [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 . [From Philippe Deléham, May 19 2009]

Comments 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

Jean-Christophe Aval, A Boussicault, P Laborde-Zubieta, M Pétréolle, Generating series of Periodic Parallelogram polyominoes, arXiv preprint arXiv:1612.03759, 2016

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, Vol. 18 (2015), Article 15.5.1.

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

Guo-Niu Han, Enumeration of Standard Puzzles [Cached copy]

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, 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 preprint 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..2n+1} binomial(2n+1, k) = 2^(2n+1). Therefore, by the symmetry of Pascal's triangle, Sum_{k=0..n} binomial(2n+1, k) = 2^(2n) = 4^n. This explains why the following two expressions for a(n) are equal: Sum_{k=0..n-1} binomial(2n+1, k) = 4^n - binomial(2n+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(2k, 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]

(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

N. J. A. Sloane

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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified January 18 18:56 EST 2018. Contains 297864 sequences.