A135491 -id:A135491 - cp's OEIS frontend

A203536 Number of nX2 0..2 arrays with every element neighboring horizontally or vertically both a 0 and a 1.

0, 4, 4, 16, 64, 196, 676, 2304, 7744, 26244, 88804, 300304, 1016064, 3437316, 11628100, 39337984, 133079296, 450203524, 1523028676, 5152368400, 17430336576, 58966408900, 199481929956, 674842534144, 2282975946304, 7723252297476

Offset: 1

R. H. Hardin Jan 02 2012

nonn

Column 2 of A203542

(A135491(n-2))^2 for n>=3

			Some solutions for n=5
..0..1....1..1....0..0....1..0....0..0....0..1....0..0....0..1....1..0....1..1
..0..1....0..0....1..1....1..0....1..1....0..1....1..1....0..1....1..0....0..0
..2..1....1..2....1..2....0..2....2..0....1..2....2..2....0..1....0..0....2..1
..0..0....1..0....0..0....0..1....1..0....1..0....0..0....0..0....0..1....0..1
..1..1....1..0....1..1....0..1....1..0....1..0....1..1....1..1....0..1....0..1

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

Empirical: a(n) = 2*a(n-1) +3*a(n-2) +6*a(n-3) -a(n-4) -a(n-6)

A170877 Number of binary words of length n with properties that there is no pair of adjacent 1's and no subword of the form X^4 for any string X.

Original entry on oeis.org

1, 2, 3, 5, 7, 10, 15, 22, 30, 43, 61, 88, 123, 173, 246, 348, 487, 688, 972, 1371, 1928, 2714, 3822, 5387, 7582, 10681, 15046, 21194, 29835, 42009, 59159, 83305, 117292, 165170, 232593, 327530, 461198, 649431, 914493, 1287747, 1813281, 2553346, 3595465

Offset: 0

Benjamin Chaffin and N. J. A. Sloane, Jan 07 2010

nonn

The subword 01010101 (corresponding to X = 01) for example cannot occur.

			a(3) = 5: 000, 001, 010, 100, 101.
a(4) = 7: 0001, 0010, 0100, 1000, 0101, 1010, 1001.

Lars Blomberg, Table of n, a(n) for n = 0..43

Cf. A003410, A028445, A135491.

a(24)-a(42) from Lars Blomberg, Aug 22 2013

A232275 T(n,k)=Number of nXk 0..3 arrays with every 0 next to a 1, every 1 next to a 2 and every 2 next to a 3 horizontally, vertically, diagonally or antidiagonally, and no adjacent values equal.

Original entry on oeis.org

1, 2, 2, 4, 24, 4, 8, 48, 48, 8, 14, 96, 72, 96, 14, 26, 192, 120, 120, 192, 26, 48, 384, 216, 168, 216, 384, 48, 88, 768, 408, 264, 264, 408, 768, 88, 162, 1536, 792, 456, 360, 456, 792, 1536, 162, 298, 3072, 1560, 840, 552, 552, 840, 1560, 3072, 298, 548, 6144, 3096

Offset: 1

R. H. Hardin, Nov 22 2013

Table starts
...1....2....4....8...14...26...48...88..162...298...548..1008..1854...3410
...2...24...48...96..192..384..768.1536.3072..6144.12288.24576.49152..98304
...4...48...72..120..216..408..792.1560.3096..6168.12312.24600.49176..98328
...8...96..120..168..264..456..840.1608.3144..6216.12360.24648.49224..98376
..14..192..216..264..360..552..936.1704.3240..6312.12456.24744.49320..98472
..26..384..408..456..552..744.1128.1896.3432..6504.12648.24936.49512..98664
..48..768..792..840..936.1128.1512.2280.3816..6888.13032.25320.49896..99048
..88.1536.1560.1608.1704.1896.2280.3048.4584..7656.13800.26088.50664..99816
.162.3072.3096.3144.3240.3432.3816.4584.6120..9192.15336.27624.52200.101352
.298.6144.6168.6216.6312.6504.6888.7656.9192.12264.18408.30696.55272.104424

			Some solutions for n=7 k=4
..3..0..3..0....0..1..0..1....1..0..1..0....3..2..3..2....0..2..0..2
..1..2..1..2....3..2..3..2....3..2..3..2....0..1..0..1....3..1..3..1
..0..3..0..3....1..0..1..0....1..0..1..0....3..2..3..2....0..2..0..2
..1..2..1..2....3..2..3..2....2..3..2..3....1..0..1..0....3..1..3..1
..3..0..3..0....0..1..0..1....1..0..1..0....3..2..3..2....2..0..2..0
..2..1..2..1....2..3..2..3....2..3..2..3....1..0..1..0....3..1..3..1
..0..3..0..3....1..0..1..0....1..0..1..0....2..3..2..3....0..2..0..2

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

