A362055 - OEIS

%I #27 May 09 2023 22:14:10

%S 1,1,1,3,3,7,11,17,33,49,89,147,243,423,691,1185,1985,3329,5649,9443,

%T 15971,26855,45179,76209,128097,215921,363433,611827,1030611,1734599,

%U 2921443,4918593,8281473,13945473,23478689,39535299,66566851,112082503,188725611

%N Number of compositions of n that are anti-palindromic modulo 2.

%C A composition (c(1), c(2), ..., c(k)) is anti-palindromic modulo 2 if c(i) and c(k+1-i) are not congruent modulo 2 whenever 1 <= i <= k/2.

%H Jia Huang, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL26/Huang/huang8.html">Partially Palindromic Compositions</a>, Journal of Integer Sequences, Vol. 26 (2023), Article 23.4.1.

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

%F a(n) = Sum_{3*i + j + r + 2*s + 2*d = n} (-1)^r * 2^i * binomial(i+j,j) * binomial(i,r) * binomial(i+s-1,s) * binomial(i+d-1,d).

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

%e There are a(4) = 3 compositions of n = 4 that are anti-palindromic modulo 2: 4, 211, and 112. Although 31 and 13 are anti-palindromic, they are not anti-palindromic modulo 2.

%o (PARI) a(n) = {sum(i=0, n\3,  sum(s=0, (n-3*i)\2, sum(d=0, (n-3*i)\2-s, 2^i * binomial(i+s-1,s) * binomial(i+d-1,d) * sum(j=0, n-3*i-2*d-2*s, my(r=n-3*i-2*d-2*s-j); (-1)^r * binomial(i+j,j) * binomial(i,r) ))))} \\ _Andrew Howroyd_, Apr 10 2023

%o (PARI) Vec((1 + x - x^2 - x^3)/(1 - 2*x^2 - 2*x^3 + x^4) + O(x^41)) \\ _Andrew Howroyd_, Apr 11 2023

%o (PARI) my(p=Mod('x, 'x^4-2*'x^2-2*'x+1)); a(n) = vecsum(Vec(lift(p^(n+1)))); \\ _Kevin Ryde_, Apr 12 2023

%Y Cf. A000213 (number of anti-palindromic compositions), A362057.

%K nonn,easy

%O 0,4

%A _Jia Huang_, Apr 06 2023