|
%I M3920 N1611 #155 Nov 29 2023 11:43:12
%S 1,5,22,93,386,1586,6476,26333,106762,431910,1744436,7036530,28354132,
%T 114159428,459312152,1846943453,7423131482,29822170718,119766321572,
%U 480832549478,1929894318332,7744043540348,31067656725032,124613686513778,499744650202436
%N a(n) = 2^(2*n+1) - binomial(2*n+1, n+1).
%C Also a(n) = 2nd elementary symmetric function of binomial(n,0), binomial(n,1), ..., binomial(n,n).
%C 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
%C 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
%C Row sums of the Riordan matrix (1/(1-4x),(1-sqrt(1-4x))/2) (A187926). - _Emanuele Munarini_, Mar 16 2011
%C From _Gus Wiseman_, Jul 19 2021: (Start)
%C 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:
%C (6) (1,5) (1,1,4) (1,1,1,3) (1,1,1,1,2)
%C (2,4) (1,2,3) (1,1,3,1) (1,1,2,1,1)
%C (4,2) (1,4,1) (1,2,1,2) (2,1,1,1,1)
%C (5,1) (2,1,3) (1,3,1,1)
%C (2,2,2) (2,1,2,1)
%C (3,1,2) (3,1,1,1)
%C (3,2,1)
%C (4,1,1)
%C (End)
%D 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 D. Phulara and L. W. Shapiro, Descendants in ordered trees with a marked vertex, Congressus Numerantium, 205 (2011), 121-128.
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Vincenzo Librandi, <a href="/A000346/b000346.txt">Table of n, a(n) for n = 0..500</a>
%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 Paul Barry, <a href="https://arxiv.org/abs/2004.04577">On a Central Transform of Integer Sequences</a>, arXiv:2004.04577 [math.CO], 2020.
%H E. A. Bender, E. R. Canfield and R. W. Robinson, <a href="http://dx.doi.org/10.4153/CMB-1988-039-4">The enumeration of maps on the torus and the projective plane</a>, Canad. Math. Bull., 31 (1988), 257-271; see p. 270.
%H D. E. Davenport, L. K. Pudwell, L. W. Shapiro and L. C. Woodson, <a href="http://faculty.valpo.edu/lpudwell/papers/treeboundary.pdf">The Boundary of Ordered Trees</a>, 2014.
%H P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/books.html">Analytic Combinatorics</a>, 2009; see page 185
%H R. K. Guy, <a href="/A000346/a000346.pdf">Letter to N. J. A. Sloane</a>
%H Toufik Mansour and José L. Ramirez, <a href="https://ajc.maths.uq.edu.au/pdf/81/ajc_v81_p447.pdf">Enumerations of polyominoes determined by Fuss-Catalan words</a>, Australas. J. Combin. 81 (3) (2021) 447-457, table 1.
%H Mircea Merca, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL15/Merca1/merca6.html">A Special Case of the Generalized Girard-Waring Formula</a>, J. Integer Sequences, Vol. 15 (2012), Article 12.5.7. - From _N. J. A. Sloane_, Nov 25 2012
%H D. Merlini, R. Sprugnoli and M. C. Verri, <a href="http://www.dsi.unifi.it/~merlini/fun01.ps">Waiting patterns for a printer</a>, FUN with algorithm'01, Isola d'Elba, 2001.
%H D. Merlini, R. Sprugnoli and M. C. Verri, <a href="http://dx.doi.org/10.1006/jcta.2002.3273">The tennis ball problem</a>, J. Combin. Theory, A 99 (2002), 307-344 (A_n for s=2).
%H Vera Posch, <a href="https://www.diva-portal.org/smash/get/diva2:1776814/FULLTEXT01.pdf">Correlators in Matrix Models</a>, Master Thesis, Uppsala Univ. (Sweden 2023). See p. 44.
%H John Riordan, <a href="/A002720/a002720_3.pdf">Letter to N. J. A. Sloane, Sep 26 1980 with notes on the 1973 Handbook of Integer Sequences</a>. Note that the sequences are identified by their N-numbers, not their A-numbers.
%H W. T. Tutte, <a href="http://dx.doi.org/10.1090/S0002-9904-1968-11877-4">On the enumeration of planar maps</a>. Bull. Amer. Math. Soc. 74 1968 64-74.
%H T. R. S. Walsh and A. B. Lehman, <a href="http://dx.doi.org/10.1016/0095-8956(72)90056-1">Counting rooted maps by genus</a>, J. Comb. Thy B13 (1972), 122-141 and 192-218 (eq. 5, b=1).
%H N. J. A. Sloane, <a href="/A007401/a007401_1.pdf">Notes</a>
%F G.f.: c(x)/(1-4x), c(x) = g.f. of Catalan numbers.
%F Convolution of Catalan numbers and powers of 4.
%F 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, ...
%F a(n) = A045621(2n+1) = (1/2)*A068551(n+1).
%F a(n) = Sum_{k=0..n} A000984(k)*A001700(n-k). - _Philippe Deléham_, Jan 22 2004
%F a(n) = Sum_{k=0..n+1} binomial(n+k, k-1)2^(n-k+1). - _Paul Barry_, Nov 13 2004
%F a(n) = Sum_{i=0..n} binomial(2n+2, i). See A008949. - Ed Catmur (ed(AT)catmur.co.uk), Dec 09 2006
%F a(n) = Sum_{k=0..n+1, C(2n+2,k)} - C(2n+2,n+1). - _Paul Barry_, Jan 21 2007
%F Logarithm g.f. log(1/(2-C(x)))=sum(n>0, a(n)/n*x^n), C(x)=(1-sqrt(1-4*x))/2x (A000108). - _Vladimir Kruchinin_, Aug 10 2010
%F 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
%F E.g.f.:exp(2*x)*(2*exp(2*x) - BesselI(0,2*x) - BesselI(1,2*x)).
%F 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
%F a(n) = Sum_{0<=i<j<=n+1} binomial(n+1, i)*binomial(n+1, j). - _Mircea Merca_, Apr 05 2012
%F A000346 = A004171 - A001700. See A032443 for the sum. - _M. F. Hasler_, Jan 02 2014
%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 REVERT transform is [1,-5,28,-168,1056,...] = alternating signed version of A069731. - _Michael Somos_, Jan 25 2014
%F Convolution square is A038806. - _Michael Somos_, Jan 25 2014
%F BINOMIAL transform of A055217(n-1) is a(n-1). - _Michael Somos_, Jan 25 2014
%F (n+1) * a(n) = A033504(n). - _Michael Somos_, Jan 25 2014
%F 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
%F Asymptotic approximation: a(n) ~ 2^(2n+1)*(1-1/sqrt(n*Pi)). - _Fung Lam_, Mar 21 2014
%F a(n) = Sum_{m = n+2..2*(n+1)} binomial(2*(n+1), m), n >= 0. - _Wolfdieter Lang_, May 22 2015
%F a(n) = A000302(n) + A008549(n). - _Gus Wiseman_, Jul 19 2021
%F a(n) = Sum_{j=1..n+1} Sum_{k=1..j} 2^(j-k)*binomial(n+k-1, n). - _Fabio Visonà_, May 04 2022
%F 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
%e G.f. = 1 + 5*x + 22*x^2 + 93*x^3 + 386*x^4 + 1586*x^5 + 6476*x^6 + ...
%p seq(2^(2*n+1)-binomial(2*n,n)*(2*n+1)/(n+1), n=0..12); # _Emanuele Munarini_, Mar 16 2011
%t Table[2^(2n+1)-Binomial[2n,n](2n+1)/(n+1),{n,0,20}] (* _Emanuele Munarini_, Mar 16 2011 *)
%t a[ n_] := If[ n<-4, 0, (4^(n + 1) - Binomial[2 n + 2, n + 1]) / 2]; (* _Michael Somos_, Jan 25 2014 *)
%o (PARI) {a(n) = if( n<-4, 0, n++; (2^(2*n) - binomial(2*n, n)) / 2)}; /* _Michael Somos_, Jan 25 2014 */
%o (Maxima) makelist(2^(2*n+1)-binomial(2*n,n)*(2*n+1)/(n+1),n,0,12); /* _Emanuele Munarini_, Mar 16 2011 */
%o (Magma) [2^(2*n+1) - Binomial(2*n+1,n+1): n in [0..30]]; // _Vincenzo Librandi_, Jun 07 2011
%Y Cf. A000108, A014137, A014318. A column of A058893. Subdiagonal of A053979.
%Y Bisection of A058622 and (possibly) A007008.
%Y Cf. A045621, A068551.
%Y Cf. A033504, A038806, A055217, A069731.
%Y Even bisection of A294175 (without the first two terms).
%Y The following relate to compositions of 2n with alternating sum k.
%Y - The k > 0 case is counted by A000302.
%Y - The k <= 0 case is counted by A000302.
%Y - The k != 0 case is counted by A000346 (this sequence).
%Y - The k = 0 case is counted by A001700 or A088218.
%Y - The k < 0 case is counted by A008549.
%Y - The k >= 0 case is counted by A114121.
%Y A011782 counts compositions.
%Y A086543 counts partitions with nonzero alternating sum (bisection: A182616).
%Y A097805 counts compositions by alternating (or reverse-alternating) sum.
%Y A103919 counts partitions by sum and alternating sum (reverse: A344612).
%Y A345197 counts compositions by length and alternating sum.
%Y Cf. A000070, A001791, A007318, A025047, A027306, A032443, A053754, A120452, A163493, A239830, A344611, A345921.
%K nonn,easy
%O 0,2
%A _N. J. A. Sloane_, _Wolfdieter Lang_
%E Corrected by _Christian G. Bower_
|
