A005251 -id:A005251 - cp's OEIS frontend

A207000 T(n,k)=Number of nXk 0..1 arrays avoiding 0 1 0 horizontally and 0 1 1 vertically.

2, 4, 4, 7, 16, 7, 12, 49, 49, 12, 21, 144, 230, 144, 20, 37, 441, 1011, 1020, 400, 33, 65, 1369, 4705, 6612, 4120, 1089, 54, 114, 4225, 22412, 45932, 38144, 16109, 2916, 88, 200, 12996, 105936, 329734, 382349, 211471, 61003, 7744, 143, 351, 40000, 497727

Offset: 1

R. H. Hardin Feb 14 2012

Table starts
..2....4......7......12........21.........37...........65...........114
..4...16.....49.....144.......441.......1369.........4225.........12996
..7...49....230....1011......4705......22412.......105936........497727
.12..144...1020....6612.....45932.....329734......2346621......16555996
.20..400...4120...38144....382349....3997768.....41429335.....424457832
.33.1089..16109..211471...3032756...45723467....683241763...10070110597
.54.2916..61003.1124120..22816988..490003769..10432265840..218637649146
.88.7744.227197.5856490.167677230.5103567157.154004233160.4567604720632

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

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

Column 1 is A000071(n+3)
Column 2 is A188516
Column 3 is A206780
Row 1 is A005251(n+3)
Row 2 is A188501
Row 3 is A206878

A209972 Number of binary words of length n avoiding the subword given by the binary expansion of k; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 3, 1, 1, 1, 2, 3, 4, 1, 1, 1, 2, 4, 5, 5, 1, 1, 1, 2, 4, 7, 8, 6, 1, 1, 1, 2, 4, 7, 12, 13, 7, 1, 1, 1, 2, 4, 7, 12, 20, 21, 8, 1, 1, 1, 2, 4, 7, 12, 21, 33, 34, 9, 1, 1, 1, 2, 4, 8, 13, 20, 37, 54, 55, 10, 1, 1, 1, 2, 4, 8, 15, 24, 33, 65, 88, 89, 11, 1, 1

Offset: 0

Alois P. Heinz, Mar 16 2012

			Square array begins:
  1,  1,  1,   1,   1,   1,   1,   1,   1, ...
  1,  1,  2,   2,   2,   2,   2,   2,   2, ...
  1,  1,  3,   3,   4,   4,   4,   4,   4, ...
  1,  1,  4,   5,   7,   7,   7,   7,   8, ...
  1,  1,  5,   8,  12,  12,  12,  13,  15, ...
  1,  1,  6,  13,  20,  21,  20,  24,  28, ...
  1,  1,  7,  21,  33,  37,  33,  44,  52, ...
  1,  1,  8,  34,  54,  65,  54,  81,  96, ...
  1,  1,  9,  55,  88, 114,  88, 149, 177, ...

Alois P. Heinz, Antidiagonals n = 0..150, flattened

Columns give: 0, 1: A000012, 2: A001477(n+1), 3: A000045(n+2), 4, 6: A000071(n+3), 5: A005251(n+3), 7: A000073(n+3), 8, 12, 14: A008937(n+1), 9, 11, 13: A049864(n+2), 10: A118870, 15: A000078(n+4), 16, 20, 24, 26, 28, 30: A107066, 17, 19, 23, 25, 29: A210003, 18, 22: A209888, 21: A152718(n+3), 27: A210021, 31: A001591(n+5), 32: A001949(n+5), 33, 35, 37, 39, 41, 43, 47, 49, 53, 57, 61: A210031.

Main diagonal equals A234005 or column k=0 of A233940.

A[n_, k_] := Module[{bb, cnt = 0}, Do[bb = PadLeft[IntegerDigits[j, 2], n]; If[SequencePosition[bb, IntegerDigits[k, 2], 1]=={}, cnt++], {j, 0, 2^n-1 }]; cnt];
Table[A[n-k, k], {n, 0, 12}, {k, n, 0, -1}] // Flatten (* Jean-François Alcover, Nov 01 2021 *)

A221499 T(n,k)=Majority value maps: number of nXk binary arrays indicating the locations of corresponding elements equal to at least half of their horizontal and antidiagonal neighbors in a random 0..3 nXk array.

Original entry on oeis.org

1, 2, 1, 4, 7, 1, 7, 33, 21, 1, 12, 119, 228, 65, 1, 21, 457, 1733, 1561, 200, 1, 37, 1710, 14297, 24485, 10648, 616, 1, 65, 6466, 111042, 420022, 345755, 72625, 1897, 1, 114, 24433, 874106, 6665056, 12253352, 4882030, 495329, 5842, 1, 200, 92196, 6765307

