A233940 -id:A233940 - cp's OEIS frontend

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.

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 *)

A234005 Number of binary words of length n avoiding the subword given by the binary expansion of n.

Original entry on oeis.org

1, 1, 3, 5, 12, 21, 33, 81, 177, 338, 667, 1178, 2031, 4105, 6872, 20569, 42744, 84457, 167863, 315633, 590081, 1325032, 2366125, 4408350, 8146016, 16474904, 30266484, 67320433, 112454976, 230099960, 417825921, 1333610936, 2714234540, 5411487988, 10800172911

Offset: 0

Alois P. Heinz, Dec 18 2013

nonn

			a(0) = 1: the empty word.
a(1) = 1: 0.
a(2) = 3: 00, 01, 11.
a(3) = 5: 000, 001, 010, 100, 101.
a(4) = 12: 0000, 0001, 0010, 0011, 0101, 0110, 0111, 1010, 1011, 1101, 1110, 1111.

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

Main diagonal of A209972.

Column k=0 of A233940.

A228612 Number of (possibly overlapping) occurrences of the subword given by the binary expansion of n in all binary words of length n.

Original entry on oeis.org

0, 1, 1, 4, 4, 12, 32, 80, 80, 192, 448, 1024, 2304, 5120, 11264, 24576, 24576, 53248, 114688, 245760, 524288, 1114112, 2359296, 4980736, 10485760, 22020096, 46137344, 96468992, 201326592, 419430400, 872415232, 1811939328, 1811939328, 3758096384, 7784628224

Offset: 0

Alois P. Heinz, Dec 18 2013

nonn

a(2^n) = a(2^n-1) for n>0.

			a(3) = 4 because we have one subword 11 in each of 011, 110 and two overlapping occurrences of 11 in 111.
a(4) = 4 because we have one subword 100 in each of 0100, 1000, 1001, 1100 and no other occurrences in binary words of length 4.
a(5) = 12 because we have one subword 101 in each of 00101, 01010, 01011, 01101, 10100, 10110, 10111, 11010, 11011, 11101 and two overlapping occurrences of 101 in 10101.

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

Cf. A233940.

a(n) = Sum_{k>0} k*A233940(n,k).

A229293 Number of binary words of length n with exactly k (possibly overlapping) occurrences of the subword given by the binary expansion of n for maximal k with at least one word.

Original entry on oeis.org

1, 1, 1, 1, 4, 1, 1, 1, 1, 18, 1, 6, 1, 1, 40, 1, 8, 1, 4, 33, 1, 1, 17, 42, 1120, 1, 12, 11, 448, 1, 1, 1, 84, 52, 1, 985, 1, 10, 1, 316, 3360, 1, 1, 75, 144, 1, 1, 12, 1, 504, 180, 15, 7920, 102, 1, 16, 220, 14, 11440, 17, 1, 1, 264, 1, 20, 3206, 399, 1, 4

Offset: 0

Alois P. Heinz, Dec 18 2013

nonn

			a(4) = 4 because there are 4 binary words of length 4 with one occurrence of 100, namely 0100, 1000, 1001, 1100, and no words with more than one occurrence of 100.

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

Last (positive) terms of rows of A233940.

A229905 Number of binary words of length n with exactly one occurrence of the subword given by the binary expansion of n.

Original entry on oeis.org

0, 1, 1, 2, 4, 10, 30, 26, 78, 156, 278, 722, 1827, 3140, 7800, 5810, 21016, 40260, 76104, 173836, 394492, 520775, 1376090, 3080882, 6887040, 12734023, 28266044, 44217698, 114969792, 211934801, 464129402, 354151217, 1360414116, 2644465928, 5134476403

Offset: 0

Alois P. Heinz, Dec 19 2013

nonn

			a(1) = 1: 1.
a(2) = 1: 10.
a(3) = 2: 011, 110.
a(4) = 4: 0100, 1000, 1001, 1100.
a(5) = 10: 00101, 01010, 01011, 01101, 10100, 10110, 10111, 11010, 11011, 11101.

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

Column k=1 of A233940.

A236231 Number of binary words of length n with exactly 2 (possibly overlapping) occurrences of the subword given by the binary expansion of n.

Original entry on oeis.org

