A186314 -id:A186314 - cp's OEIS frontend

A186244 Number of ternary strings of length n containing 00.

0, 0, 1, 5, 21, 79, 281, 963, 3217, 10547, 34089, 108955, 345137, 1085331, 3392377, 10549739, 32667201, 100782787, 309946697, 950599131, 2908512145, 8880484019, 27064776729, 82350874699, 250212362465, 759269653155, 2301393567721, 6968615051195

Offset: 0

Toby Gottfried, Feb 15 2011

G. C. Greubel, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (5,-4,-6).

Cf. A028859, A186314 (number of ternary strings of length n containing 01), A351529 (4-ary), A351530 (5-ary).

t = {0, 0, 1}; Do[AppendTo[t, 3 t[[-1]] + 2*(3^(n - 3) - t[[-3]])], {n, 3, 40}]; t (* T. D. Noe, Nov 11 2013 *)
CoefficientList[Series[x^2/(3*x - 1)/(2*x^2 + 2*x - 1), {x,0,50}], x] (* G. C. Greubel, Feb 19 2017 *)

x='x+O('x^50); Vec(x^2/(3*x - 1)/(2*x^2 + 2*x - 1)) \\ G. C. Greubel, Feb 19 2017

a(n)=3^n - ([1, 3; 1, 1]^n*[2; 1])[2, 1] \\ Charles R Greathouse IV, Feb 19 2017

a(n) = 3*a(n-1) + 2*(3^(n-3) - a(n-3)). This recursive formula is based on adding any of {0,1,2} to strings of length n-1 which already have 00 in them, or {100,200} to strings of length n-3 which do not.  For n = 3, we add {0,1,2} to 00, and {100,200} to the empty string to get the 5 strings of length 3 which have 00 in them. For n = 4, we add {0,1,2} to those 5, and {100,200} to all three strings of length 1, to get the 21 strings of length 4.
a(n) = -(1/3)*(1+sqrt(3))^n*sqrt(3) - (1/2)*(1+sqrt(3))^n + 3^n - (1/2)*(1-sqrt(3))^n + (1/3)*sqrt(3)*(1-sqrt(3))^n. - Alexander R. Povolotsky, Feb 18 2011
G.f.: x^2/(3*x-1)/(2*x^2+2*x-1). - Simon Plouffe, Feb 26 2011
a(n) = 3^n - A028859(n). - Toby Gottfried, Mar 06 2013
a(n) = 2*a(n-1) + 2*a(n-2) + 3^(n-2). This recursive formula is based on adding the case where the last two digits are not the same to the case where the last two digits are the same. In the first case, there are 2*a(n-1) strings, since any string of length n-1 containing 00 can be made into an appropriate string of length n by appending either of the values {0,1,2} that are not the same as the (n-1)-th digit. The case where the last two digits are the same has two subcases: to any string of length n-2 containing 00, we can append 11 or 22. There are 2*a(n-2) strings in this subcase. Or, to any string of length n-2 (whether or not it contains 00), we can append 00. There are 3^(n-2) strings in this subcase. - Todd CadwalladerOlsker, Oct 24 2020
a(n) = 5*a(n-1) - 4*a(n-2) - 6*a(n-3). - Kevin Ryde, Oct 24 2020
E.g.f.: exp(x)*(exp(2*x) - cosh(sqrt(3)*x) - 2*sinh(sqrt(3)*x)/sqrt(3)). - Stefano Spezia, Mar 02 2024

A338230 Number of ternary strings of length n that contain at least two 0's and at most one 1.

Original entry on oeis.org

0, 0, 1, 7, 27, 81, 213, 519, 1207, 2725, 6033, 13179, 28515, 61257, 130861, 278287, 589551, 1244877, 2621097, 5504643, 11533915, 24116785, 50331141, 104857047, 218103207, 452984181, 939523393, 1946156299, 4026531027, 8321498265, 17179868253, 35433479199, 73014442975, 150323854237

Offset: 0

