A215595 Number of strings of length n, formed from the 26-letter English alphabet, which contain the substring xy.

0, 0, 1, 52, 2027, 70226, 2280825, 71112600, 2155562551, 64005323902, 1870809923477, 54006556365476, 1543466751232275, 43746473462661450, 1231293799939647601, 34451045198171912752, 959005856055827234927, 26576960554539062120726, 733650711461388661963725

Offset

0,4

Links

G. C. Greubel, Table of n, a(n) for n = 0..700

Index entries for linear recurrences with constant coefficients, signature (52,-677,26).

Formula

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

a(n) = 52*a(n-1) - 677*a(n-2) + 26*a(n-3). - Charles R Greathouse IV, Aug 16 2012

G.f.: x/(1 - 52*x + 677*x^2 - 26*x^3). - Alexander R. Povolotsky, Aug 16 2012

a(n) = (1/168)*(13 +2*sqrt(42))^(-n)*(-(84+13*sqrt(42))*(13+2*sqrt(42))^(2*n) + 168*(338+52*sqrt(42))^n-84+13*sqrt(42)). - Alexander R. Povolotsky, Aug 16 2012

a(n) = Sum_{j=1..n} (-1)^(j+1) * B(n,j), where B(n,j) is the number of ways to place k occurrences of xy in a string of length n, and then choosing arbitrary letters for the n - 2k remaining positions. B(n,j) = product((n-i),i=j..(2*j-1)) / j! * 26^(n-2*j).

Example

For n = 2, the only such string is xy. For n = 3, there are 26 strings of the form *xy and 26 of the form xy*. For n = 4, there are 26^2 of each of the forms xy**, *xy* and **xy, but we double count xyxy, so the answer for n=4 is 3*26^2 - 1 = 2027.

Mathematica

Join[{0}, CoefficientList[Series[x/(1 - 52*x + 677*x^2 - 26*x^3), {x, 0, 50}], x]] (* G. C. Greubel, Feb 26 2017 *)

Prog

(PARI) x='x+O('x^50); concat([0, 0], Vec(x/(1 - 52*x + 677*x^2 - 26*x^3))) \\ G. C. Greubel, Feb 26 2017

Crossrefs

Cf. A186314 (same problem for ternary strings).

Sequence in context: A188389 A169997 A342898 * A134552 A004296 A097837

Adjacent sequences: A215592 A215593 A215594 * A215596 A215597 A215598

Keyword

nonn,easy

Author

David Kofoed Wind, Aug 16 2012

Status

approved