0, 0, 0, 1, 0, 1, 1, 13, 1, 18, 68, 142, 237, 862, 1672, 3188, 1768, 6078, 16090, 32566, 62214, 181695, 380903, 802572, 1634880, 3784693, 7871112, 17020646, 36800640, 78582498, 168074511, 206295476, 209557176, 490017420, 1097340244, 2222684855, 5116364054

Offset: 0

Alois P. Heinz, Jan 20 2014

nonn

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

Column k=2 of A233940.

A236232 Number of binary words of length n with exactly 3 (possibly overlapping) occurrences of the subword given by the binary expansion of n.

Original entry on oeis.org

5, 0, 0, 10, 6, 1, 84, 40, 1662, 8, 276, 1948, 2220, 1788, 52903, 63836, 92548, 108160, 527238, 691832, 4591942, 4085120, 14751215, 22719212, 116689525, 10635080, 42281072, 136612465, 216703500, 987830670, 1083905462, 3170868937, 5311691060, 8407495040

Offset: 7

Alois P. Heinz, Jan 20 2014

nonn

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

Column k=3 of A233940.

A236233 Number of binary words of length n with exactly 4 (possibly overlapping) occurrences of the subword given by the binary expansion of n.

Original entry on oeis.org

2, 0, 0, 1, 0, 0, 1, 0, 829, 0, 1, 135, 33, 1, 13240, 6875, 4214, 1120, 32898, 13380, 916700, 124480, 1436212, 984719, 64373760, 126300, 1658572, 10718156, 10201655, 151128452, 59698016, 302737587, 335666252, 302196960, 1826553416, 42810588352, 9670953778

Offset: 7

Alois P. Heinz, Jan 20 2014

nonn

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

Column k=4 of A233940.

A236234 Number of binary words of length n with exactly 5 (possibly overlapping) occurrences of the subword given by the binary expansion of n.

Original entry on oeis.org

1, 0, 0, 0, 0, 0, 0, 0, 394, 0, 0, 4, 0, 0, 2874, 458, 42, 0, 675, 12, 135358, 448, 65247, 8058, 34741899, 84, 23560, 532949, 199274, 19005607, 1503366, 19302273, 10429164, 3054912, 67835066, 12419002159, 419211720, 185903568, 36708519210, 17236630474

Offset: 7

Alois P. Heinz, Jan 20 2014

nonn

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

Column k=5 of A233940.

A236235 Number of binary words of length n with exactly 6 (possibly overlapping) occurrences of the subword given by the binary expansion of n.

Original entry on oeis.org

181, 0, 0, 0, 0, 0, 535, 17, 0, 0, 1, 0, 14082, 0, 978, 1, 18383716, 0, 52, 15824, 985, 1995824, 12572, 806911, 127964, 3360, 1121590, 3388924416, 8831268, 767760, 5674830623, 1127556150, 436806956, 75269404, 2826220760, 623517360, 178352390026, 4750656064

Offset: 15

Alois P. Heinz, Jan 20 2014

nonn

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

Column k=6 of A233940.

cp's OEIS Frontend

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

A234005 Number of binary words of length n avoiding the subword given by the binary expansion of n.

Views

Author

Keywords

Examples

Links

Crossrefs

A228612 Number of (possibly overlapping) occurrences of the subword given by the binary expansion of n in all binary words of length n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A229293 Number of binary words of length n with exactly k (possibly overlapping) occurrences of the subword given by the binary expansion of n for maximal k with at least one word.

Views

Author

Keywords

Examples

Links

Crossrefs

A229905 Number of binary words of length n with exactly one occurrence of the subword given by the binary expansion of n.

Views

Author

Keywords

Examples

Links

Crossrefs

A236231 Number of binary words of length n with exactly 2 (possibly overlapping) occurrences of the subword given by the binary expansion of n.

Views

Author

Keywords

Links

Crossrefs

A236232 Number of binary words of length n with exactly 3 (possibly overlapping) occurrences of the subword given by the binary expansion of n.

Views

Author

Keywords

Links

Crossrefs

A236233 Number of binary words of length n with exactly 4 (possibly overlapping) occurrences of the subword given by the binary expansion of n.

Views

Author

Keywords

Links

Crossrefs

A236234 Number of binary words of length n with exactly 5 (possibly overlapping) occurrences of the subword given by the binary expansion of n.

Views

Author

Keywords

Links

Crossrefs

A236235 Number of binary words of length n with exactly 6 (possibly overlapping) occurrences of the subword given by the binary expansion of n.

Views

Author

Keywords

Links

Crossrefs