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. 16
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

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.

C. Banderier, Analytic combinatorics of random walks and planar maps, PhD Thesis, 2001.

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 September 26 06:54 EDT 2017. Contains 292502 sequences.