|
| |
|
|
A008549
|
|
Number of ways of choosing at most n-1 items from a set of size 2n+1.
|
|
17
|
|
|
|
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]
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.
Jean-Christophe Aval, A Boussicault, P Laborde-Zubieta, M Pétréolle, Generating series of Periodic Parallelogram polyominoes, arXiv preprint arXiv:1612.03759, 2016
R. Bacher, On generating series of complementary plane trees arXiv:math/0409050 [math.CO], 2004.
C. Banderier, Analytic combinatorics of random walks and planar maps, PhD Thesis, 2001.
Adrien Boussicault, P. Laborde-Zubieta, Periodic Parallelogram Polyominoes, arXiv preprint arXiv:1611.03766 [math.CO], 2016.
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]
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, 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
|
| |
|
|
