OFFSET
0,4
COMMENTS
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.
LINKS
Jia Huang, Partially Palindromic Compositions, Journal of Integer Sequences, Vol. 26 (2023), Article 23.4.1.
Index entries for linear recurrences with constant coefficients, signature (0,2,2,-1).
FORMULA
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).
G.f.: (1+x-x^2-x^3)/(1-2*x^2-2*x^3+x^4).
EXAMPLE
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.
PROG
(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
(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
(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
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Jia Huang, Apr 06 2023
STATUS
approved