OFFSET
0,5
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}.
For n>=1, a(n) is the total number of runs of ones contained in binary strings of length n-1 that are devoid of runs of ones of length 1. - Félix Balado, Sep 18 2025
REFERENCES
D. E. Knuth, The Art of Computer Programming, Vol. 4A, Section 7.1.4.
LINKS
Michael De Vlieger, Table of n, a(n) for n = 0..4084
Félix Balado and Guénolé C. M. Silvestre, Systematic Enumeration of Fundamental Quantities Involving Runs in Binary Strings, arXiv:2602.10005 [math.CO], 2026. See p. 105.
Toufik Mansour and Mark 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.
Index entries for linear recurrences with constant coefficients, signature (4,-6,6,-5,2,-1).
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
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 *)
PROG
(Magma) [&+[k*Binomial(n-k, 2*k): k in [0..n]]: n in [0..40]]; // Bruno Berselli, Feb 13 2015
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Don Knuth, Apr 04 2008
STATUS
approved