Column 1 is A135491(n-1)
Column 2 is A003945(n+2)
Diagonal is 12*A000918 for n>1

Empirical for column k:
k=1: a(n) = a(n-1) +a(n-2) +a(n-3) for n>4
k=2: a(n) = 2*a(n-1) for n>2
k=3: a(n) = 3*a(n-1) -2*a(n-2) for n>3
k=4: a(n) = 3*a(n-1) -2*a(n-2) for n>3
k=5: a(n) = 3*a(n-1) -2*a(n-2) for n>3
k=6: a(n) = 3*a(n-1) -2*a(n-2) for n>3
k=7: a(n) = 3*a(n-1) -2*a(n-2) for n>3
Apparently T(n,k)=12*(2^(n-1)+2^(k-1)-2) for n>1 and k>1

A354784 First differences of A000213, also twice A000073.

Original entry on oeis.org

0, 0, 2, 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

Offset: 0

N. J. A. Sloane, Jul 12 2022

Number of anti-palindromic compositions of n+1 of even length.

Paolo Xausa, Table of n, a(n) for n = 0..1000
George E. Andrews, Matthew Just, and Greg Simay, Anti-palindromic compositions, arXiv:2102.01613 [math.CO], 2021. Also Fib. Q., 60:2 (2022), 164-176. See Table 1.
Index entries for linear recurrences with constant coefficients, signature (1,1,1).

Cf. A000213, A000073, A135491 (essentially the same sequence).

LinearRecurrence[{1, 1, 1}, {0, 0, 2}, 50] (* Paolo Xausa, May 27 2024 *)

From Chai Wah Wu, Jul 12 2022: (Start)
a(n) = a(n-1) + a(n-2) + a(n-3) for n > 2.
G.f.: -2*x^2/(x^3 + x^2 + x - 1). (End)

A273154 Number of 4-power-free binary words of length n.

Original entry on oeis.org

1, 2, 4, 8, 14, 26, 48, 88, 160, 292, 532, 972, 1768, 3220, 5866, 10686, 19454, 35430, 64528, 117520, 214004, 389724, 709730, 1292496, 2353758, 4286442, 7806048, 14215620, 25888034, 47144704, 85855230, 156350996, 284730756, 518523184, 944282620

Offset: 0

Vladimir Reshetnikov, May 16 2016

A 4-power-free binary word is a word over the alphabet {0, 1} that cannot be represented as a concatenation XYYYYZ, where Y is a nonempty word, but X and Z may be empty.

A028445(n) <= a(n) <= A135491(n).

Cf. A028445, A135491.

