Toby Gottfried - cp's OEIS frontend

A231430 Number of ternary sequences which contain 000.

0, 0, 0, 1, 5, 21, 81, 295, 1037, 3555, 11961, 39667, 130049, 422403, 1361385, 4359115, 13880129, 43984227, 138795849, 436367131, 1367434577, 4272615603, 13315096089, 41397076939, 128429930465, 397665266595, 1229127726825, 3792875384251, 11686625364785

Offset: 0

Toby Gottfried, Nov 09 2013

nonn

Recurrence formula given below, a(n) = 3*a(n-1) + 2* (3^(n-4) - a(n-4)) based on following recursive construction: To a string of length (n-1) containing 000 add any of {0,1,2}. To a string of length (n-4) NOT containing 000, add 1000 or 2000. These two operations result in the two terms of the formula.

			For n = 3, the only string is 000.
For n = 4, the 5 strings are: 0000,0001,0002,1000,2000.
For n = 5, there are: 1 with 5 0's, 12 with 4 0's, and 8 with just 3; total 21.

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

Cf. A119826 (without 000), A119827 (exactly one 000).

Cf. A186244 (with 00).

t = {0, 0, 0, 1}; Do[AppendTo[t, 3 t[[-1]] + 2*(3^(n - 4) - t[[-4]])], {n, 4, 30}]; t (* T. D. Noe, Nov 11 2013 *)
(* or *)
nn=28;r=Solve[{s==2x s+2x a+2x b+1,a==x s,b==x a,c==3x c+x b},{s,a,b,c}];CoefficientList[Series[c/.r,{x,0,nn}],x] (* Geoffrey Critzer, Jan 14 2014 *)
CoefficientList[Series[x^3/(1-5x+4x^2+4x^3+6x^4),{x,0,40}],x] (* or *) LinearRecurrence[{5,-4,-4,-6},{0,0,0,1},40] (* Harvey P. Dale, Jul 27 2021 *)

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

G.f.: x^3/(1 - 5*x + 4*x^2 + 4*x^3 +6*x^4). - Geoffrey Critzer, Jan 14 2014

A216211 Number of self-avoiding walks of any length from NW to SW corners of a grid or lattice with n rows and 4 columns.

Original entry on oeis.org

1, 4, 28, 178, 1008, 5493, 29879, 163357, 895519, 4911542, 26932856, 147666219, 809584243, 4438588016, 24334993398, 133419407518, 731487440774, 4010463570150, 21987820817522, 120550714106036, 660932932241338, 3623639639745022, 19867014703421770, 108923158026586497, 597183548915194615

Offset: 1

Toby Gottfried, Mar 13 2013

As n increases, the ratio of a(n)/a(n-1) appears to converge to around 5.483.

			For n=2, using the notation D(own), R(ight), L(eft), U(p), the 4 walks are {D, RDL, RRDLL, RRRDLLL}.

Andrew Howroyd, Table of n, a(n) for n = 1..100

Column 4 of A271465. Cf. A005409 for grids with 3 rows, A006189 for grids with 3 columns, and A214931 for grids with 4 rows.

a[n_] := Block[{t=0,w,b=Array[1&, {n,4}]}, w[rr_,cc_] := Block[{r,c}, If[rr+cc == 2, t++, Do[{r,c} = {rr,cc} + e; If[0 0, b[[r,c]] = 0; w[r, c]; b[[r,c]] = 1], {e, {{-1,0}, {1,0}, {0,1}, {0,-1}}}]]]; b[[n,1]] = 0; w[n,1]; t]; a /@ Range[6] (* Giovanni Resta, Mar 13 2013 *)

Conjectures from Colin Barker, Nov 18 2017: (Start)
G.f.: x*(1 - 8*x + 34*x^2 - 66*x^3 + 21*x^4 + 85*x^5 - 64*x^6 - 45*x^7 + 26*x^8 + 11*x^9 - 3*x^10 - x^11) / ((1 - 8*x + 15*x^2 - 5*x^3 - 9*x^4 + 2*x^5 + x^6)*(1 - 4*x + 7*x^2 - 3*x^3 - 7*x^4 + 2*x^5 + x^6)).
a(n) = 12*a(n-1) - 54*a(n-2) + 124*a(n-3) - 133*a(n-4) - 16*a(n-5) + 175*a(n-6) - 94*a(n-7) - 69*a(n-8) + 40*a(n-9) + 12*a(n-10) - 4*a(n-11) - a(n-12) for n>12.
(End)

