|
| |
|
|
A000346
|
|
a(n) = 2^(2*n+1) - binomial(2*n+1, n+1).
(Formerly M3920 N1611)
|
|
89
|
|
|
|
1, 5, 22, 93, 386, 1586, 6476, 26333, 106762, 431910, 1744436, 7036530, 28354132, 114159428, 459312152, 1846943453, 7423131482, 29822170718, 119766321572, 480832549478, 1929894318332, 7744043540348, 31067656725032, 124613686513778, 499744650202436
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,2
|
|
|
COMMENTS
|
Also a(n) = 2nd elementary symmetric function of binomial(n,0), binomial(n,1), ..., binomial(n,n).
Also a(n) = one half the sum of the heights, over all Dyck (n+2)-paths, of the vertices that are at even height and terminate an upstep. For example with n=1, these vertices are indicated by asterisks in the 5 Dyck 3-paths: UU*UDDD, UU*DU*DD, UDUU*DD, UDUDUD, UU*DDUD, yielding a(1)=(2+4+2+0+2)/2=5. - David Callan, Jul 14 2006
Hankel transform is (-1)^n*(2n+1); the Hankel transform of sum(k=0..n, C(2*n,k) ) - C(2n,n) is (-1)^n*n. - Paul Barry, Jan 21 2007
For n > 0, a(n-1) is also the number of integer compositions of 2n with nonzero alternating sum, where the alternating sum of a sequence (y_1,...,y_k) is Sum_i (-1)^(i-1) y_i. These compositions are ranked by A053754 /\ A345921. For example, the a(3-1) = 22 compositions of 6 are:
(6) (1,5) (1,1,4) (1,1,1,3) (1,1,1,1,2)
(2,4) (1,2,3) (1,1,3,1) (1,1,2,1,1)
(4,2) (1,4,1) (1,2,1,2) (2,1,1,1,1)
(5,1) (2,1,3) (1,3,1,1)
(2,2,2) (2,1,2,1)
(3,1,2) (3,1,1,1)
(3,2,1)
(4,1,1)
(End)
|
|
|
REFERENCES
|
T. Myers and L. Shapiro, Some applications of the sequence 1, 5, 22, 93, 386, ... to Dyck paths and ordered trees, Congressus Numerant., 204 (2010), 93-104.
D. Phulara and L. W. Shapiro, Descendants in ordered trees with a marked vertex, Congressus Numerantium, 205 (2011), 121-128.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
|
LINKS
|
D. Merlini, R. Sprugnoli and M. C. Verri, The tennis ball problem, J. Combin. Theory, A 99 (2002), 307-344 (A_n for s=2).
|
|
|
FORMULA
|
G.f.: c(x)/(1-4x), c(x) = g.f. of Catalan numbers.
Convolution of Catalan numbers and powers of 4.
Also one half of convolution of central binomial coeffs. A000984(n), n=0, 1, 2, ... with shifted central binomial coeffs. A000984(n), n=1, 2, 3, ...
a(n) = Sum_{k=0..n+1} binomial(n+k, k-1)2^(n-k+1). - Paul Barry, Nov 13 2004
a(n) = Sum_{i=0..n} binomial(2n+2, i). See A008949. - Ed Catmur (ed(AT)catmur.co.uk), Dec 09 2006
a(n) = Sum_{k=0..n+1, C(2n+2,k)} - C(2n+2,n+1). - Paul Barry, Jan 21 2007
D-finite with recurrence: (n+3) a(n+2) - 2(4n+9) a(n+1) + 8(2n+3) a(n) = 0. - Emanuele Munarini, Mar 16 2011
E.g.f.:exp(2*x)*(2*exp(2*x) - BesselI(0,2*x) - BesselI(1,2*x)).
This is the first derivative of exp(2*x)*(exp(2*x) - BesselI(0,2*x))/2. See the e.g.f. of A032443 (which has a plus sign) and the remarks given there. - Wolfdieter Lang, Jan 16 2012
a(n) = Sum_{0<=i<j<=n+1} binomial(n+1, i)*binomial(n+1, j). - Mircea Merca, Apr 05 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
REVERT transform is [1,-5,28,-168,1056,...] = alternating signed version of A069731. - Michael Somos, Jan 25 2014
Recurrence: (n+1)*a(n) = 512*(2*n-7)*a(n-5) + 256*(13-5*n)*a(n-4) + 64*(10*n-17)*a(n-3) + 32*(4-5*n)*a(n-2) + 2*(10*n+1)*a(n-1), n>=5. - Fung Lam, Mar 21 2014
Asymptotic approximation: a(n) ~ 2^(2n+1)*(1-1/sqrt(n*Pi)). - Fung Lam, Mar 21 2014
a(n) = Sum_{m = n+2..2*(n+1)} binomial(2*(n+1), m), n >= 0. - Wolfdieter Lang, May 22 2015
a(n) = Sum_{j=1..n+1} Sum_{k=1..j} 2^(j-k)*binomial(n+k-1, n). - Fabio Visonà, May 04 2022
a(n) = (1/2)*(-1)^n*binomial(-(n+1), n+2)*hypergeom([1, 2*n + 3], [n + 3], 1/2). - Peter Luschny, Nov 29 2023
|
|
|
EXAMPLE
|
G.f. = 1 + 5*x + 22*x^2 + 93*x^3 + 386*x^4 + 1586*x^5 + 6476*x^6 + ...
|
|
|
MAPLE
|
seq(2^(2*n+1)-binomial(2*n, n)*(2*n+1)/(n+1), n=0..12); # Emanuele Munarini, Mar 16 2011
|
|
|
MATHEMATICA
|
Table[2^(2n+1)-Binomial[2n, n](2n+1)/(n+1), {n, 0, 20}] (* Emanuele Munarini, Mar 16 2011 *)
a[ n_] := If[ n<-4, 0, (4^(n + 1) - Binomial[2 n + 2, n + 1]) / 2]; (* Michael Somos, Jan 25 2014 *)
|
|
|
PROG
|
(PARI) {a(n) = if( n<-4, 0, n++; (2^(2*n) - binomial(2*n, n)) / 2)}; /* Michael Somos, Jan 25 2014 */
(Maxima) makelist(2^(2*n+1)-binomial(2*n, n)*(2*n+1)/(n+1), n, 0, 12); /* Emanuele Munarini, Mar 16 2011 */
(Magma) [2^(2*n+1) - Binomial(2*n+1, n+1): n in [0..30]]; // Vincenzo Librandi, Jun 07 2011
|
|
|
CROSSREFS
|
Even bisection of A294175 (without the first two terms).
The following relate to compositions of 2n with alternating sum k.
- The k > 0 case is counted by A000302.
- The k <= 0 case is counted by A000302.
- The k != 0 case is counted by A000346 (this sequence).
- The k < 0 case is counted by A008549.
- The k >= 0 case is counted by A114121.
A086543 counts partitions with nonzero alternating sum (bisection: A182616).
A097805 counts compositions by alternating (or reverse-alternating) sum.
A103919 counts partitions by sum and alternating sum (reverse: A344612).
A345197 counts compositions by length and alternating sum.
Cf. A000070, A001791, A007318, A025047, A027306, A032443, A053754, A120452, A163493, A239830, A344611, A345921.
|
|
|
KEYWORD
|
nonn,easy
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
