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,8

Links

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

Example

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, ...

Mathematica

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

Crossrefs

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.

Sequence in context: A245563 A356917 A122945 * A205573 A119338 A054124

Adjacent sequences: A209969 A209970 A209971 * A209973 A209974 A209975

Keyword

nonn,tabl,base

Author

Alois P. Heinz, Mar 16 2012

Status

approved