cp's OEIS Frontend

A109435 Triangle read by rows: T(n,m) = number of binary numbers n digits long, which have m 0's as a substring.

%I A109435 #21 Jun 05 2025 10:08:42
%S A109435 1,2,1,4,3,1,8,7,3,1,16,15,8,3,1,32,31,19,8,3,1,64,63,43,20,8,3,1,128,
%T A109435 127,94,47,20,8,3,1,256,255,201,107,48,20,8,3,1,512,511,423,238,111,
%U A109435 48,20,8,3,1,1024,1023,880,520,251,112,48,20,8,3,1,2048,2047,1815,1121,558
%N A109435 Triangle read by rows: T(n,m) = number of binary numbers n digits long, which have m 0's as a substring.
%C A109435 Column 0 is A000079, column 2 is A000225, column 3 is A008466, column 4 is A050231
%C A109435 Column 5 is A050232, column 6 is A050233, the last column is A001792.
%C A109435 A050227 with a leading column of powers of 2. - _R. J. Mathar_, Mar 25 2014
%F A109435 G.f. for column m: x^m/( (1 - Sum_{k=1..m} x^k)*(1-2*x) ). - _Geoffrey Critzer_, Jan 07 2014
%e A109435 Triangle begins:
%e A109435 n\m_0__1__2__3__4__5
%e A109435 0|  1  0  0  0  0  0
%e A109435 1|  2  1  0  0  0  0
%e A109435 2|  4  3  1  0  0  0
%e A109435 3|  8  7  3  1  0  0
%e A109435 4| 16 15  8  3  1  0
%e A109435 5| 32 31 19  8  3  1
%e A109435 T(5,3)=8 because there are 8 length 5 binary words that contain 000 as a contiguous substring:  00000, 00001, 00010, 00011, 01000, 10000, 10001, 11000. - _Geoffrey Critzer_, Jan 07 2014
%p A109435 A109435 := proc(n,k)
%p A109435     option remember ;
%p A109435     if n< k then
%p A109435         0;
%p A109435     elif n = k then
%p A109435         1;
%p A109435     else
%p A109435         2*procname(n-1,k)+2^(n-1-k)-procname(n-1-k,k) ;
%p A109435     end if;
%p A109435 end proc:
%p A109435 seq(seq( A109435(n,k),k=0..n),n=0..12) ; # _R. J. Mathar_, Jun 05 2025
%t A109435 T[n_, m_] := Length[ Select[ StringPosition[ #, StringDrop[ ToString[10^m], 1]] & /@ Table[ ToString[ FromDigits[ IntegerDigits[i, 2]]], {i, 2^n, 2^(n + 1) - 1}], # != {} &]]; Flatten[ Table[ T[n, m], {n, 0, 11}, {m, 0, n}]]
%t A109435 nn=15;Map[Select[#,#>0&]&,Transpose[Table[CoefficientList[Series[x^m/(1-Sum[x^k,{k,1,m}])/(1-2x),{x,0,nn}],x],{m,0,nn}]]]//Grid (* _Geoffrey Critzer_, Jan 07 2014 *)
%Y A109435 Cf. A109433, A001792, A109436, A102712 (row sums ?).
%K A109435 base,nonn,tabl
%O A109435 0,2
%A A109435 _Robert G. Wilson v_, Jun 28 2005