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
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, ...
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.
-
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 *)
A277678
Number T(n,k) of binary words of length n containing exactly k (possibly overlapping) occurrences of the subword 11011; triangle T(n,k), n>=0, k=0..max(0,floor((n-2)/3)), read by rows.
Original entry on oeis.org
1, 2, 4, 8, 16, 31, 1, 60, 4, 116, 12, 225, 30, 1, 437, 70, 5, 849, 158, 17, 1649, 351, 47, 1, 3202, 770, 118, 6, 6217, 1669, 283, 23, 12071, 3578, 664, 70, 1, 23438, 7599, 1535, 189, 7, 45510, 16016, 3500, 480, 30, 88368, 33545, 7876, 1182, 100, 1, 171586
Offset: 0
Triangle T(n,k) begins:
: 1;
: 2;
: 4;
: 8;
: 16;
: 31, 1;
: 60, 4;
: 116, 12;
: 225, 30, 1;
: 437, 70, 5;
: 849, 158, 17;
: 1649, 351, 47, 1;
: 3202, 770, 118, 6;
Row sums except column k=0 give
A276785.
-
b:= proc(n, t) option remember; expand(
`if`(n=0, 1, b(n-1, [1, 1, 4, 1, 1][t])+
`if`(t=5, x, 1)* b(n-1, [2, 3, 3, 5, 3][t])))
end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 1)):
seq(T(n), n=0..20);
# second Maple program:
gf:= k-> `if`(k=0, -(x^4+x^3+1), x^5*(x^3*(x^2+x-1))^(k-1))
/(x^5+x^4-x^3+2*x-1)^(k+1):
T:= (n, k)-> coeff(series(gf(k), x, n+1), x, n):
seq(seq(T(n, k), k=0..max(0, floor((n-2)/3))), n=0..20);
-
b[n_, t_] := b[n, t] = Expand[
If[n == 0, 1, b[n-1, {1, 1, 4, 1, 1}[[t]]] +
If[t == 5, x, 1]*b[n-1, {2, 3, 3, 5, 3}[[t]]]]];
T[n_] := CoefficientList[b[n, 1], x];
Table[T[n], {n, 0, 20}] // Flatten (* Jean-François Alcover, Apr 29 2022, after Alois P. Heinz *)
A276785
Number of binary strings of length n containing the substring 11011.
Original entry on oeis.org
0, 0, 0, 0, 0, 1, 4, 12, 31, 75, 175, 399, 894, 1975, 4313, 9330, 20026, 42704, 90558, 191117, 401654, 841016, 1755249, 3652663, 7581369, 15698735, 32438224, 66897295, 137718495, 283056086, 580906268, 1190538424, 2436854280, 4982012329, 10174319500, 20756971236, 42306806495, 86153127395
Offset: 0
Showing 1-3 of 3 results.