A265624 -id:A265624 - cp's OEIS frontend

A135491 Number of ways to toss a coin n times and not get a run of four.

1, 2, 4, 8, 14, 26, 48, 88, 162, 298, 548, 1008, 1854, 3410, 6272, 11536, 21218, 39026, 71780, 132024, 242830, 446634, 821488, 1510952, 2779074, 5111514, 9401540, 17292128, 31805182, 58498850, 107596160, 197900192, 363995202, 669491554, 1231386948, 2264873704

Offset: 0

James R FitzSimons (cherry(AT)getnet.net), Feb 07 2008

G. C. Greubel, Table of n, a(n) for n = 0..1000
Elena Barcucci, Antonio Bernini, Stefano Bilotta, Renzo Pinzani, Non-overlapping matrices, arXiv:1601.07723 [cs.DM], 2016. See column 2 of Table 2 p. 11.
Elena Barcucci, Antonio Bernini, Stefano Bilotta and Renzo Pinzani, Non-overlapping matrices, Theoretical Computer Science, Vol. 658, Part A (2017), 36-45.
B. Chaffin, J. P. Linderman, N. J. A. Sloane and Allan Wilks, On Curling Numbers of Integer Sequences, arXiv:1212.6102 [math.CO], 2012-2013.
B. Chaffin, J. P. Linderman, N. J. A. Sloane and Allan Wilks, On Curling Numbers of Integer Sequences, Journal of Integer Sequences, Vol. 16 (2013), Article 13.4.3.
Emrah Kılıç, Talha Arıkan, Evaluation of Hessenberg determinants with recursive entries: generating function approach, Filomat (2017) Vol. 31, Issue 15, pp. 4945-4962.
A. V. Zharkova, Inaccesible States in Dynamic Systems Associated with Paths and Cycles, Izv. Saratov Univ. (N.S.), Ser. Math. Mech. Inform., 11 (2011), 116-122.
Index entries for linear recurrences with constant coefficients, signature (1, 1, 1).

Cf. A000073. Column 2 of A265624. Cf. A135492, A135493, A000213, A058265.

LinearRecurrence[{1, 1, 1}, {1, 2, 4, 8}, 36] (* Vladimir Joseph Stephan Orlovsky, Jul 23 2011; first term 1 added by Georg Fischer, Apr 02 2019 *)

Vec(1-2*x*(1+x+x^2)/(-1+x+x^2+x^3) + O(x^100)) \\ Altug Alkan, Dec 10 2015

a(n) = 2*A000073(n+2) for n > 0.
a(n) = a(n-1) + a(n-2) + a(n-3) for n > 3.
G.f.: -(x+1)*(x^2+1)/(x^3+x^2+x-1).
a(n) = nearest integer to b*c^n, where b = 1.2368... and c = 1.839286755... is the real root of x^3-x^2-x-1 = 0. See A058265. - N. J. A. Sloane, Jan 06 2010
G.f.: (1-x^4)/(1-2*x+x^4) and generally to "not get a run of k" (1-x^k)/(1-2*x+x^k). - Geoffrey Critzer, Feb 01 2012
G.f.: Q(0)/x^2 - 2/x- 1/x^2, where Q(k) = 1 + (1+x)*x^2 + (2*k+3)*x - x*(2*k+1 +x+x^2)/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, Oct 04 2013
a(n) = A000213(n+3) - A000213(n+2), n>=1. - Peter M. Chema, Jan 11 2017.

More terms from Robert G. Wilson v, Feb 10 2008

a(0)=1 prepended by Alois P. Heinz, Dec 10 2015

A265584 Array T(n,k) counting words with n letters drawn from a k-letter alphabet with no letter appearing thrice in a 3-letter subword.

Original entry on oeis.org

1, 1, 2, 0, 4, 3, 0, 6, 9, 4, 0, 10, 24, 16, 5, 0, 16, 66, 60, 25, 6, 0, 26, 180, 228, 120, 36, 7, 0, 42, 492, 864, 580, 210, 49, 8, 0, 68, 1344, 3276, 2800, 1230, 336, 64, 9, 0, 110, 3672, 12420, 13520, 7200, 2310, 504, 81, 10, 0, 178, 10032, 47088, 65280, 42150, 15876, 3976, 720, 100, 11

Offset: 1

