A255256 -id:A255256 - cp's OEIS frontend

A055099 Expansion of g.f.: (1 + x)/(1 - 3x - 2x^2).

1, 4, 14, 50, 178, 634, 2258, 8042, 28642, 102010, 363314, 1293962, 4608514, 16413466, 58457426, 208199210, 741512482, 2640935866, 9405832562, 33499369418, 119309773378, 424928058970, 1513403723666, 5390067288938, 19197009314146, 68371162520314, 243507506189234

Offset: 0

Wolfdieter Lang, Apr 26 2000

Row sums of triangle A054458.
a(n) = term (1,1) in M^n, M = the 3 X 3 matrix [1,1,1; 1,1,1; 2,2,1]. - Gary W. Adamson, Mar 12 2009
Equals the INVERT transform of A001333: (1, 3, 7, 17, 41, 99, ...). - Gary W. Adamson, Aug 14 2010
a(n) is the number of one sided n-step walks taking steps from {(0,1), (-1,0), (1,0), (1,1)}. - Shanzhen Gao, May 13 2011
Number of quaternary words of length n on {0,1,2,3} containing no subwords 03 or 30. - Philippe Deléham, Apr 27 2012
Pisano period lengths: 1, 1, 4, 1, 24, 4, 48, 1, 12, 24, 30, 4, 12, 48, 24, 2, 272, 12, 18, 24, ... - R. J. Mathar, Aug 10 2012
a(n) = A007481(2*n+1) - A007481(2*n) = A007481(2*(n+1)) - A007481(2*n+1). - Reinhard Zumkeller, Oct 25 2015
Number of length-n words on a,b,c,d avoiding aa and ab. For n >= 1, the number of such words ending with a or the number of those ending with b is A007482(n-1), and the number of those ending with c or the number of those ending with d is a(n-1). - Jianing Song, Jun 01 2022

			a(3) = 50 because among the 4^3 = 64 quaternary words of length 3 only 14 namely 003, 030, 031, 032, 033, 103, 130, 203, 230, 300, 301, 302, 303, 330 contain the subwords 03 or 30. - _Philippe Deléham_, Apr 27 2012

I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, Wiley, N.Y., 1983, (Problem 2.4.6).

Alois P. Heinz, Table of n, a(n) for n = 0..1000
M. Abrate, S. Barbero, U. Cerruti, and N. Murru, Construction and composition of rooted trees via descent functions, Algebra, Volume 2013 (2013), Article ID 543913, 11 pages.
D. Birmajer, J. B. Gil, and M. D. Weiner, On the Enumeration of Restricted Words over a Finite Alphabet, J. Int. Seq. 19 (2016) # 16.1.3 , example 17
A. S. Fraenkel, Heap games, numeration systems and sequences, arXiv:math/9809074 [math.CO], 1998; Annals of Combinatorics, 2 (1998), 197-210.
Shanzhen Gao and Keh-Hsun Chen, Tackling Sequences From Prudent Self-Avoiding Walks, FCS'14, The 2014 International Conference on Foundations of Computer Science.
S. Gao and H. Niederhausen, Sequences Arising From Prudent Self-Avoiding Walks, 2010.
Sergey Kitaev and Jeffrey Remmel, (a,b)-rectangle patterns in permutations and words, arXiv:1304.4286 [math.CO], 2013.
Paul K. Stockmeyer, The Pascal Rhombus and the Stealth Configuration, arXiv:1504.04404 [math.CO], 2015.
Index entries for linear recurrences with constant coefficients, signature (3,2).

Column k=2 of A255256.

Cf. A001333, A002203, A007481, A007482, A054458, A104934, A202396.

a055099 n = a007481 (2 * n + 1) - a007481 (2 * n)
-- Reinhard Zumkeller, Oct 25 2015

I:=[1,4]; [n le 2 select I[n] else 3*Self(n-1) + 2*Self(n-2): n in [1..41]]; // G. C. Greubel, Jun 27 2021

a := proc(n) option remember; `if`(n < 2, [1, 4][n+1], (3*a(n-1) + 2*a(n-2))) end:
seq(a(n), n=0..23); # Peter Luschny, Jan 06 2019

max = 24; cv = ContinuedFraction[ Sqrt[2], max] // Convergents // Numerator; Series[ 1/(1 - cv.x^Range[max]), {x, 0, max}] // CoefficientList[#, x]& // Rest (* Jean-François Alcover, Jun 21 2013, after Gary W. Adamson *)
LinearRecurrence[{3, 2}, {1, 4}, 24] (* Jean-François Alcover, Sep 23 2017 *)

