A208354 Number of compositions of n with at most one even part.

1, 1, 2, 4, 7, 13, 23, 41, 72, 126, 219, 379, 653, 1121, 1918, 3272, 5567, 9449, 16003, 27049, 45636, 76866, 129267, 217079, 364057, 609793, 1020218, 1705036, 2846647, 4748101, 7912559, 13174889, 21919488, 36440646, 60538443, 100503667, 166744997, 276476129

Offset

0,3

Comments

Conjecture: a(n) is the number of compositions of n if all the 1's are constrained to be in a single run; for example, a(7) counts the compositions 4,1,1,1 and 1,1,1,4 but not the compositions 1,4,1,1 and 1,1,4,1. - Gregory L. Simay, Sep 29 2018

Links

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Jia Huang, Partially Palindromic Compositions, J. Int. Seq. (2023) Vol. 26, Art. 23.4.1. See p. 11.

Index entries for linear recurrences with constant coefficients, signature (2,1,-2,-1).

Formula

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

a(n) = T(n+1) - T(n-1), where T(n) = ((2*n+3)*Fibonacci(n) - n*Fibonacci(n-1)) / 5 = A010049(n). - Gary Detlefs, Jan 19 2013

a(n) = (2*(A099920(n-2)+A000045(n+2)) + A099920(n-1)+A000045(n+1)) / 5. - Yuchun Ji, Mar 21 2019

Example

a(4) =  7: {4, 13, 31, 112, 121, 211, 1111}.
a(5) = 13: {5, 14, 41, 23, 32, 113, 131, 311, 1112, 1121, 1211, 2111, 11111}.
a(6) = 23: {6, 15, 51, 33, 114, 141, 411, 123, 132, 213, 231, 312, 321, 1113, 1131, 1311, 3111, 11112, 11121, 11211, 12111, 21111, 111111}.

Maple

a:= n-> (<<0|1|0|0>, <0|0|1|0>, <0|0|0|1>, <-1|-2|1|2>>^n.
         <<1, 1, 2, 4>>)[1, 1]:
seq(a(n), n=0..40);

Mathematica

LinearRecurrence[{2, 1, -2, -1}, {1, 1, 2, 4}, 40] (* Jean-François Alcover, Feb 18 2017 *)
CoefficientList[Series[((-1 + x)^2 (1 + x))/(-1 + x + x^2)^2, {x, 0, 50}], x] (* Stefano Spezia, Oct 29 2018 *)

Prog

(PARI) x='x+O('x^50); Vec((x+1)*(x-1)^2/(x^2+x-1)^2) \\ Altug Alkan, Oct 02 2018
(GAP) T:=n->((2*n+3)*Fibonacci(n)-n*Fibonacci(n-1))/5; a:=List([0..40], n->T(n+1)-T(n-1)); # Muniru A Asiru, Oct 28 2018
(Magma) I:=[1, 1, 2, 4]; [n le 4 select I[n] else 2*Self(n-1)+Self(n-2)-2*Self(n-3)-Self(n-4): n in [1..40]]; // Vincenzo Librandi, Oct 29 2018

Crossrefs

Cf. A010049, A211164.

Sequence in context: A239553 A319255 A136299 * A003116 A368299 A303666

Adjacent sequences: A208351 A208352 A208353 * A208355 A208356 A208357

Keyword

nonn,easy

Author

Alois P. Heinz, Feb 25 2012

Status

approved