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

1, 2, 7, 26, 88, 272, 784, 2144, 5632, 14336, 35584, 86528, 206848, 487424, 1134592, 2613248, 5963776, 13500416, 30343168, 67764224, 150470656, 332398592, 730857472, 1600126976, 3489660928, 7583301632, 16424894464, 35467034624, 76369887232, 164014063616

Offset: 0

Author

Franck Maminirina Ramaharo, Mar 06 2018

Keywords

• nonn
• easy

Comments

First difference yields A295288.

1 and 7 are the only odd terms.

a(n) gives the number of words of length n defined over the alphabet {a,b,c,d} such that letters from {a,b} are only used in pairs of at most one, and consist of (a,a), (a,b) and (b,a).

Examples

			a(4) = 88. The corresponding words are cccc, cccd, ccdc, ccdd, cdcc, cdcd, cddc, cddd, dccc, dccd, dcdc, dcdd, ddcc, ddcd, dddc, dddd, caac, caca, ccaa, caad, cada, caad, cabc, cacb, ccab, cabd, cadb, cabd, cbac, cbca, ccba, cbad, cbda, cbad, daac, daca, dcaa, daad, dada, daad, dabc, dacb, dcab, dabd, dadb, dabd, dbac, dbca, dcba, dbad, dbda, dbad, aacc, acac, acca, aacd, acad, acda, aadc, adac, adca, aadd, adad, adda, abcc, acbc, accb, abcd, acbd, acdb, abdc, adbc, adcb, abdd, adbd, addb, bacc, bcac, bcca, bacd, bcad, bcda, badc, bdac, bdca, badd, bdad, bdda.
		

References

• Robert A. Beeler, How to Count: An Introduction to Combinatorics and Its Applications, Springer International Publishing, 2015.
• Ian F. Blake, The Mathematical Theory of Coding, Academic Press, 1975.

Links

• G. C. Greubel, Table of n, a(n) for n = 0..1000
• Hermann Gruber, Jonathan Lee and Jeffrey Shallit, Enumerating regular expressions and their languages, arXiv preprint arXiv:1204.4982 [cs.FL], 2012.
• Luis Manuel Rivera, Integer sequences and k-commuting permutations, arXiv preprint arXiv:1406.3081 [math.CO], 2014.
• Franck Ramaharo, A generating polynomial for the pretzel knot, arXiv:1805.10680 [math.CO], 2018.
• Index entries for linear recurrences with constant coefficients, signature (6,-12,8).

Crossrefs

Cf. A000079, A000292, A001788, A005448, A006003, A045943, A052481, A053730, A081908, A295288, A300184.

Programs

GAP

List([0..30],n->(3*n^2-3*n+8)*2^(n-3)); # Muniru A Asiru, Mar 09 2018

Magma

[(3*n^2-3*n+8)*2^(n-3): n in [0..30]]; // Vincenzo Librandi, Mar 10 2018

Maple

A := n -> (3*n^2 - 3*n + 8)*2^(n - 3);
seq(A(n), n = 0 .. 70);

Mathematica

Table[(3 n^2 - 3 n + 8) 2^(n - 3), {n, 0, 70}]
CoefficientList[Series[(1 - 4x + 7x^2)/(1 - 2x)^3, {x, 0, 30}], x] (* or *)
LinearRecurrence[{6, -12, 8}, {1, 2, 7}, 30] (* Robert G. Wilson v, Mar 07 2018 *)

Maxima

makelist((3*n^2 - 3*n + 8)*2^(n - 3), n, 0, 70);

PARI

a(n) = (3*n^2-3*n+8)*2^(n-3); \\ Altug Alkan, Mar 09 2018

Formula

G.f.: (1 - 4*x + 7*x^2)/(1 - 6*x + 12*x^2 - 8*x^3).

E.g.f: (1/2)*(3*x^2 + 2)*exp(2*x).

a(n) = ((3/4)*binomial(n, 2) + 1)*2^n.

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

a(n) = 3*A001788(n) + A000079(n).

a(n) = 6*a(n-1) - 12*a(n-2) + 8*a(n-3), for n >= 3, with a(0) = 1, a(1) = 2 and a(2) = 7.

a(n) = A300184(n,2).