[(i*sqrt(2))^(n-1)*( i*sqrt(2)*chebyshev_U(n, -3*i/(2*sqrt(2))) + chebyshev_U(n-1, -3*i/(2*sqrt(2))) ) for n in (0..40)] # G. C. Greubel, Jun 27 2021

a(n) = a*c^n - b*d^n, a := (5 + sqrt(17))/(2*sqrt(17)), b := (5 - sqrt(17))/(2*sqrt(17)), c := (3 + sqrt(17))/2, d := (3 - sqrt(17))/2.
a(n) = Sum_{m=0..n} A054458(n, m).
a(n) = F32(n) + F32(n-1) with F32(n) = A007482(n), n >= 1, a(0) = 1.
a(n) = A007482(n) + A007482(n-1) = 2*A007482(n) - A104934(n). - R. J. Mathar, Jul 23 2010
a(n) = 3*a(n-1) + 2*a(n-2) with a(0) = 1, a(1) = 4. - Vincenzo Librandi, Dec 08 2010
a(n) = (Sum_{k = 0..n} A202396(n,k)*3^k)/2^n. - Philippe Deléham, Feb 05 2012
a(n) = (i*sqrt(2))^(n-1)*( i*sqrt(2)*ChebyshevU(n, -3*i/(2*sqrt(2))) + ChebyshevU(n-1, -3*i/(2*sqrt(2))) ). - G. C. Greubel, Jun 27 2021
a(n) = 2*a(n-1) + 2*A007482(n-1), n >= 1. - Jianing Song, Jun 01 2022
E.g.f.: exp(3*x/2)*(17*cosh(sqrt(17)*x/2) + 5*sqrt(17)*sinh(sqrt(17)*x/2))/17. - Stefano Spezia, May 24 2024

Edited by N. J. A. Sloane, Jun 08 2010

A133357 Number of 2-colorings of a 3 X n rectangle for which no subsquare has monochromatic corners.

Original entry on oeis.org

1, 8, 50, 276, 1498, 8352, 46730, 260204, 1447890, 8062968, 44907298, 250082756, 1392637914, 7755351712, 43188407610, 240509081468, 1339353796226, 7458635202952, 41535888495186, 231306378487028, 1288106280145770, 7173247100732400, 39946606186601514

Offset: 0

Victor S. Miller, Dec 21 2007

Figures obtained via clever exhaustion, using Gray Codes.

			a(1) = 8, because there are no conditions.
a(2) = 50 because if the middle row is not monochromatic, the top and bottom rows are unconstrained, contributing 2*4*4.  If the middle row is monochromatic, the top and bottom rows can each take on only 3 values contributing 2*3*3.

J. Solymosi, "A Note on a Question of Erdos and Graham", Combinatorics, Probability and Computing, Volume 13, Issue 2 (March 2004) 263 - 267.

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Sci.math, Discussion of a related problems

Cf. A133129, A255255.

Column k=3 of A255256.

gf:= -(x+1)*(8*x^7-12*x^6-2*x^5-16*x^4-30*x^3-15*x^2-4*x-1)/
     (24*x^8-4*x^7-46*x^6-66*x^5-74*x^4-25*x^3-7*x^2-3*x+1):
a:= n-> coeff(series(gf, x, n+1), x, n):
seq(a(n), n=0..30);  # Alois P. Heinz, Feb 18 2015

G.f.: -(x+1)*(8*x^7-12*x^6-2*x^5-16*x^4-30*x^3-15*x^2-4*x-1) / (24*x^8-4*x^7-46*x^6-66*x^5-74*x^4-25*x^3-7*x^2-3*x+1). - Alois P. Heinz, Feb 18 2015

a(0), a(8)-a(22) from Alois P. Heinz, Feb 18 2015

A255255 Number of 2-colorings of a 4 X n rectangle such that no nontrivial subsquare has monochromatic corners.

Original entry on oeis.org

1, 16, 178, 1498, 10980, 85138, 655090, 5115398, 39914386, 312388874, 2436283602, 18994966598, 148059349634, 1154792660474, 9007078544234, 70254124462638, 547921292697778, 4273303250042966, 33327954035543034, 259932116476519958, 2027268764564330754

Offset: 0

Alois P. Heinz, Feb 19 2015

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Column k=4 of A255256.

Cf. A133357.