Offset: 1

R. H. Hardin Jan 18 2013

Table starts
.1......2.........4...........7...........12............21............37
.1......7........33.........119..........457..........1710..........6466
.1.....21.......228........1733........14297........111042........874106
.1.....65......1561.......24485.......420022.......6665056.....107190767
.1....200.....10648......345755.....12253352.....395300442...12890161742
.1....616.....72625.....4882030....356799776...23379869304.1542965772979
.1...1897....495329....68933905..10385011060.1381866811158
.1...5842...3378333...973340015.302233979821
.1..17991..23041525.13743460075
.1..55405.157152036
.1.170625
.1

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

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

Column 2 is A218836
Column 3 is A221030
Column 4 is A221031
Row 1 is A005251(n+2)
Row 2 is A221036

A057985 Start with 0 and repeatedly substitute: 0->01, 1->12, 2->0.

Original entry on oeis.org

0, 1, 1, 2, 1, 2, 0, 1, 2, 0, 0, 1, 1, 2, 0, 0, 1, 0, 1, 1, 2, 1, 2, 0, 0, 1, 0, 1, 1, 2, 0, 1, 1, 2, 1, 2, 0, 1, 2, 0, 0, 1, 0, 1, 1, 2, 0, 1, 1, 2, 1, 2, 0, 0, 1, 1, 2, 1, 2, 0, 1, 2, 0, 0, 1, 1, 2, 0, 0, 1, 0, 1, 1, 2, 0, 1, 1, 2, 1, 2, 0, 0, 1, 1, 2, 1, 2, 0, 1, 2, 0, 0, 1, 0, 1, 1

Offset: 1

Clark Kimberling, Oct 30 2000

nonn

This is the fixed point of the morphism 0->01, 1->12, 2->0 starting with 0. Let u be the sequence of positions of 0, and likewise, v for 1 and w for 2. Let U, V, W be the limits of u(n)/n, v(n)/n, w(n)/n, respectively. Then 1/U + 1/V + 1/W = 1, where U = 3.079595623491438786010417..., V = 2.324717957244746025960908..., W = U + 1. If n >=2, then u(n) - u(n-1) is in {1,2,3,4,6}, v(n) - v(n-1) is in {1,2,3,4}, and w(n) - w(n-1) is in {2,3,4,5,7}. For n >= 1, the number of terms resulting from n iterations of the morphism is A005251(n+2). - Clark Kimberling, May 20 2017.

Clark Kimberling, Table of n, a(n) for n = 1..10000
Index entries for sequences that are fixed points of mappings

Cf. A287066 (initial term 1 instead of 0).

