login
Number of compositions of n with at most one even part.
11

%I #58 Apr 28 2024 11:05:36

%S 1,1,2,4,7,13,23,41,72,126,219,379,653,1121,1918,3272,5567,9449,16003,

%T 27049,45636,76866,129267,217079,364057,609793,1020218,1705036,

%U 2846647,4748101,7912559,13174889,21919488,36440646,60538443,100503667,166744997,276476129

%N Number of compositions of n with at most one even part.

%C 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

%C 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

%H Alois P. Heinz, <a href="/A208354/b208354.txt">Table of n, a(n) for n = 0..1000</a>

%H Jia Huang, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL26/Huang/huang8.html">Partially Palindromic Compositions</a>, J. Int. Seq. (2023) Vol. 26, Art. 23.4.1. See p. 11.

%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (2,1,-2,-1).

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

%F 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

%F a(n) = (2*(A099920(n-2)+A000045(n+2)) + A099920(n-1)+A000045(n+1)) / 5. - _Yuchun Ji_, Mar 21 2019

%e a(4) = 7: {4, 13, 31, 112, 121, 211, 1111}.

%e a(5) = 13: {5, 14, 41, 23, 32, 113, 131, 311, 1112, 1121, 1211, 2111, 11111}.

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

%p a:= n-> (<<0|1|0|0>, <0|0|1|0>, <0|0|0|1>, <-1|-2|1|2>>^n.

%p <<1, 1, 2, 4>>)[1, 1]:

%p seq(a(n), n=0..40);

%t LinearRecurrence[{2, 1, -2, -1}, {1, 1, 2, 4}, 40] (* _Jean-François Alcover_, Feb 18 2017 *)

%t CoefficientList[Series[((-1 + x)^2 (1 + x))/(-1 + x + x^2)^2, {x, 0, 50}], x] (* _Stefano Spezia_, Oct 29 2018 *)

%o (PARI) x='x+O('x^50); Vec((x+1)*(x-1)^2/(x^2+x-1)^2) \\ _Altug Alkan_, Oct 02 2018

%o (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

%o (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

%Y Cf. A010049, A211164.

%K nonn,easy

%O 0,3

%A _Alois P. Heinz_, Feb 25 2012