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

%I

%S 0,1,6,29,130,562,2380,9949,41226,169766,695860,2842226,11576916,

%T 47050564,190876696,773201629,3128164186,12642301534,51046844836,

%U 205954642534,830382690556,3345997029244,13475470680616,54244942336114,218269673491780,877940640368572

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

%C 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).

%C 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

%C Convolution of A001791 and A000984. - _Paul Barry_, Feb 16 2005

%C 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

%C [1,6,29,130,562,2380,...] is convolution of A001700 with itself . [From _Philippe Deléham_, May 19 2009]

%C From _Ran Pan_, Feb 04 2016 (Start)

%C 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.

%C 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.

%C 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.

%C 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)

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

%H Indranil Ghosh, <a href="/A008549/b008549.txt">Table of n, a(n) for n = 0..1500</a> (terms 0..200 from T. D. Noe)

%H José Agapito, Ângela Mestre, Maria M. Torres, and Pasquale Petrullo, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Agapito/agapito2.html">On One-Parameter Catalan Arrays</a>, Journal of Integer Sequences, Vol. 18 (2015), Article 15.5.1.

%H Jean-Christophe Aval, A Boussicault, P Laborde-Zubieta, M Pétréolle, <a href="http://arxiv.org/abs/1612.03759">Generating series of Periodic Parallelogram polyominoes</a>, arXiv preprint arXiv:1612.03759, 2016

%H R. Bacher, <a href="http://arxiv.org/abs/math/0409050">On generating series of complementary plane trees</a> arXiv:math/0409050 [math.CO], 2004.

%H C. Banderier, <a href="http://algo.inria.fr/banderier/">Analytic combinatorics of random walks and planar maps</a>, PhD Thesis, 2001.

%H Adrien Boussicault, P. Laborde-Zubieta, <a href="https://arxiv.org/abs/1611.03766">Periodic Parallelogram Polyominoes</a>, arXiv preprint arXiv:1611.03766 [math.CO], 2016.

%H A. Burstein and S. Elizalde, <a href="http://arxiv.org/abs/1305.3177">Total occurrence statistics on restricted permutations</a>, arXiv preprint arXiv:1305.3177 [math.CO], 2013.

%H R. Chapman, <a href="http://dx.doi.org/10.1016/S0012-365X(98)00367-7">Moments of Dyck paths</a>, Discrete Math., 204 (1999), 113-117.

%H Guo-Niu Han, <a href="http://www-irma.u-strasbg.fr/~guoniu/papers/p77puzzle.pdf">Enumeration of Standard Puzzles</a>

%H Guo-Niu Han, <a href="/A196265/a196265.pdf">Enumeration of Standard Puzzles</a> [Cached copy]

%H N. G. Johansson, <a href="http://urn.kb.se/resolve?urn=urn%3Anbn%3Ase%3Aliu%3Adiva-120110">Efficient Simulation of the Deutsch-Jozsa Algorithm</a>, Master's Project, Department of Electrical Engineering & Department of Physics, Chemistry and Biology, Linkoping University, April, 2015.

%H M. Jones, S. Kitaev, J. Remmel, <a href="http://arxiv.org/abs/1311.3332">Frame patterns in n-cycles</a>, arXiv preprint arXiv:1311.3332 [math.CO], 2013.

%H Henri Mühle, <a href="http://arxiv.org/abs/1509.06942">Symmetric Chain Decompositions and the Strong Sperner Property for Noncrossing Partition Lattices</a>, arXiv preprint arXiv:1509.06942v1 [math.CO], 2015.

%H Ran Pan, Jeffrey B. Remmel, <a href="http://arxiv.org/abs/1601.07988">Paired patterns in lattice paths</a>, arXiv:1601.07988 [math.CO], 2016.

%H E. Pergola, <a href="http://dx.doi.org/10.1016/S0012-365X(01)00129-7">Two bijections for the area of Dyck paths</a>, Discrete Math., 241 (2001), 435-447.

%H W.-J. Woan, <a href="http://dx.doi.org/10.1016/S0012-365X(00)00162-X">Area of Catalan Paths</a>, Discrete Math., 226 (2001), 439-444.

%F a(n) = 4^n - C(2*n+1, n).

%F a(n) = Sum_{k=1..n} Catalan(k)*4^(n-k): convolution of Catalan numbers and powers of 4.

%F G.f.: x*(c(x)^2)/(1-4*x), c(x) = g.f. of Catalan numbers [ _Wolfdieter Lang_ ]

%F 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

%F G.f.: (2*x^2-1+sqrt(1-4*x^2))/(2*(1+2*x)*(2*x-1)*x^3).

%F a(n) = Sum_{k=0..n} C(2k, k)*C(2(n-k), n-k-1). - _Paul Barry_, Feb 16 2005

%F Second binomial transform of 2^n-C(n, floor(n/2)) = A045621(n). - _Paul Barry_, Jan 13 2006

%F a(n) = Sum_{0<i<=k<n} binomial(n,k+i)*binomial(n,k-i). [_Mircea Merca_, Apr 05 2012]

%F (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

%F 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

%F Convolution square is A045894. - _Michael Somos_, Jan 25 2014

%F HANKEL transform is [0,-1,2,-3,4,-5,...]. - _Michael Somos_, Jan 25 2014

%F BINOMIAL transform of [0,0,1,3,11,35,...] (A109196) is [0,0,1,6,29,130,...]. - _Michael Somos_, Jan 25 2014

%F (n+1) * a(n) = A153338(n+1). - _Michael Somos_, Jan 25 2014

%F a(n) = Sum_{m = n+2..2*n+1} binomial(2*n+1,m), n >= 0. - _Wolfdieter Lang_, May 22 2015

%F E.g.f.: (exp(2*x) - BesselI(0,2*x) - BesselI(1,2*x))*exp(2*x). - _Ilya Gutkovskiy_, Aug 30 2016

%e 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.

%e G.f. = x + 6*x^2 + 29*x^3 + 130*x^4 + 562*x^5 + 2380*x^6 + 9949*x^7 + ...

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

%t Table[4^n-Binomial[2n+1,n],{n,0,30}] (* _Harvey P. Dale_, May 11 2011 *)

%t a[ n_] := If[ n<-4, 0, 4^n - Binomial[2 n + 2, n + 1] / 2] (* _Michael Somos_, Jan 25 2014 *)

%o (PARI) {a(n)=if(n<0, 0, 4^n - binomial(2*n+1, n))} /* _Michael Somos_ Oct 31 2006 */

%o (PARI) {a(n) = if( n<-4, 0, n++; (4^n / 2 - binomial(2*n, n)) / 2)} /* _Michael Somos_, Jan 25 2014 */

%o (MAGMA) [4^n-Binomial(2*n+1, n): n in [0..30]]; // _Vincenzo Librandi_, Feb 04 2016

%o (Python)

%o import math

%o def C(n,r):

%o ....f=math.factorial

%o ....return f(n)/f(r)/f(n-r)

%o def A008549(n):

%o ....return str((4**n)-C(2*n+1,n)) # _Indranil Ghosh_, Feb 18 2017

%Y Cf. A038608, A045894, A057571, A109196, A153338.

%K nonn,easy,nice

%O 0,3

%A _N. J. A. Sloane_

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

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 May 22 00:03 EDT 2018. Contains 304403 sequences. (Running on oeis4.)