OFFSET
0,4
COMMENTS
A composition (c(1), c(2), ..., c(k)) is anti-palindromic modulo 3 if c(i) and c(k+1-i) are not congruent modulo 3 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 (1,0,3,-1).
FORMULA
a(n) = Sum_{3*i + j + 2*r + 2*s + 3*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^3)/(1 - x - 3*x^3 + x^4).
EXAMPLE
There are a(5) = 7 compositions of n = 5 that are anti-palindromic modulo 3: 5, 32, 23, 311, 113, 221, 122. Note that 41 and 14 are anti-palindromic but not anti-palindromic modulo 3.
PROG
(PARI) a(n) = {sum(i=0, n\3, sum(d=0, (n-3*i)\3, sum(s=0, (n-3*i-3*d)\2, 2^i * binomial(i+s-1, s) * binomial(i+d-1, d) * sum(r=0, (n-3*i-3*d-2*s)\2, my(j=n-3*i-3*d-2*s-2*r); (-1)^r * binomial(i+j, j) * binomial(i, r) ))))} \\ Andrew Howroyd, Apr 10 2023
(PARI) Vec((1 - x^3)/(1 - x - 3*x^3 + x^4) + O(x^41)) \\ Andrew Howroyd, Apr 11 2023
(PARI) my(p=Mod('x, 'x^4-'x^3-3*'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