A133129 -id:A133129 - cp's OEIS frontend

A181245 T(n,k) = Number of n X k binary matrices with no 2 X 2 circuit having pattern 0101 in any orientation.

2, 4, 4, 8, 14, 8, 16, 50, 50, 16, 32, 178, 322, 178, 32, 64, 634, 2066, 2066, 634, 64, 128, 2258, 13262, 23858, 13262, 2258, 128, 256, 8042, 85126, 275690, 275690, 85126, 8042, 256, 512, 28642, 546410, 3185462, 5735478, 3185462, 546410, 28642, 512, 1024

Offset: 1

R. H. Hardin, Oct 10 2010

Table starts
....2......4.........8..........16.............32...............64
....4.....14........50.........178............634.............2258
....8.....50.......322........2066..........13262............85126
...16....178......2066.......23858.........275690..........3185462
...32....634.....13262......275690........5735478........119310334
...64...2258.....85126.....3185462......119310334.......4468252414
..128...8042....546410....36806846.....2481942354.....167341334542
..256..28642...3507314...425288998....51630303190....6267120468434
..512.102010..22512862..4914052362..1074033301458..234710735573170
.1024.363314.144506294.56780001474.22342450688162.8790181730741270

			All solutions for 2X2
..0..0....0..0....0..0....0..0....0..1....0..1....0..1....1..0....1..0....1..0
..0..0....0..1....1..0....1..1....0..0....0..1....1..1....0..0....1..0....1..1
...
..1..1....1..1....1..1....1..1
..0..0....0..1....1..0....1..1

R. H. Hardin, Table of n, a(n) for n=1..480

Main diagonal is A133130.
Column 2 is A055099.
Column 3 is A133129.

Empirical column 1: a(n)=2*a(n-1)
Empirical column 2: a(n)=3*a(n-1)+2*a(n-2)
Empirical column 3: a(n)=6*a(n-1)+3*a(n-2)-2*a(n-3)
Empirical column 4: a(n)=10*a(n-1)+20*a(n-2)-21*a(n-3)-30*a(n-4)+8*a(n-5)
Empirical column 5: a(n)=21*a(n-1)+9*a(n-2)-278*a(n-3)+73*a(n-4)+790*a(n-5)-662*a(n-6)+29*a(n-7)+69*a(n-8)-10*a(n-9)
Empirical column 6: a(n)=36*a(n-1)+120*a(n-2)-2391*a(n-3)-3905*a(n-4)+50702*a(n-5)+27152*a(n-6)-396016*a(n-7)+154999*a(n-8)+751787*a(n-9)-499260*a(n-10)-410368*a(n-11)+355981*a(n-12)+38077*a(n-13)-70276*a(n-14)+6203*a(n-15)+3386*a(n-16)-622*a(n-17)+28*a(n-18)
Empirical column 7: a(n)=77*a(n-1)-429*a(n-2)-16791*a(n-3)+132938*a(n-4)+1140609*a(n-5)-11250708*a(n-6)-21101443*a(n-7)+356560316*a(n-8)-276630106*a(n-9)-3595865197*a(n-10)+5253257444*a(n-11)+16399879057*a(n-12)-30419637636*a(n-13)-37486637674*a(n-14)+87632998667*a(n-15)+40083109062*a(n-16)-140235056122*a(n-17)-7589163210*a(n-18)+128111780723*a(n-19)-23221600421*a(n-20)-65939015129*a(n-21)+21868944788*a(n-22)+18307048178*a(n-23)-8259596531*a(n-24)-2431120428*a(n-25)+1497147381*a(n-26)+85285300*a(n-27)-123174410*a(n-28)+8581030*a(n-29)+3300116*a(n-30)-512304*a(n-31)+18304*a(n-32)

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

cp's OEIS Frontend

A181245 T(n,k) = Number of n X k binary matrices with no 2 X 2 circuit having pattern 0101 in any orientation.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

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