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

1, 1, 1, 3, 3, 7, 11, 17, 33, 49, 89, 147, 243, 423, 691, 1185, 1985, 3329, 5649, 9443, 15971, 26855, 45179, 76209, 128097, 215921, 363433, 611827, 1030611, 1734599, 2921443, 4918593, 8281473, 13945473, 23478689, 39535299, 66566851, 112082503, 188725611

Offset: 0

Author

Jia Huang, Apr 06 2023

Keywords

• nonn
• easy

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.

Examples

			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.
		

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).

Crossrefs

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

Programs

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

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).