A097896 Number of compositions of n with either all parts odd or all parts even.

1, 2, 2, 5, 5, 12, 13, 29, 34, 71, 89, 176, 233, 441, 610, 1115, 1597, 2840, 4181, 7277, 10946, 18735, 28657, 48416, 75025, 125489, 196418, 326003, 514229, 848424, 1346269, 2211077, 3524578, 5768423, 9227465, 15061424, 24157817, 39350313

Offset: 1

Author

Dubois Marcel (dubois.ml(AT)club-internet.fr), Sep 03 2004

Keywords

• nonn

Comments

Number of compositions of n with only even parts is 0 if n is odd, or 2^((n-2)/2) if n is even.

Examples

			For n=4: 1+1+1+1, 3+1, 1+3, 2+2, 4: total=5 so a(n)=5.
		

Links

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

Crossrefs

Cf. A096441, A000045.

Programs

Mathematica

f[n_] := Block[{}, Fibonacci[n] + If[EvenQ[n], 2^(n/2 - 1), 0]]; Table[ f[n], {n, 22}] (* Robert G. Wilson v, Sep 06 2004 *)
LinearRecurrence[{1,3,-2,-2},{1,2,2,5},40] (* Harvey P. Dale, Nov 27 2012 *)

Formula

a(2*n-1) = Fibonacci(2*n-1), a(2*n) = 2^(n-1)+Fibonacci(2*n). - Vladeta Jovovic, Sep 05 2004

a(n)= +a(n-1) +3*a(n-2) -2*a(n-3) -2*a(n-4). G.f.: -x*(-1-x+x^3+3*x^2)/ ((2*x^2-1) * (x^2+x-1)). - R. J. Mathar, Feb 06 2010

Extensions

More terms from Robert G. Wilson v, Sep 06 2004