R. J. Mathar, Dec 10 2015

The antidiagonal sums are s(d) = 1, 3, 7, 19, 55, 173, 597, 2245, 9127, 39827, 185411, 916177, 4784217,.. at index d=n+k >=2.

			1      2      3      4      5       6       7        8
1      4      9     16     25      36      49       64
0      6     24     60    120     210     336      504
0     10     66    228    580    1230    2310     3976
0     16    180    864   2800    7200   15876    31360
0     26    492   3276  13520   42150  109116   247352
0     42   1344  12420  65280  246750  749952  1950984
0     68   3672  47088 315200 1444500 5154408 15388352
T(3,2) =6 counts the 3-letter words aab, aba, abb, bba, bab, baa. The words aaa and bbb are not counted.

Cf. A265583 (no letter twice), A265624. A000290 (row 2), A007531 (row 3), A006355 (column 2), A121907 (column 3), A123620 (column 4), A123871 (column 5), A123887 (column 6).

A265584 := proc(n,k)
    (1+x+x^2)/(1-(k-1)*x-(k-1)*x^2) ;
    coeftayl(%,x=0,n) ;
end proc:
seq(seq( A265584(d-k,k),k=1..d-1),d=2..13) ;

T[n_, k_] := SeriesCoefficient[(1+x+x^2)/(1-(k-1)*x-(k-1)*x^2), {x, 0, n}];
Table[T[n-k, k], {n, 2, 12}, {k, 1, n-1}] // Flatten (* Jean-François Alcover, Mar 26 2020, from Maple *)

T(4,k) = k*(k-1)*(k^2+k-1).
T(5,k) = k^2*(k+2)*(k-1)^2.
T(6,k) = k*(k^3+2*k^2-k-1)*(k-1)^2.
T(7,k) = k*(k+1)*(k^2+2*k-1)*(k-1)^3.

A181137 The number of ways to color n balls in a row with 3 colors with no color runs having lengths greater than 3.

Original entry on oeis.org

1, 3, 9, 27, 78, 228, 666, 1944, 5676, 16572, 48384, 141264, 412440, 1204176, 3515760, 10264752, 29969376, 87499776, 255467808, 745873920, 2177683008, 6358049472, 18563212800, 54197890560, 158238305664, 461998818048, 1348870028544, 3938214304512

Offset: 0

William Sit (wyscc(AT)sci.ccny.cuny.edu), Oct 06 2010

This sequence is a special case of the general problem for coloring n balls in a row with p colors where each color has a given maximum run-length. In this example, the bounds are uniformly 3. It can be phrased in terms of tossing a p-faced die n times, requiring each face to have no runs longer than b.

Generating function and recurrence for given p and uniform bound b are known. a(n+b) = (p-1)(a(n)+ ... + a(n+b-1)), using b initial values a(1)=p, a(2)=p^2, ..., a(b)=p^(b) The g.f. is p*G/(1-(p-1)*G) where G = t + t^2 + ... + t^b.

			For p=3 and b=3, a(4)=78. The colorings are: 1112, 1113, 1121, 1122, 1123, 1131, 1132, 1133, 1211, 1212, 1213, 1221, 1222, 1223, 1231, 1232, 1233, 1311, 1312, 1313, 1321, 1322, 1323, 1331, 1332, 1333, 2111, 2112, 2113, 2121, 2122, 2123, 2131, 2132, 2133, 2211, 2212, 2213, 2221, 2223, 2231, 2232, 2233, 2311, 2312, 2313, 2321, 2322, 2323, 2331, 2332, 2333, 3111, 3112, 3113, 3121, 3122, 3123, 3131, 3132, 3133, 3211, 3212, 3213, 3221, 3222, 3223, 3231, 3232, 3233, 3311, 3312, 3313, 3321, 3322, 3323, 3331, 3332.

Colin Barker, Table of n, a(n) for n = 0..1000
Li Guo and William Sit, Enumeration and Generating Functions for Differential Rota-Baxter Words, Math. Comput. Sci. 4 (2010), 339-358.
Index entries for linear recurrences with constant coefficients, signature (2,2,2).

A135492 is sequence[2, {2, 4, 6, 8}, n-4], for colorings of n balls in a row with p=2 colors so no color has run length more than 4. A135491 coloring of 2 balls in a row with p=2 colors so no color has run length more than 3. In general 2 colorings are like coin tossing. The example here is 3 colorings (tossing 3-sided dice).