t = Nest[Flatten[# /. {0 -> {0, 1}, 1 -> {1, 2}, 2 -> {0}}] &, {0}, 10] (* A057985 *)
Flatten[Position[t, 0]] (* A057986 *)
Flatten[Position[t, 1]] (* A057987 *)
Flatten[Position[t, 2]] (* A057988 *)
(* Clark Kimberling, May 13 2013 *)

A077855 Expansion of 1/((1-2x+x^2-x^3)(1-x)).

Original entry on oeis.org

1, 3, 6, 11, 20, 36, 64, 113, 199, 350, 615, 1080, 1896, 3328, 5841, 10251, 17990, 31571, 55404, 97228, 170624, 299425, 525455, 922110, 1618191, 2839728, 4983376, 8745216, 15346785, 26931731, 47261894, 82938843, 145547524, 255418100, 448227520, 786584465

Offset: 0

N. J. A. Sloane, Nov 17 2002

a(n) is the number of binary words of length n+2 such that there is at least one run of 0's and every run of 0's is of length >=2. a(1)=3 because we have: {0,0,0}, {0,0,1}, {1,0,0}. - Geoffrey Critzer, Jan 12 2013
INVERT transform of A099254: (1, 2, 1, -2, -4, -2, 3, 6, 3, ...). - Gary W. Adamson, Jan 11 2017
a(n) is the number of nonempty subsets A of {1, 2, ..., n+1} with the property that every element in A has at least one consecutive neighbor also in A. That is, for every element x in A, either x-1 is in A or x+1 is in A. - MingKun Yue, Mar 07 2025

Seiichi Manyama, Table of n, a(n) for n = 0..4092
Index entries for linear recurrences with constant coefficients, signature (3,-3,2,-1).

Cf. A018918, A099254, A005314 (first differences).

nn=40; a=x^2/(1-x); Drop[CoefficientList[Series[(a+1)/(1-x a/(1-x))/(1-x)-1/(1-x), {x,0,nn}], x], 2] (* Geoffrey Critzer, Jan 12 2013 *)
LinearRecurrence[{3, -3, 2, -1}, {1, 3, 6, 11}, 36] (* or *)
CoefficientList[ Series[1/(x^4 - 2 x^3 + 3 x^2 - 3 x + 1), {x, 0, 35}], x] (* Robert G. Wilson v, Nov 25 2016 *)

Vec((1-x)^(-1)/(1-2*x+x^2-x^3)+O(x^99)) \\ Charles R Greathouse IV, Sep 27 2012

G.f.: 1/((1-2*x+x^2-x^3)*(1-x)).
a(n) = A005251(n+4) - 1. a(n+1) - a(n) = A005314(n+2). - R. J. Mathar, Sep 19 2008
a(n) = 3*a(n-1) - 3*a(n-2) + 2*a(n-3) - a(n-4). - Seiichi Manyama, Nov 25 2016
a(n) = Sum_{i=1..(n+3)} binomial((n+3)-i, (n+3)-3*i). - Wesley Ivan Hurt, Jul 07 2020
a(n) ~ (48 - 11*r + 29*r^2) / (23 * r^n), where r = 0.569840290998... is the root of the equation r*(2 - r + r^2) = 1. - Vaclav Kotesovec, Apr 15 2024
From MingKun Yue, Mar 07 2025: (Start)
a(n) = 2*a(n-1) - a(n-2) + a(n-3) + 1.
a(n) = a(n-1) + Sum_{i=1..(n-3)} a(i) + n. (End)

A144795 A positive integer n is included if every 1 in binary n is next to at least one other 1.

Original entry on oeis.org

3, 6, 7, 12, 14, 15, 24, 27, 28, 30, 31, 48, 51, 54, 55, 56, 59, 60, 62, 63, 96, 99, 102, 103, 108, 110, 111, 112, 115, 118, 119, 120, 123, 124, 126, 127, 192, 195, 198, 199, 204, 206, 207, 216, 219, 220, 222, 223, 224, 227, 230, 231, 236, 238, 239, 240, 243, 246

Offset: 1

Leroy Quet, Sep 21 2008

n is included if A144790(n) >= 2.

A173024 is a subsequence. - Reinhard Zumkeller, Feb 07 2010

Michael De Vlieger, Table of n, a(n) for n = 1..10000

Cf. A144790, A144794.
Cf. A004760, A173022, A005251, A173025. - Reinhard Zumkeller, Feb 07 2010
Complement of A377169.

isA144795 := proc(n) local bind,i ; bind := convert(n,base,2) ; for i from 1 to nops(bind) do if i = 1 then if op(i,bind) = 1 and op(i+1,bind) = 0 then RETURN(false) : fi; elif i = nops(bind) then if op(i,bind) = 1 and op(i-1,bind) = 0 then RETURN(false) : fi; else if op(i,bind) = 1 and op(i-1,bind) = 0 and op(i+1,bind) = 0 then RETURN(false) : fi; fi; od: RETURN(true) ; end: for n from 3 to 400 do if isA144795(n) then printf("%d,",n) ; fi; od: # R. J. Mathar, Sep 29 2008

Select[Range@ 250, AllTrue[Map[Length, Select[Split@ IntegerDigits[#, 2], First@ # == 1 &]], # > 1 &] &] (* Michael De Vlieger, Aug 20 2017 *)

Extended by R. J. Mathar, Sep 29 2008

A188508 T(n,k)=Number of nXk binary arrays without the pattern 0 1 0 diagonally, vertically or horizontally.

Original entry on oeis.org

2, 4, 4, 7, 16, 7, 12, 49, 49, 12, 21, 144, 229, 144, 21, 37, 441, 971, 971, 441, 37, 65, 1369, 4351, 5626, 4351, 1369, 65, 114, 4225, 20124, 35079, 35079, 20124, 4225, 114, 200, 12996, 92597, 230877, 317751, 230877, 92597, 12996, 200, 351, 40000, 423074

Offset: 1

R. H. Hardin Apr 02 2011

Table starts
...2......4.......7........12..........21............37..............65
...4.....16......49.......144.........441..........1369............4225
...7.....49.....229.......971........4351.........20124...........92597
..12....144.....971......5626.......35079........230877.........1512392
..21....441....4351.....35079......317751.......3121877........30288308
..37...1369...20124....230877.....3121877......47153387.......697038111
..65...4225...92597...1512392....30288308.....697038111.....15602080066
.114..12996..423074...9787958...288040928...10000092025....335304991524
.200..40000.1932355..63259244..2737303569..143394872372...7194757384224
.351.123201.8836938.409715970.26117921403.2069826687060.155853551899068

			Some solutions for 5X3
..1..1..0....1..0..1....0..1..1....1..0..0....1..1..1....1..1..1....0..0..0
..1..1..0....1..1..1....1..0..1....1..1..1....1..0..0....1..1..1....1..0..0
..1..1..1....1..1..1....1..0..0....1..1..1....1..0..0....1..0..1....1..1..1
..0..1..1....1..0..1....0..0..0....1..1..1....0..0..1....1..1..0....0..1..1
..0..0..0....0..0..1....0..0..1....0..0..0....0..0..1....1..1..0....0..0..0

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

Column 1 is A005251(n+3)

A221290 T(n,k) = Equals two maps: number of n X k binary arrays indicating the locations of corresponding elements equal to exactly two of their horizontal and antidiagonal neighbors in a random 0..3 n X k array.

Original entry on oeis.org

1, 1, 1, 2, 4, 1, 4, 16, 12, 1, 7, 52, 92, 37, 1, 12, 200, 673, 556, 114, 1, 21, 792, 5912, 9107, 3332, 351, 1, 37, 3080, 48298, 172904, 123958, 19996, 1081, 1, 65, 12164, 396846, 2890017, 4983598, 1686304, 119972, 3329, 1, 114, 47827, 3240527, 49684593

Offset: 1

R. H. Hardin, Jan 09 2013

Table starts
.1.....1.......2.........4..........7..........12.........21........37
.1.....4......16........52........200.........792.......3080.....12164
.1....12......92.......673.......5912.......48298.....396846...3240527
.1....37.....556......9107.....172904.....2890017...49684593.821323042
.1...114....3332....123958....4983598...172905144.6138441061
.1...351...19996...1686304..143511784.10344276279
.1..1081..119972..22931365.4129628435
.1..3329..719836.311813067
.1.10252.4319012
.1.31572
.1

			Some solutions for n=3, k=4
..0..0..1..0....0..0..0..0....0..1..0..0....0..0..0..1....0..0..0..1
..0..0..1..0....0..1..0..0....1..0..1..0....0..0..0..0....1..0..0..0
..0..1..0..0....1..0..1..0....1..1..1..0....1..1..0..0....1..1..0..0

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

Column 2 is A099098.
Column 3 is A220932.
Column 4 is A220933.
Row 1 is A005251(n+1).
Row 2 is A220936.

A303696 Number A(n,k) of binary words of length n with k times as many occurrences of subword 101 as occurrences of subword 010; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

1, 1, 2, 1, 2, 4, 1, 2, 4, 7, 1, 2, 4, 6, 12, 1, 2, 4, 6, 12, 21, 1, 2, 4, 6, 10, 20, 37, 1, 2, 4, 6, 10, 17, 38, 65, 1, 2, 4, 6, 10, 16, 28, 66, 114, 1, 2, 4, 6, 10, 16, 26, 49, 124, 200, 1, 2, 4, 6, 10, 16, 26, 42, 84, 224, 351, 1, 2, 4, 6, 10, 16, 26, 42, 70, 148, 424, 616

Offset: 0

Alois P. Heinz, Apr 28 2018

A(n,n) is the number of binary words of length n avoiding both subwords 101 and 010. A(4,4) = 10: 0000, 0001, 0011, 0110, 0111, 1000, 1001, 1100, 1110, 1111.

			Square array A(n,k) begins:
    1,   1,   1,   1,   1,   1,   1, ...
    2,   2,   2,   2,   2,   2,   2, ...
    4,   4,   4,   4,   4,   4,   4, ...
    7,   6,   6,   6,   6,   6,   6, ...
   12,  12,  10,  10,  10,  10,  10, ...
   21,  20,  17,  16,  16,  16,  16, ...
   37,  38,  28,  26,  26,  26,  26, ...
   65,  66,  49,  42,  42,  42,  42, ...
  114, 124,  84,  70,  68,  68,  68, ...
  200, 224, 148, 116, 110, 110, 110, ...
  351, 424, 263, 196, 178, 178, 178, ...

Alois P. Heinz, Antidiagonals for n = 0..200, flattened

Columns k=0-3 give: A005251(n+3), A164146, A303430, A307795.
Main diagonal gives A128588(n+1).
Cf. A000045, A307796.

b:= proc(n, t, h, c, k) option remember; `if`(abs(c)>k*n, 0,
     `if`(n=0, 1, b(n-1, [1, 3, 1][t], 2, c-`if`(h=3, k, 0), k)
                + b(n-1, 2, [1, 3, 1][h], c+`if`(t=3, 1, 0), k)))
    end:
A:= (n, k)-> b(n, 1$2, 0, min(k, n)):
seq(seq(A(n, d-n), n=0..d), d=0..14);

b[n_, t_, h_, c_, k_] := b[n, t, h, c, k] = If[Abs[c] > k n, 0, If[n == 0, 1, b[n - 1, {1, 3, 1}[[t]], 2, c - If[h == 3, k, 0], k] + b[n - 1, 2, {1, 3, 1}[[h]], c + If[t == 3, 1, 0], k]]];
A[n_, k_] := b[n, 1, 1, 0, Min[k, n]];
Table[Table[A[n, d - n], {n, 0, d}], {d, 0, 14}] // Flatten (* Jean-François Alcover, Mar 20 2020, from Maple *)

ceiling(A(n,n)/2) = A000045(n+1).

A306680 Square array A(n,k), n >= 0, k >= 0, read by antidiagonals, where column k is the expansion of g.f. ((1-x)^(k-1))/((1-x)^k-x^(k+1)).

Original entry on oeis.org

1, 1, 2, 1, 1, 3, 1, 1, 2, 4, 1, 1, 1, 3, 5, 1, 1, 1, 2, 5, 6, 1, 1, 1, 1, 4, 8, 7, 1, 1, 1, 1, 2, 7, 13, 8, 1, 1, 1, 1, 1, 5, 12, 21, 9, 1, 1, 1, 1, 1, 2, 11, 21, 34, 10, 1, 1, 1, 1, 1, 1, 6, 21, 37, 55, 11, 1, 1, 1, 1, 1, 1, 2, 16, 37, 65, 89, 12

Offset: 0

Seiichi Manyama, Mar 05 2019

			A(4,1) = A306713(4,1) = 5, A(4,2) = A306713(8,2) = 4.
Square array begins:
   1,  1,  1,  1,  1,  1, 1, 1, 1, ...
   2,  1,  1,  1,  1,  1, 1, 1, 1, ...
   3,  2,  1,  1,  1,  1, 1, 1, 1, ...
   4,  3,  2,  1,  1,  1, 1, 1, 1, ...
   5,  5,  4,  2,  1,  1, 1, 1, 1, ...
   6,  8,  7,  5,  2,  1, 1, 1, 1, ...
   7, 13, 12, 11,  6,  2, 1, 1, 1, ...
   8, 21, 21, 21, 16,  7, 2, 1, 1, ...
   9, 34, 37, 37, 36, 22, 8, 2, 1, ...

Seiichi Manyama, Antidiagonals n = 0..139, flattened

Columns 0-9 give A000027(n+1), A000045(n+1), A005251(n+1), A003522, A005676, A099132, A293169, A306721, A306752, A306753.

Cf. A306646, A306713, A306735.

T[n_, k_] := Sum[Binomial[n - j, k*j], {j, 0, n}]; Table[T[k, n - k], {n, 0, 11}, {k, 0, n}] // Flatten (* Amiram Eldar, Jun 21 2021 *)

A(n,k) = Sum_{j=0..n} binomial(n-j,k*j).

A(n,k) = A306713(k*n,k) for k > 0.

cp's OEIS Frontend

A207000 T(n,k)=Number of nXk 0..1 arrays avoiding 0 1 0 horizontally and 0 1 1 vertically.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A209972 Number of binary words of length n avoiding the subword given by the binary expansion of k; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

A221499 T(n,k)=Majority value maps: number of nXk binary arrays indicating the locations of corresponding elements equal to at least half of their horizontal and antidiagonal neighbors in a random 0..3 nXk array.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A057985 Start with 0 and repeatedly substitute: 0->01, 1->12, 2->0.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A077855 Expansion of 1/((1-2*x+x^2-x^3)*(1-x)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A144795 A positive integer n is included if every 1 in binary n is next to at least one other 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A188508 T(n,k)=Number of nXk binary arrays without the pattern 0 1 0 diagonally, vertically or horizontally.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A221290 T(n,k) = Equals two maps: number of n X k binary arrays indicating the locations of corresponding elements equal to exactly two of their horizontal and antidiagonal neighbors in a random 0..3 n X k array.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A303696 Number A(n,k) of binary words of length n with k times as many occurrences of subword 101 as occurrences of subword 010; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

A077855 Expansion of 1/((1-2x+x^2-x^3)(1-x)).