Enrique Navarrete, Jan 30 2021

			a(4) = 27 since the strings consist of 0000, the 4 permutations of 0001, the 4 permutations of 0002, the 6 permutations of 0022, and the 12 permutations of 0012. The total number of strings is then 1 + 4 + 4 + 6 + 12 = 27.

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

Cf. A186244, A186314.

Cf. A338229, A338232.

CoefficientList[Series[Exp[x](Exp[x]-1-x)(1+x),{x,0,32}],x]Table[i!,{i,0,32}] (* Stefano Spezia, Jan 31 2021 *)

a(n) = 2^n + n*2^(n-1) - 2*binomial(n,2) - 2*n - 1.
E.g.f.: exp(x)*(exp(x) - 1 - x)*(1 + x).
G.f.: x^2*(1 - 3*x^2)/((1 - 2*x)^2*(1 - x)^3). - Stefano Spezia, Jan 31 2021

A141688 Triangle T(n, k) = Fibonacci(2k)T(n-1, k) + Fibonacci(2(n-k+1))T(n-1, k-1), with T(n, 1) = T(n, n) = 1, read by rows.

Original entry on oeis.org

1, 1, 1, 1, 6, 1, 1, 26, 26, 1, 1, 99, 416, 99, 1, 1, 352, 5407, 5407, 352, 1, 1, 1200, 62616, 227094, 62616, 1200, 1, 1, 3977, 673728, 8212854, 8212854, 673728, 3977, 1, 1, 12918, 6889153, 269486766, 903413940, 269486766, 6889153, 12918, 1, 1, 41338, 67863290, 8256432767, 88493861004, 88493861004, 8256432767, 67863290, 41338, 1

Offset: 1

Roger L. Bagula, Sep 09 2008

Row sums are: {1, 2, 8, 54, 616, 11520, 354728, 17781120, 1456191616, 193636396800, ...}.

			Triangle begins as:
  1;
  1,     1;
  1,     6,       1;
  1,    26,      26,         1;
  1,    99,     416,        99,         1;
  1,   352,    5407,      5407,       352,        1;
  1,  1200,   62616,    227094,     62616,     1200,       1;
  1,  3977,  673728,   8212854,   8212854,   673728,    3977,     1;
  1, 12918, 6889153, 269486766, 903413940,269486766, 6889153, 12918, 1;

G. C. Greubel, Rows n = 1..50 of the triangle, flattened

Cf. A088305, A186314.

function T(n,k)
  if k eq 1 or k eq n then return 1;
  else return Fibonacci(2*(n-k+1))*T(n-1, k-1) + Fibonacci(2*k)*T(n-1, k);
  end if; return T;
end function;
[T(n,k): k in [1..n], n in [1..12]]; // G. C. Greubel, Mar 29 2021

(* First program *)
b[n_]:= b[n]= If[n==0, 1, Sum[k*b[n-k], {k,n}]];
T[n_, k_]:= If[k==1 || k==n, 1, b[n-k+1]*T[n-1, k-1] + b[k]*T[n-1, k]];
Table[T[n, k], {n,12}, {k,n}]//Flatten (* modified by G. C. Greubel, Mar 29 2021 *)
(* Second program *)
T[n_, k_]:= T[n, k]= If[k==1 || k==n, 1, Fibonacci[2*(n-k+1)]*T[n-1, k-1] + Fibonacci[2*k]*T[n-1, k]];
Table[T[n, k], {n, 12}, {k, n}]//Flatten (* G. C. Greubel, Mar 29 2021 *)

@CachedFunction
def T(n,k): return 1 if (k==1 or k==n) else fibonacci(2*(n-k+1))*T(n-1, k-1) + fibonacci(2*k)*T(n-1, k)
flatten([[T(n,k) for k in (1..n)] for n in (1..12)]) # G. C. Greubel, Mar 29 2021