gf:= -(4608*x^78 +3840*x^77 +84224*x^76 -320640*x^75 +246976*x^74 -756544*x^73 -2238400*x^72 +5321120*x^71 +12808672*x^70 +54862128*x^69 -56935120*x^68 -320396192*x^67 +196696056*x^66 +580449400*x^65 -800166640*x^64 +931676252*x^63 -3217094764*x^62 -2931282696*x^61 +15075340414*x^60 -25189807228*x^59 +8940907182*x^58 +72225838335*x^57 -79785446783*x^56 +16049408070*x^55 +94923048557*x^54 -184157650742*x^53 +84396466384*x^52 +63222211250*x^51 -205358037404*x^50
+102077559913*x^49 -54179691207*x^48 -58933050614*x^47 -72350094400*x^46 +119755954460*x^45 +391109674279*x^44 -31136120454*x^43 +7469466171*x^42 +4087734421*x^41 -259850982087*x^40 -250072129598*x^39 -106581496436*x^38 +208831935210*x^37 +402861489180*x^36 +109203162981*x^35 -275403863093*x^34 -334505242945*x^33 -114680900580*x^32 +196805363764*x^31 +294322652328*x^30 +163414286266*x^29
+9671161820*x^28 -93783726011*x^27 -117305441726*x^26 -63470276869*x^25 -4776176481*x^24 +17768047304*x^23 +14651146288*x^22 +7623498972*x^21 +4260618627*x^20 +1317986665*x^19 -720102442*x^18 -787824686*x^17 -195158015*x^16 +30687326*x^15 +15478943*x^14 +9512482*x^13 +14257207*x^12 +7365310*x^11 -194075*x^10 -1591059*x^9 -609139*x^8 -99289*x^7 +358*x^6 +4060*x^5 +1728*x^4 +632*x^3 +117*x^2 +14*x +1) /
(-2304*x^76 -4224*x^75 -48832*x^74 +106368*x^73 -28736*x^72 +387264*x^71 +1606752*x^70 -417728*x^69 -6732224*x^68 -32605960*x^67 -17678016*x^66 +104280356*x^65 +13666240*x^64 -287868964*x^63 +243731588*x^62 -345759930*x^61 +338343404*x^60 +2718472224*x^59 -4711903718*x^58 +5420902529*x^57 +8555023111*x^56 -23454331276*x^55 +9026831269*x^54
+16445485090*x^53 -42633850200*x^52 +27124456832*x^51 +15867136764*x^50 -59350410523*x^49 +30378083319*x^48 +11917445228*x^47 -36411691280*x^46 +24780724314*x^45 +72006964843*x^44 +20800791816*x^43 -64959622007*x^42 -16674723587*x^41 +8311317841*x^40 -41851983658*x^39 -10878840512*x^38 +60227329766*x^37 +71646302640*x^36 +111795917*x^35 -98969183331*x^34 -102248503015*x^33 +13126172584*x^32 +108338140330*x^31
+80553248220*x^30 -4243013616*x^29 -43486302952*x^28 -28181948095*x^27 -3688188878*x^26 +4299265271*x^25 +2263896509*x^24 +739802084*x^23 +845394966*x^22 +509931484*x^21 -127596363*x^20 -330548479*x^19 -74104054*x^18 +132481026*x^17 +79485565*x^16 +21861608*x^15 +12380793*x^14 +5359440*x^13 +161495*x^12 -1832730*x^11 -1066905*x^10 -274895*x^9 -73293*x^8 -3043*x^7 +5244*x^6 +1760*x^5 +358*x^4 +46*x^3 +29*x^2 +2*x -1):
a:= n-> coeff(series(gf, x, n+1), x, n):
seq(a(n), n=0..30);

G.f.: see Maple program.

cp's OEIS Frontend

A055099 Expansion of g.f.: (1 + x)/(1 - 3*x - 2*x^2).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

Sage

Formula

Extensions

A133357 Number of 2-colorings of a 3 X n rectangle for which no subsquare has monochromatic corners.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Formula

Extensions

A255255 Number of 2-colorings of a 4 X n rectangle such that no nontrivial subsquare has monochromatic corners.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Formula

A018803 Number of ways to color cells of an n X n square with 2 colors so that no subsquare of side > 1 has all corners same color.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A255262 Number of 2-colorings of a 5 X n rectangle such that no nontrivial subsquare has monochromatic corners.

Views

Author

Keywords

Crossrefs

A055099 Expansion of g.f.: (1 + x)/(1 - 3x - 2x^2).