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,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

Table of n, a(n) for n=0..38.

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

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

Sequence in context: A305099 A292141 A374687 * A358827 A022403 A082550

Adjacent sequences: A362052 A362053 A362054 * A362056 A362057 A362058

Keyword

nonn,easy

Author

Jia Huang, Apr 06 2023

Status

approved