A300451 - OEIS

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,2

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

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

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

EXAMPLE

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.

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

PROG

(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

(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