A114121 - OEIS

%I #52 Apr 10 2024 08:46:48

%S 1,2,7,26,99,382,1486,5812,22819,89846,354522,1401292,5546382,

%T 21977516,87167164,345994216,1374282019,5461770406,21717436834,

%U 86392108636,343801171354,1368640564996,5450095992964,21708901408216,86492546019214

%N Expansion of (sqrt(1 - 4*x) + (1 - 2*x))/(2*(1 - 4*x)).

%C Second binomial transform of A032443 with interpolated zeros.

%C a(n) is the total number of lattice points, taken over all Dyck n-paths (A000108), that (i) lie on or above ground level and (ii) lie on or directly below a peak. For example with n = 2, UUDD has 1 peak contributing 3 lattice points--(2, 0), (2, 1) and (2, 2) when the path starts at the origin--and UDUD has 2 peaks, each contributing 2 lattice points and so a(2) = 3 + 4 = 7. - _David Callan_, Jul 14 2006

%C Hankel transform is binomial(n + 2, 2). - _Paul Barry_, Dec 04 2007

%C Image of (-1)^n under the Riordan array ((1/2)(1/(1 - 4x) + 1/sqrt(1 - 4x)), c(x) - 1), c(x) the g.f. of A000108. - _Paul Barry_, Jun 15 2008

%C From _Gus Wiseman_, Jun 21 2021: (Start)

%C Also the even bisection of A116406 = number compositions of n with alternating sum >= 0, where the alternating sum of a sequence (y_1,...,y_k) is Sum_i (-1)^(i-1) y_i. The a(3) = 26 compositions are:

%C   (6)  (33)  (114)  (1122)  (11112)  (111111)

%C        (42)  (123)  (1131)  (11121)

%C        (51)  (132)  (1221)  (11211)

%C              (213)  (2112)  (12111)

%C              (222)  (2121)  (21111)

%C              (231)  (2211)

%C              (312)  (3111)

%C              (321)

%C              (411)

%C (End)

%H G. C. Greubel, <a href="/A114121/b114121.txt">Table of n, a(n) for n = 0..1000</a>

%H G.-S. Cheon, H. Kim, L. W. Shapiro, <a href="http://arxiv.org/abs/1410.1249">Mutation effects in ordered trees</a>, arXiv:1410.1249 [math.CO], 2014

%H Mircea Merca, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL15/Merca1/merca6.html">A Note on Cosine Power Sums</a> J. Integer Sequences, Vol. 15 (2012), Article 12.5.3.

%F a(n) = Sum_{k=0..n} C(n, k)*2^(n-k-2)*(2^k + C(k, k/2))*(1 + (-1)^k).

%F a(n) = (A000984(n) + A081294(n))/2.

%F From _Paul Barry_, Jun 15 2008: (Start)

%F G.f.: (1 - 4*x + (1 - 2*x)*sqrt(1 - 4*x))/(2*(1 - 4*x)^(3/2)).

%F a(n) = Sum_{k=0..n} ( Sum_{j=0..n} C(2*n, n-k-j)*(-1)^j ). (End)

%F a(n) = Sum_{k=0..n} C(2*n, n-k)*(1 + (-1)^k)/2. - _Paul Barry_, Aug 06 2009

%F From _Paul Barry_, Sep 07 2009: (Start)

%F a(n) = C(2*n-1, n-1) + (4^n + 3*0^n)/4.

%F Integral representation a(n) = (1/(2*pi))*(Integral_{x=0..4} x^n/sqrt(x(4 - x))) + (4^n + 0^n)/4. (End)

%F a(n) = Sum_{k=0..floor(n/2)} C(2*n, 2*k + (n mod 2)). - _Mircea Merca_, Jun 21 2011

%F Conjecture: n*a(n) + 2*(3 - 4*n)*a(n-1) + 8*(2*n-3)*a(n-2) = 0. - _R. J. Mathar_, Nov 07 2012

%F Conjecture verified using the differential equation (16*x^2-8*x+1)*g'(x) + (8*x-2)*g(x)-2*x=0 satisfied by the G.f. - _Robert Israel_, Jul 27 2020

%F a(n) = Sum_{i=0..n} (sum_{j=0..n} binomial(n, i+j)*binomial(n, j-i)). - _Yalcin Aktar_, Jan 07 2013.

%F G.f.: (1 + (1 - 4*x)^(-1/2))^2 / 4. Convolution square of A088218. - _Michael Somos_, Dec 31 2013

%F 0 = (1 + 2*n)*b(n) - (5 + 4*n)*b(n+1) + (4 + 2*n)*b(n+2) if n > 0 where b(n) = a(n) / 4^n. - _Michael Somos_, Dec 31 2013

%F 0 = b(n+3) * (2*b(n+2) - 7*b(n+1) + 5*b(n)) + b(n+2) * (-b(n+2) + 7*b(n+1) - 7*b(n)) + b(n+1) * (-b(n+1) + 2*b(n)) if n > 0 where b(n) = a(n) / 4^n. - _Michael Somos_, Dec 31 2013

%F For n > 0, a(n) = 2^(2n-1) - A008549(n). - _Gus Wiseman_, Jun 27 2021

%F a(n) = [x^n] 1/((1-2*x) * (1-x)^(n-1)). - _Seiichi Manyama_, Apr 10 2024

%e G.f. = 1 + 2*x + 7*x^2 + 26*x^3 + 99*x^4 + 382*x^5 + 1486*x^6 + 5812*x^7 + ...

%p seq(sum(binomial(2*n,2*k+irem(n,2)),k=0..floor((1/2)*n)),n=0..20)

%p seq(binomial(2*n-1,n)+4^(n-1)-(1/4)*0^n,n=0..20)

%t a[ n_] := SeriesCoefficient[((1 + 1/Sqrt[1 - 4 x])/2)^2, {x, 0, n}] (* _Michael Somos_, Dec 31 2013 *)

%t ats[y_]:=Sum[(-1)^(i-1)*y[[i]],{i,Length[y]}];Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],ats[#]>=0&]],{n,0,15,2}] (* _Gus Wiseman_, Jun 21 2021 *)

%Y Cf. A000984, A081294, A088218.

%Y The case of alternating sum = 0 is A001700.

%Y The case of alternating sum < 0 is A008549.

%Y This is the even bisection of A116406.

%Y The restriction to reversed partitions is A344611.

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

%Y A124754 gives the alternating sum of standard compositions.

%Y A316524 is the alternating sum of the prime indices of n.

%Y A344611 counts partitions of 2n with reverse-alternating sum >= 0.

%Y Cf. A000041, A000070, A000302, A000346, A003242, A027306, A032443, A058622, A058696, A119899, A344607, A344610.

%K easy,nonn

%O 0,2

%A _Paul Barry_, Feb 13 2006