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

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

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

From Gus Wiseman, Jul 17 2021: (Start)

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:

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

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

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

(1,2,2,3) (1,4,1,1,1) (1,2,1,1,1,2)

(1,3,1,3) (1,2,1,2,1,1)

(1,3,2,2) (1,3,1,1,1,1)

(1,4,1,2)

(1,4,2,1)

(1,5,1,1)

(2,1,1,4)

(2,2,1,3)

(2,3,1,2)

(2,4,1,1)

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.

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.

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

Vijay Balasubramanian, Javier M. Magan, and Qingyue Wu, A Tale of Two Hungarians: Tridiagonalizing Random Matrices, arXiv:2208.08452 [hep-th], 2022.

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

Adrien Boussicault and P. Laborde-Zubieta, Periodic Parallelogram Polyominoes, arXiv preprint arXiv:1611.03766 [math.CO], 2016.

AJ Bu, Explicit Generating Functions for the Sum of the Areas Under Dyck and Motzkin Paths (and for Their Powers), arXiv:2310.17026 [math.CO], 2023.

AJ Bu and Doron Zeilberger, Using Symbolic Computation to Explore Generalized Dyck Paths and Their Areas, arXiv:2305.09030 [math.CO], 2023.

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.

Nicolle González, Pamela E. Harris, Gordon Rojas Kirby, Mariana Smit Vega Garcia, and Bridget Eileen Tenner, Pinnacle sets of signed permutations, arXiv:2301.02628 [math.CO], 2023.

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.

James A. Mingo and Josue Vazquez-Becerra, The Asymptotic Infinitesimal Distribution of a Real Wishart Random Matrix, arXiv:2112.15231 [math.PR], 2021.

Henri Mühle, Symmetric Chain Decompositions and the Strong Sperner Property for Noncrossing Partition Lattices, arXiv:1509.06942v1 [math.CO], 2015.

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

Odd bisection of A294175 (even is A000346).

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

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

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

- The k = 0 version is A001700 or A088218.

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

- These compositions are ranked by A053754 /\ A345919.

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

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

A011782 counts compositions.

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

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

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

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

A345197 counts compositions by length and alternating sum.

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

Sequence in context: A172062 A081674 A173413 * A345031 A351146 A026675

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