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

Author

Mikk Heidemaa, Aug 12 2014

Keywords

• nonn
• easy

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.

Examples

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

Links

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

Crossrefs

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

Programs

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

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

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)

Extensions

Typos in formula fixed by Colin Barker, Aug 12 2014