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
Examples
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, ...
Links
- Alois P. Heinz, Antidiagonals n = 0..150, flattened
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.
Programs
-
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 *)