Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%I #35 Jul 18 2023 12:26:30
%S 0,0,0,1,3,6,12,25,51,101,197,381,731,1392,2634,4958,9290,17337,32239,
%T 59760,110460,203651,374593,687567,1259597,2303449,4205493,7666560,
%U 13956532,25374108,46076436,83575025,151431099,274108826,495708364,895670733,1617003823,2916984121
%N a(n) = Sum_{k=0..n} k*binomial(n-k, 2*k).
%C Consider four related sequences: A_n = sum C(n-k, 2k), B_n = sum C(n-k, 2k+1), A^*_n = sum k*C(n-k, 2k), B^*_n = sum k*(C(n-k, 2k+1).
%C Sequence A_n, with generating function (1-z)/p(z) where p(z) = 1 - 2z + z^2 - z^3, is A005251.
%C Sequence B_n, with generating function z/p(z), is A005314.
%C Sequence A^*_n is the present sequence.
%C Sequence B^*_n is A118430, but shifted one place so that the generating function is z^4/p(z)^2 instead of z^3/p(z)^2.
%C These sequences have many interrelations; for example,
%C B_{n+1} - B_n = A_n; B^*_{n+1} - B^*_n = A^*_n;
%C A_{n+1} - A_n = B_{n-1}; A^*_{n+1} - A^*_n = B^*_{n-1} + B_{n-1}.
%D D. E. Knuth, The Art of Computer Programming, Vol. 4A, Section 7.1.4.
%H T. Mansour and M. Shattuck, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL13/Shattuck/shattuck3.html">Counting Peaks and Valleys in a Partition of a Set</a>, J. Int. Seq. 13 (2010), #10.6.8, partitions of [n] with 2 blocks with 1 peak.
%F G.f.: x^3*(1-x)/(1-2*x+x^2-x^3)^2.
%F a(n) ~ c * d^n * n, where d = A109134 = 1.75487766624669276... is the root of the equation d*(d-1)^2 = 1, c = 0.072838349685011... is the root of the equation 529*c^3 - 207*c^2 + 26*c = 1. - _Vaclav Kotesovec_, May 25 2015
%p a:= n-> (Matrix([[0,0,1,1,-3,-5]]). Matrix(6, (i,j)-> if (i=j-1) then 1 elif j=1 then [4,-6,6,-5,2,-1][i] else 0 fi)^n)[1,1]: seq(a(n), n=0..37); # _Alois P. Heinz_, Aug 13 2008
%t a[n_] := ({0, 0, 1, 1, -3, -5} . MatrixPower[ Table[If[i == j-1, 1, If[j == 1, {4, -6, 6, -5, 2, -1}[[i]], 0]], {i, 6}, {j, 6}], n])[[1]]; Table[a[n], {n, 0, 37}] (* _Jean-François Alcover_, Feb 13 2015, after _Alois P. Heinz_ *)
%t CoefficientList[Series[x^3 (1 - x)/(1 - 2 x + x^2 - x^3)^2, {x, 0, 40}], x] (* _Vincenzo Librandi_, Aug 15 2015 *)
%o (Magma) [&+[k*Binomial(n-k, 2*k): k in [0..n]]: n in [0..40]]; // _Bruno Berselli_, Feb 13 2015
%Y Cf. A005251, A005314, A118430, A136445, A137356-A137361.
%K nonn,easy
%O 0,5
%A _Don Knuth_, Apr 04 2008