A136444 a(n) = Sum_{k=0..n} k*binomial(n-k, 2*k).

0, 0, 0, 1, 3, 6, 12, 25, 51, 101, 197, 381, 731, 1392, 2634, 4958, 9290, 17337, 32239, 59760, 110460, 203651, 374593, 687567, 1259597, 2303449, 4205493, 7666560, 13956532, 25374108, 46076436, 83575025, 151431099, 274108826, 495708364, 895670733, 1617003823, 2916984121

Offset: 0

Author

Don Knuth, Apr 04 2008

Keywords

• nonn
• easy

Comments

Consider four related sequences: A_n = sum C(n-k, 2*k), B_n = sum C(n-k, 2*k+1), A^*_n = sum k*C(n-k, 2*k), B^*_n = sum k*C(n-k, 2*k+1).

Sequence A_n, with generating function (1-z)/p(z) where p(z) = 1 - 2*z + z^2 - z^3, is A005251.

Sequence B_n, with generating function z/p(z), is A005314.

Sequence A^*_n is the present sequence.

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.

These sequences have many interrelations; for example,

B_{n+1} - B_n = A_n; B^*_{n+1} - B^*_n = A^*_n;

A_{n+1} - A_n = B_{n-1}; A^*{n+1} - A^*_n = B^*{n-1} + B_{n-1}.

References

• D. E. Knuth, The Art of Computer Programming, Vol. 4A, Section 7.1.4.

Links

• T. Mansour and M. Shattuck, Counting Peaks and Valleys in a Partition of a Set, J. Int. Seq. 13 (2010), #10.6.8, partitions of [n] with 2 blocks with 1 peak.

Crossrefs

Cf. A005251, A005314, A118430, A136445, A137356-A137361.

Programs

Magma

[&+[k*Binomial(n-k, 2*k): k in [0..n]]: n in [0..40]]; // Bruno Berselli, Feb 13 2015

Maple

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

Mathematica

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 *)
CoefficientList[Series[x^3 (1 - x)/(1 - 2 x + x^2 - x^3)^2, {x, 0, 40}], x] (* Vincenzo Librandi, Aug 15 2015 *)

Formula

G.f.: x^3*(1-x)/(1-2*x+x^2-x^3)^2.

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