A362057 Number of compositions of n that are anti-palindromic modulo 3.

1, 1, 1, 3, 5, 7, 15, 27, 43, 81, 147, 249, 449, 809, 1409, 2507, 4485, 7903, 14015, 24963, 44187, 78329, 139203, 246801, 437601, 776881, 1378081, 2444083, 4337125, 7694487, 13648655, 24215947, 42962283, 76213761, 135212947, 239883849, 425562849, 754987929

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

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

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

Cf. A000213 (anti-palindromic compositions), A362055.

Sequence in context: A061950 A166093 A165785 * A261646 A303027 A217615

Adjacent sequences: A362054 A362055 A362056 * A362058 A362059 A362060

Keyword

nonn,easy

Author

Jia Huang, Apr 06 2023

Status

approved