|
%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
|
