OFFSET
0,5
COMMENTS
From Gus Wiseman, Jun 26 2022: (Start)
Also the number of integer compositions of n + 1 with an even part other than the first or last. For example, the a(3) = 1 through a(5) = 12 compositions are:
(121) (122) (123)
(221) (141)
(1121) (222)
(1211) (321)
(1122)
(1212)
(1221)
(2121)
(2211)
(11121)
(11211)
(12111)
The odd version is A274230.
(End)
LINKS
Colin Barker, Table of n, a(n) for n = 0..1000
Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, Cambridge Univ. Press, 2009, page 34.
Index entries for linear recurrences with constant coefficients, signature (4,-4,-1,2).
FORMULA
O.g.f.: x^3/( (1-x)^2*(1-x^2/(1-x))*(1-2x) ).
a(n) ~ 2^n.
From Colin Barker, Nov 03 2016: (Start)
a(n) = (1 + 2^n - (2^(-n)*((1-sqrt(5))^n*(-2+sqrt(5)) + (1+sqrt(5))^n*(2+sqrt(5))))/sqrt(5)).
a(n) = 4*a(n-1) - 4*a(n-2) - a(n-3) + 2*a(n-4) for n > 3. (End)
a(n) = 2^n - Fibonacci(n+3) + 1. - Ehren Metcalfe, Dec 27 2018
E.g.f.: 2*exp(x/2)*(5*exp(x)*cosh(x/2) - 5*cosh(sqrt(5)*x/2) - 2*sqrt(5)*sinh(sqrt(5)*x/2))/5. - Stefano Spezia, Apr 06 2022
EXAMPLE
a(4) = 4 because we have: 0011, 0110, 0111, 1011.
MATHEMATICA
nn=40; a=x/(1-x); CoefficientList[Series[a^2 x/(1-a x)/(1-2x), {x, 0, nn}], x]
(* second program *)
Table[Length[Select[Tuples[{0, 1}, n], MatchQ[#, {___, 0, 1, 1, ___}]&]], {n, 0, 10}] (* Gus Wiseman, Jun 26 2022 *)
PROG
(PARI) concat(vector(3), Vec(x^3/(-2*x^4+x^3+4*x^2-4*x+1) + O(x^40))) \\ Colin Barker, Nov 03 2016
CROSSREFS
For the contiguous pattern (1,1) or (0,0) we have A000225.
For the contiguous pattern (1,0,1) or (0,1,0) we have A000253.
For the contiguous pattern (1,0) or (0,1) we have A000295.
Numbers whose binary expansion is of this type are A004750.
For the contiguous pattern (1,1,1) or (0,0,0) we have A050231.
The not necessarily contiguous version is A324172.
KEYWORD
nonn,easy
AUTHOR
Geoffrey Critzer, Nov 26 2013
STATUS
approved