A242026 Number of non-palindromic n-tuples of 4 distinct elements.

0, 12, 48, 240, 960, 4032, 16128, 65280, 261120, 1047552, 4190208, 16773120, 67092480, 268419072, 1073676288, 4294901760, 17179607040, 68719214592, 274876858368, 1099510579200, 4398042316800, 17592181850112, 70368727400448, 281474959933440, 1125899839733760

Offset

1,2

Comments

Non-palindromic vs palindromic (DNA) sequences (e.g., {a,c,a,c} is a non-palindromic sequence but {a,c,c,a} is palindromic). Useful in bioinformatics.

Links

Table of n, a(n) for n=1..25.

Index entries for linear recurrences with constant coefficients, signature (4,4,-16).

Formula

a(n) = 2^(n-1) * (2^(n+1) + (-1)^n - 3).

a(n) = 4^n - 4^ceiling(n/2) = A000302(n) - A056450(n).

From Colin Barker, Aug 12 2014: (Start)

a(n) = 4*a(n-1) + 4*a(n-2) - 16*a(n-3).

G.f.: 12*x^2 / ((2*x-1)*(2*x+1)*(4*x-1)). (End)

Example

For n=2 the a(2)=12 solutions (non-palindromic 2-tuples over 4 distinct elements {a,c,g,t}) are: {a,c}, {a,g}, {a,t}, {c,a}, {c,g}, {c,f}, {g,a},{g,c}, {g,t}, {t,a}, {t,c}, {t,g}.

Mathematica

Table[2^(n-1) * (2^(n+1) + (-1)^n - 3), {n, 66}]
LinearRecurrence[{4, 4, -16}, {0, 12, 48}, 30] (* Harvey P. Dale, May 24 2023 *)

Prog

(PARI) a(n) = ((-1)^n - 3)*2^(n-1) + 4^n; \\ Michel Marcus, Aug 12 2014
(PARI) concat(0, Vec(12*x^2 / ((2*x-1)*(2*x+1)*(4*x-1)) + O(x^100))) \\ Colin Barker, Aug 12 2014

Crossrefs

Cf. A000302, A056450, A233411, A242278, A240437.

Sequence in context: A061148 A339760 A221908 * A340727 A052601 A003498

Adjacent sequences: A242023 A242024 A242025 * A242027 A242028 A242029

Keyword

nonn,easy

Author

Mikk Heidemaa, Aug 12 2014

Extensions

Typos in formula fixed by Colin Barker, Aug 12 2014

Status

approved