Column 3 in A265624.

(* next[p,z] computes the next member in a sequence and
next[p,z] = a(n+b)= (p-1)( c(b)+ ... + c(n+b-1)) where z is the preceding b items on the sequence starting with a(n) where b is the uniform bound on runs.
The function sequence[p,z,n] computes the next n terms. *) next[p_,z_]:=(p-1) Apply[Plus,z] sequence[p_,z_,n_]:=Module[{y=z,seq=z, m=n, b=Length[z]}, While[m>0, seq = Join[seq,{next[p,y]}]; y = Take[seq, -b]; m-- ]; seq] (* sequence[3,{3,9,27},10] computes the next 10 terms after 3,9,27. *)
LinearRecurrence[{2,2,2},{1,3,9,27},30] (* Harvey P. Dale, Dec 01 2017 *)

Vec((1 + x)*(1 + x^2) / (1 - 2*x - 2*x^2 - 2*x^3) + O(x^30)) \\ Colin Barker, Jun 28 2019

G.f.: 1+3t(t^2+t+1)/(1 - 2t(t^2+t+1)).
a(n+3) = 2(a(n)+a(n+1)+a(n+2)), a(0)=1, a(1)=3, a(2)=9, a(3)=27.
a(n) = 3*A119826(n-1). - R. J. Mathar, Dec 10 2015
G.f.: (1 + x)*(1 + x^2) / (1 - 2*x - 2*x^2 - 2*x^3). - Colin Barker, Jun 28 2019

a(0)=1 prepended by Alois P. Heinz, Dec 10 2015

A188714 G.f.: (1+x+x^2+x^3)/(1-3x-3x^2-3*x^3).

Original entry on oeis.org

1, 4, 16, 64, 252, 996, 3936, 15552, 61452, 242820, 959472, 3791232, 14980572, 59193828, 233896896, 924213888, 3651913836, 14430073860, 57018604752, 225301777344, 890251367868, 3517715249892, 13899805185312, 54923315409216, 217022507533260, 857536884383364, 3388448121977520, 13389022541682432, 52905022644129948, 209047479923369700

Offset: 0

N. J. A. Sloane, Apr 08 2011

nonn

G.f. for number of ways to spin a dreidel n times without having a run of length 4 of any of gimel, heh, nun or shin.
More generally, fix an alphabet of size M and consider the number of words of length n which do not contain M consecutive equal letters. The present sequence is the case M = 4.
For the cases M=2 through 5 see A040000, A121907, A188714, A188680.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
J. Noonan and D. Zeilberger, The Goulden-Jackson cluster method: extensions, applications and implementations
Doron Zeilberger, Webpage of the paper `The Goulden-Jacskon Cluster Method: Extensions, Applications and Implementations', by John Noonan and Doron Zeilberger; Local copy, pdf file only, no active links
Index entries for linear recurrences with constant coefficients, signature (3, 3, 3).

Cf. A040000, A121907, A188680. Column 4 of A265624.

# First download the Maple package DAVID_IAN from the Zeilberger web site
read(DAVID_IAN);
M:=4;
lis1:={}; for i from 1 to M do lis1:={op(lis1),x[i]}; od:
lis2:={}; for i from 1 to M do t1:=[]; for j from 1 to M do t1:=[op(t1),x[i]]; od: lis2:={op(lis2),t1}; od:
GJs(lis1, lis2, x);

CoefficientList[Series[(1+x+x^2+x^3)/(1-3x-3x^2-3x^3),{x,0,30}], x]  (* Harvey P. Dale, Apr 16 2011 *)

cp's OEIS Frontend

A135491 Number of ways to toss a coin n times and not get a run of four.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A265584 Array T(n,k) counting words with n letters drawn from a k-letter alphabet with no letter appearing thrice in a 3-letter subword.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Mathematica

Formula

A181137 The number of ways to color n balls in a row with 3 colors with no color runs having lengths greater than 3.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A188714 G.f.: (1+x+x^2+x^3)/(1-3*x-3*x^2-3*x^3).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

A188714 G.f.: (1+x+x^2+x^3)/(1-3x-3x^2-3*x^3).