login
The OEIS is supported by the many generous donors 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 2*n+1. 65

%I #155 Oct 27 2023 09:40:04

%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 2*n+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. - _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)

%C From _Gus Wiseman_, Jul 17 2021: (Start)

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

%C (1,7) (1,5,2) (1,1,1,5) (1,1,1,4,1) (1,1,1,1,1,3)

%C (2,6) (1,6,1) (1,1,2,4) (1,2,1,3,1) (1,1,1,2,1,2)

%C (3,5) (2,5,1) (1,2,1,4) (1,3,1,2,1) (1,1,1,3,1,1)

%C (1,2,2,3) (1,4,1,1,1) (1,2,1,1,1,2)

%C (1,3,1,3) (1,2,1,2,1,1)

%C (1,3,2,2) (1,3,1,1,1,1)

%C (1,4,1,2)

%C (1,4,2,1)

%C (1,5,1,1)

%C (2,1,1,4)

%C (2,2,1,3)

%C (2,3,1,2)

%C (2,4,1,1)

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

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

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

%H Jean-Christophe Aval, A. Boussicault, P. Laborde-Zubieta, and M. Pétréolle, <a href="http://arxiv.org/abs/1612.03759">Generating series of Periodic Parallelogram polyominoes</a>, 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 Vijay Balasubramanian, Javier M. Magan, and Qingyue Wu, <a href="https://arxiv.org/abs/2208.08452">A Tale of Two Hungarians: Tridiagonalizing Random Matrices</a>, arXiv:2208.08452 [hep-th], 2022.

%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 and P. Laborde-Zubieta, <a href="https://arxiv.org/abs/1611.03766">Periodic Parallelogram Polyominoes</a>, arXiv preprint arXiv:1611.03766 [math.CO], 2016.

%H AJ Bu, <a href="https://arxiv.org/abs/2310.17026">Explicit Generating Functions for the Sum of the Areas Under Dyck and Motzkin Paths (and for Their Powers)</a>, arXiv:2310.17026 [math.CO], 2023.

%H AJ Bu and Doron Zeilberger, <a href="https://arxiv.org/abs/2305.09030">Using Symbolic Computation to Explore Generalized Dyck Paths and Their Areas</a>, arXiv:2305.09030 [math.CO], 2023.

%H A. Burstein and S. Elizalde, <a href="http://arxiv.org/abs/1305.3177">Total occurrence statistics on restricted permutations</a>, 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 Nicolle González, Pamela E. Harris, Gordon Rojas Kirby, Mariana Smit Vega Garcia, and Bridget Eileen Tenner, <a href="https://arxiv.org/abs/2301.02628">Pinnacle sets of signed permutations</a>, arXiv:2301.02628 [math.CO], 2023.

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

%H Guo-Niu Han, <a href="https://arxiv.org/abs/2006.14070">Enumeration of Standard Puzzles</a>, arXiv:2006.14070 [math.CO], 2020.

%H Milan Janjić, <a href="https://www.emis.de/journals/JIS/VOL21/Janjic2/janjic103.html">Pascal Matrices and Restricted Words</a>, J. Int. Seq., Vol. 21 (2018), Article 18.5.2.

%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, and 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 James A. Mingo and Josue Vazquez-Becerra, <a href="https://arxiv.org/abs/2112.15231">The Asymptotic Infinitesimal Distribution of a Real Wishart Random Matrix</a>, arXiv:2112.15231 [math.PR], 2021.

%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:1509.06942v1 [math.CO], 2015.

%H Ran Pan and 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..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

%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(2*k, 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 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

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

%Y Odd bisection of A294175 (even is A000346).

%Y For integer compositions of 2*(n+1) with alternating sum k < 0 we have:

%Y - The opposite (k > 0) version is A000302.

%Y - The weak (k <= 0) version is (also) A000302.

%Y - The k = 0 version is A001700 or A088218.

%Y - The reverse-alternating version is also A008549 (this sequence).

%Y - These compositions are ranked by A053754 /\ A345919.

%Y - The complement (k >= 0) is counted by A114121.

%Y - The case of reversed integer partitions is A344743(n+1).

%Y A011782 counts compositions.

%Y A097805 counts compositions by alternating (or reverse-alternating) sum.

%Y A103919 counts partitions by sum and alternating sum (reverse: A344612).

%Y A316524 gives the alternating sum of prime indices (reverse: A344616).

%Y A344610 counts partitions by sum and positive reverse-alternating sum.

%Y A345197 counts compositions by length and alternating sum.

%Y Cf. A000070, A001791, A007318, A025047, A027306, A032443, A058622, A120452, A163493, A239830, A344611.

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 29 06:15 EDT 2024. Contains 371265 sequences. (Running on oeis4.)