

A008549


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


64



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 321avoiding permutations of [n+1]. Example: a(2)=6 because the 321avoiding permutations of [3], namely 123,132,312,213,231, have 0, 1, 2, 1, 2 inversions, respectively.  Emeric Deutsch, Jul 28 2003
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
a(n) is the total number of times that all the NorthEast 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 NorthEast 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 NorthEast 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 NorthEast 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)
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)^(i1) 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 reversealternating sum < 0. For a bijection, keep the oddlength compositions and reverse the evenlength 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), 121128.


LINKS

José Agapito, Ângela Mestre, Maria M. Torres, and Pasquale Petrullo, On OneParameter Catalan Arrays, Journal of Integer Sequences, 18 (2015), Article 15.5.1.
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.


FORMULA

a(n) = 4^n  C(2*n+1, n).
a(n) = Sum_{k=1..n} Catalan(k)*4^(nk): 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..n1} 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*(nk), nk1).  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, ki).  Mircea Merca, Apr 05 2012
Dfinite with recurrence (n+1)*a(n) + 2*(4*n1)*a(n1) + 8*(2*n1)*a(n2) = 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
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
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 oneelement sets.
G.f. = x + 6*x^2 + 29*x^3 + 130*x^4 + 562*x^5 + 2380*x^6 + 9949*x^7 + ...


MAPLE



MATHEMATICA

Table[4^nBinomial[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 */
(Python)
import math
def C(n, r):
....f=math.factorial
....return f(n)/f(r)/f(nr)


CROSSREFS

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 reversealternating version is also A008549 (this sequence).
 The complement (k >= 0) is counted by A114121.
 The case of reversed integer partitions is A344743(n+1).
A097805 counts compositions by alternating (or reversealternating) 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 reversealternating sum.
A345197 counts compositions by length and alternating sum.
Cf. A000070, A001791, A007318, A025047, A027306, A032443, A058622, A120452, A163493, A239830, A344611.


KEYWORD

nonn,easy,nice


AUTHOR



EXTENSIONS

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


STATUS

approved



