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

Author

Alois P. Heinz, Feb 25 2012

Keywords

• nonn
• easy

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

This also gives the number of ordered partitions of n into parts of sizes 1, 2, and 3 with at most one 3. - Jerrold Grossman, Apr 03 2024

Examples

			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}.
		

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).

Crossrefs

Cf. A010049, A211164.

Programs

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

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 *)

PARI

x='x+O('x^50); Vec((x+1)*(x-1)^2/(x^2+x-1)^2) \\ Altug Alkan, Oct 02 2018

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