Length/@NestList[DeleteCases[Flatten[Outer[Append, #, {0, 1}, 1], 1], {_, x__, x__, x__, x__, _}] &, {{}}, 16]

from itertools import product
def qf(s):
    for l in range(1, len(s)//4 + 1):
      for i in range(len(s) - 4*l + 1):
          if s[i:i+l] == s[i+l:i+2*l] == s[i+2*l:i+3*l] == s[i+3*l:i+4*l]:
              return False
    return True
def a(n):
    if n == 0: return 1
    return 2*sum(1 for w in product("01", repeat=n-1) if qf("0"+"".join(w)))
print([a(n) for n in range(21)]) # Michael S. Branicky, Mar 14 2022

# faster, but > memory, version for initial segment of sequence
def iqf(s): # incrementally 4th-power free
    for l in range(1, len(s)//4 + 1):
        if s[-4*l:-3*l] == s[-3*l:-2*l] == s[-2*l:-l] == s[-l:]:
            return False
    return True
def aupton(nn, verbose=False):
    alst, qfs = [1], set("0")
    for n in range(1, nn+1):
        an = 2*len(qfs)
        qfsnew = set(q+i for q in qfs for i in "01" if iqf(q+i))
        alst, qfs = alst+[an], qfsnew
        if verbose: print(n, an)
    return alst
print(aupton(20)) # Michael S. Branicky, Mar 14 2022

a(17)-a(30) from Lars Blomberg, Nov 11 2017

a(31)-a(34) from Michael S. Branicky, Mar 14 2022

A277828 Least number of tosses of a fair coin needed to have an even chance or better of getting a run of at least m consecutive heads or consecutive tails.

Original entry on oeis.org

1, 2, 5, 11, 23, 45, 90, 179, 357, 712, 1422, 2842, 5681, 11360, 22716, 45430, 90856, 181709, 363413, 726822, 1453640, 2907276, 5814546, 11629086, 23258166, 46516327, 93032647

Offset: 1

Tim Miles, Nov 01 2016

There are a family of sequences that represent the number of sequences of tosses of a fair coin to n tosses where there are no runs of m or more consecutive heads or consecutive tails. Some are given in this Encyclopedia. Their general form is given as part of the formula below. As n increases, the proportion of sequences of tosses that meet this condition decreases. When that proportion becomes a half or less of the total number of sequences of tosses, there is an even or better chance that a run of m consecutive heads or m consecutive tails occurs.
There is actually a family of sequences of which the above sequence is an instance: those in which, for successive values of m, r*g(n) <= 2^n for r > 1.
a(n) - ceiling((log 2)*2^n + (1-log 2)*n + (log 2)/2-2) equals 0 or (almost never) 1 for all n. Obtained using Weisstein's exact formula for Fibonacci k-step number seeing that the function g(N) described in the Formula section is 2*A092921(n-1,N+1). - Andrey Zabolotskiy, Nov 01 2016

Marcus du Sautoy, The Number Mysteries, Fourth Estate, 2011, pages 126 - 127.

Eric Weisstein's World of Mathematics, Coin Tossing

Cf. A135491, A135492, A135493.

a:= proc(n) option remember; local l, j; Digits:= 50;
      if n<3 then n else l:= 0$n;
        for j from 0 while l[n]<1/2 do l:= seq(
          (`if`(i=1, 1.0, l[i-1])+l[n-1])/2, i=1..n)
        od; j
      fi
    end:
seq(a(n), n=1..16);  # Alois P. Heinz, Nov 01 2016

a[n_] := a[n] = Module[{l, j}, If[n < 3, n, l = Table[0, {n}]; For[j = 0, l[[n]] < 1/2, j++, l = Table[(If[i == 1, 1, l[[i - 1]]] + l[[n - 1]])/2, {i, n}]]; j]];
Array[a, 16] (* Jean-François Alcover, May 31 2019, after Alois P. Heinz *)

step(v)=my(n=#v); concat([sum(i=1,n-1,v[i])], concat(vector(n-2,i, v[i]), 2*v[n]+v[n-1]))
a(n)=if(n<3, return(n)); my(v=vector(n), flips=1, needed=1/2); v[1]=1; while(v[n]Charles R Greathouse IV, Nov 02 2016

a(n)=if(n<3, return(n)); my(M=2^(n-1),v=powers(2,n-1)[2..n],i=1,m=n); while(1, v[i]=vecsum(v); if(v[i]<=M, return(m)); if(i++>#v, i=1); M*=2; m++) \\ Charles R Greathouse IV, Nov 02 2016

def a(m):
    if m == 1:
        return 1
    g = [2**i for i in range(1, m)]
    sg, lim, n = sum(g), 2**(m-1), m
    while True:
        g.append(sg)
        sg <<= 1
        sg -= g.pop(0)
        if g[-1] <= lim:
            return n
        lim <<= 1
        n += 1
print([a(i) for i in range(1, 15)])
# Andrey Zabolotskiy, Nov 01 2016

For successive integers m, where g(n) is the number of sequences of tosses of a fair coin with runs of fewer than m consecutive heads or tails out of all possible sequences of tosses to n tosses, g(n) = 2^n where n <= m-1, and thereafter g(n) = g(n-1) + g(n-2) + ... + g(n-m+1) and a(m) = the least value of n for which 2g(n) <= 2^n.

a(11)-a(22) from Andrey Zabolotskiy, Nov 01 2016

a(23)-a(27) from Alois P. Heinz, Nov 02 2016

cp's OEIS Frontend

A203536 Number of nX2 0..2 arrays with every element neighboring horizontally or vertically both a 0 and a 1.

Views

Author

Keywords

Comments

Examples

Links

Formula

A170877 Number of binary words of length n with properties that there is no pair of adjacent 1's and no subword of the form X^4 for any string X.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A232275 T(n,k)=Number of nXk 0..3 arrays with every 0 next to a 1, every 1 next to a 2 and every 2 next to a 3 horizontally, vertically, diagonally or antidiagonally, and no adjacent values equal.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A354784 First differences of A000213, also twice A000073.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A273154 Number of 4-power-free binary words of length n.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Python

Python

Extensions

A277828 Least number of tosses of a fair coin needed to have an even chance or better of getting a run of at least m consecutive heads or consecutive tails.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Python

Formula

Extensions