Let A088305(n) be defined by b(n) = Sum_{j=1..n} j*b(n-j), with b(0)=1, then T(n, k) = b(n-k+1)*T(n-1, k-1) + b(k)*T(n-1, k) with T(n,1) = T(n,n) = 1.
From G. C. Greubel, Mar 29 2021: (Start)
T(n, k) = Fibonacci(2*k)*T(n-1, k) + Fibonacci(2*(n-k+1))*T(n-1, k-1), with T(n, 1) = T(n, n) = 1.
T(n, 2) = A186314(n+1). (End)

Edited by G. C. Greubel, Mar 29 2021

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

Original entry on oeis.org

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

Offset: 0

David Kofoed Wind, Aug 16 2012

			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.

G. C. Greubel, Table of n, a(n) for n = 0..700
Index entries for linear recurrences with constant coefficients, signature (52,-677,26).

Cf. A186314 (same problem for ternary strings).

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

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

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

A309000 Number of strings of length n from a 3-symbol alphabet (A,B,C, say) containing at least one "A" and at least two "B"s.

Original entry on oeis.org

3, 22, 105, 416, 1491, 5034, 16365, 51892, 161799, 498686, 1524705, 4635528, 14037627, 42391378, 127763925, 384536924, 1156232175, 3474201510, 10434138825, 31326533680, 94029932643, 282194655482, 846802070205, 2540859195396, 7623517110231, 22872497487694

Offset: 3

Adam Vellender, Jul 04 2019

This sequence can be thought of as the number of ways of rolling n 3-sided dice (with sides "A", "B", and "C") and obtaining at least one A and at least two B's.

The general formula is readily proved true by counting arguments.

			Suppose three-sided dice each have sides labeled A,B,C.
If there are three dice, then ABB, BAB, and BBA are the three strings resulting from rolling the dice satisfying the property of at least one A and at least two B's, hence a(3)=3 [Note a(0)=a(1)=a(2)=0].
If there are four such dice, there are 22 such permutations, hence a(4)=22: AABB, ABAB, ABBA, ABBB, ABBC, ABCB, ACBB, BAAB, BABA, BABB, BABC, BACB, BBAA, BBAB, BBAC, BBBA, BBCA, BCAB, BCBA, CABB, CBAB, CBBA.

Index entries for linear recurrences with constant coefficients, signature (9,-31,51,-40,12).

Cf. A269914, A269915, A269916, A269917, A186244, A186314.

[3^n-2^(n+1)-n*2^(n-1)+n+1: n in [3..40]]; // Vincenzo Librandi, Jul 05 2019

Array[3^# - 2^(# + 1) - # 2^(# - 1) + # + 1 &, 27, 3] (* or *)
CoefficientList[Series[(-3 + 5 x)/((-1 + 3 x) (1 - 3 x + 2 x^2)^2), {x, 0, 26}], x] (* Michael De Vlieger, Jul 04 2019 *)

[3**n-2**(n+1)-n*2**(n-1)+n+1 for n in range(3,20)]

a(n) = 3^n - 2^(n+1) - n*2^(n-1) + n + 1.
G.f.: x^3*(-3 + 5*x)/((-1 + 3*x)*(1 - 3*x + 2*x^2)^2). - Michael De Vlieger, Jul 04 2019.
a(n) = 9*a(n-1) - 31*a(n-2) + 51*a(n-3) - 40*a(n-4) + 12*a(n-5) for n > 7. - Stefano Spezia, Jul 05 2019

cp's OEIS Frontend

A186244 Number of ternary strings of length n containing 00.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

A338230 Number of ternary strings of length n that contain at least two 0's and at most one 1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A141688 Triangle T(n, k) = Fibonacci(2*k)*T(n-1, k) + Fibonacci(2*(n-k+1))*T(n-1, k-1), with T(n, 1) = T(n, n) = 1, read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

Sage

Formula

Extensions

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A309000 Number of strings of length n from a 3-symbol alphabet (A,B,C, say) containing at least one "A" and at least two "B"s.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

Python

Formula

A141688 Triangle T(n, k) = Fibonacci(2k)T(n-1, k) + Fibonacci(2(n-k+1))T(n-1, k-1), with T(n, 1) = T(n, n) = 1, read by rows.