a(13)-a(14) from Giovanni Resta, Mar 13 2013

Terms a(15) and beyond from Andrew Howroyd, Apr 08 2016

A214931 Number of self-avoiding walks of any length from NW to SW corners of a grid or lattice with 4 rows and n columns.

Original entry on oeis.org

1, 8, 38, 178, 844, 4012, 19072, 90658, 430938, 2048450, 9737260, 46285868, 220018976, 1045856010, 4971456754, 23631725866, 112332963420, 533972624844, 2538228811648, 12065422836242, 57352760145834, 272625264866098, 1295919060481740, 6160126839867820

Offset: 1

Toby Gottfried, Mar 09 2013

			For n=2, and moves U(p), D(own), R(ight), L(eft), the a(2)=8 walks are {DDD, DRDDL, DRDLD, DDRDL, RDDDL, RDDLD, RDLDD, RDLDRDL} with only the last touching all 8 squares of the grid.
Illustration of the 8 walks of a(2):
    .__      __      __        .       .        .       .     __
     __|    .  |    .  |    |__     |__      |  .    |  .     __|
    |  .     __|    .  |     __|     . |     |__     |  .    |__
    |  .    |  .     __|    |  .     __|      __|    |  .     __|

Andrew Howroyd, Table of n, a(n) for n = 1..100

Row 4 of A271465.
Cf. A181688 (maximal walks with same conditions).
Cf. A005409 (grids with 3 rows), A006189 (grids with 3 columns).
Cf. A216211 (grids with 4 columns).

Empirical recurrence: a(1,...,5) = (1, 8, 38, 178, 844), a(n) = 7*a(n-1) - 12*a(n-2) + 7*a(n-3) - 3*a(n-4) - 2*a(n-5). - Giovanni Resta, Mar 13 2013

Empirical g.f.: x*(1+x-6*x^2+x^3+x^4)/(1-7*x+12*x^2-7*x^3+3*x^4+2*x^5). - Bruno Berselli, Mar 13 2013

Missing a(7) and a(13)-a(14) from Giovanni Resta, Mar 13 2013

a(15)-a(24) from Andrew Howroyd, Apr 08 2016

A186314 Number of ternary strings of length n which contain 01.

Original entry on oeis.org

0, 0, 1, 6, 26, 99, 352, 1200, 3977, 12918, 41338, 130779, 410048, 1276512, 3950929, 12170598, 37343834, 114209811, 348332320, 1059927312, 3218870105, 9758944470, 29544747706, 89335651851, 269843267456, 814337329344, 2455598257057, 7399746051270

Offset: 0

Toby Gottfried, Feb 17 2011

			The recursive formula is based on extending such a string of length n-1 with {0,1,2} or extending a non-matching string of length (n-2) with "01".  For n=2, there is just 1 string: "01". For n=3, we append {0,1,2} to "01" and append "01" to {"0","1","2"}, the three non-matching strings of length 1, for a total of a(3)=6.

Index entries for linear recurrences with constant coefficients, signature (6,-10,3).

Cf. A186244 (ternary strings which contain 00).

nn=20;CoefficientList[Series[1/(1-3x)-1/(x^2+(1-3x)),{x,0,nn}],x] (* Geoffrey Critzer, Dec 25 2013 *)
LinearRecurrence[{6,-10,3},{0,0,1},30] (* Harvey P. Dale, Jun 14 2020 *)

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

G.f.: x^2/((1-3*x)*(1-3*x+x^2)). a(n) = 3^n - A001906(n+1). - Bruno Berselli, Feb 23 2011

A186244 Number of ternary strings of length n containing 00.

Original entry on oeis.org

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

cp's OEIS Frontend

User: Toby Gottfried

A231430 Number of ternary sequences which contain 000.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A216211 Number of self-avoiding walks of any length from NW to SW corners of a grid or lattice with n rows and 4 columns.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A214931 Number of self-avoiding walks of any length from NW to SW corners of a grid or lattice with 4 rows and n columns.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

Extensions

A186314 Number of ternary strings of length n which contain 01.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A186244 Number of ternary strings of length n containing 00.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula